0

Прошу помощи у сообщества, задача простейшая, но решить никак не получается. Дано Список чисел, пусть будет [1, 2, 3, 4] необходимо получить список, в котором каждый элемент равен произведению всех остальных элементов списка: [24, 12, 8, 6] - в случае с примером. у меня получилось решить задачу для суммы:

a = [1, 2, 3, 4] 
print([sum(a) - i for i in a])

как мне сделать для того, что бы получить произведения?

def product(a):
    pr = 1
    for i in a:
        pr *= i
    return pr
ans = [int(product(a)/i) for i in a]
print(ans)
4
  • 2
    Чем вас не устраивает ваш код? Я вижу только один недстаток, возможно, не существенный. Ладно, два. То есть три. Но с ними можно жить. 20 окт 2021 в 15:27
  • перечислите, пожалуйста, недостатки. Не устраивает, громоздкостью, чувствую, есть другие, более простые и изящные решения.
    – VanoKi
    20 окт 2021 в 15:38
  • 2
    ну например, произведение всех чисел списка считает столько раз, сколько чисел в списке. А ведь оно не изменится, поэтому достаточно посчитать его только один раз и потом делить на каждый элемент. Приводить к int тоже нет смысла, там уже и без этого число. 20 окт 2021 в 16:04
  • 1
    Три недостатка: много раз вычисляется product (линейная сложность -> квадратичная сложность; int(... / ...) теряет точность, лучше ... // ...; неправильно обрабатываются нули в списке. 20 окт 2021 в 17:14

2 ответа 2

4

В вашем коде я вижу три недостатка:

  • много раз вычисляется product, что делает ваше решение квадратичным по сложности, а можно уложиться в линейное время;

  • int(... / ...) теряет точность, переводя целые (которые в Питоне не ограничены) в вещественные (у которых 53 бита точности). Вот пример:

[9007199254740993, 9007199254740991] -> [9007199254740991, 9007199254740992]
  • неправильно обрабатываются нули в списке.

Возможное решение всех этих проблем ниже.

Код из вопроса int(... / ...) позволяет предположить что в списке только целые.

Наивное решение которое использует свежий Питон (3.8 и выше):

def naive_partial_products(a):
    # если Питон не свежий, то вычислите произведение так
    # p = functools.reduce(operator.mul, a, 1)
    p = math.prod(a)
    return [p // v for v in a]

Это короткое быстрое решение, которое хорошо работает пока в массиве нет нулей. Если нули есть, надо разбирать случаи. Если ноль один, то в ответе все нули кроме одного элемента. Если нулей больше одного, то в ответе одни нули.

Кроме нулей надо внимательно проследить как обрабатываются короткие массивы.

После учёта всех возможностей получается такой симпатичный монстрик:

import math


def partial_products(a):
    zc = a.count(0)
    if zc > 1:
        return [0] * len(a)
    p = math.prod(v for v in a if v != 0)
    if zc == 0:
        return [p // v for v in a]
    return [p if v == 0 else 0 for v in a]


def check(a):
    print(f'{a} -> {partial_products(a)}')


check([])
check([0])
check([0, 0])
check([0, 0, 0])
check([10])
check([0, 10])
check([1, 2, 3, 4])
check([0, 1, 2, 3, 4])
check([0, 0, 1, 2, 3, 4])
$ python partial-products.py 
[] -> []
[0] -> [1]
[0, 0] -> [0, 0]
[0, 0, 0] -> [0, 0, 0]
[10] -> [1]
[0, 10] -> [10, 0]
[1, 2, 3, 4] -> [24, 12, 8, 6]
[0, 1, 2, 3, 4] -> [24, 0, 0, 0, 0]
[0, 0, 1, 2, 3, 4] -> [0, 0, 0, 0, 0, 0]

P.S. Предыдущее решение длинное и сложное со множеством краевых случаев. Можно сделать немного изящнее, но потребуется дополнительная линейная память.

Из списка [1, 2, 3, 4] построим два списка с накопительными произведениями:

a  = [ 1,  2,  3,  4]
lr = [ 1,  1,  2,  6]   # lr[i] = prod(a[     :i])
rl = [24, 12,  4,  1]   # rl[i] = prod(a[i + 1: ])

Список lr строится за линейное время проходом по a слева направо. Список rl строится за линейное время проходом по a справа налево. Его потом придётся перевернуть. Поэлементное произведение lr и rl - ответ.

Код:

def cum_prod(seq):
    p = 1
    for v in seq:
        yield p
        p *= v


def partial_products(a):
    lr = cum_prod(a)
    rl = reversed(tuple(cum_prod(reversed(a))))
    return [a * b for a, b in zip(lr, rl)]
1
  • Спасибо огромнейшее!
    – VanoKi
    21 окт 2021 в 15:14
1
import math

print([math.prod(a[:i] + a[i + 1:]) for i in range(len(a))])

так есть гуд?

import math
a = [0, 0, 1, 2, 3, 4]

temp_p = math.prod(a)
temp_i = a.count(0)
if temp_p == 0 and temp_i == 1:
    i = a.index(0)
    print([0] * i + [math.prod(a[:i] + a[i + 1:])] + [0] * (len(a) - i - 1))
elif temp_i > 1:
    print([0] * len(a))
else:
    print([int(temp_p / i) for i in a])
Новый участник
Vladimir Gonchar — новый участник сайта. Будьте снисходительны, задавая уточняющие вопросы, комментируя и отвечая. Почитайте про нормы поведения.
6
  • 2
    Квадратичное время расчёта не есть гут, когда линейное сделать нетрудно
    – MBo
    12 часов назад
  • Стало хуже. Лучше сделайте накопительные произведения слева и справа. Будет и коротко и быстро. 11 часов назад
  • Можно пример для облегчения понимания алгоритма? 11 часов назад
  • За линейное время можно сосчитать [prod(a[:1]), prod(a[:2]), prod(a[:3]), ...] - накопительные произведения слева. Аналогично считаются накопительные произведения справа. Из двух списков накопительных произведений за линейное время строится список неполных произведений. 11 часов назад
  • так есть гуд? - нет. Вы понимаете, что считаете одни и те же произведения много раз? Посчитайте lprod[i]=lprod[i-1]*a[i] слева направо и rprod[i]=rprod[i+1]*a[i] справа налево
    – MBo
    11 часов назад

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.