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
    Чем вас не устраивает ваш код? Я вижу только один недстаток, возможно, не существенный. Ладно, два. То есть три. Но с ними можно жить. Commented 20 окт. 2021 в 15:27
  • перечислите, пожалуйста, недостатки. Не устраивает, громоздкостью, чувствую, есть другие, более простые и изящные решения.
    – VanoKi
    Commented 20 окт. 2021 в 15:38
  • 2
    ну например, произведение всех чисел списка считает столько раз, сколько чисел в списке. А ведь оно не изменится, поэтому достаточно посчитать его только один раз и потом делить на каждый элемент. Приводить к int тоже нет смысла, там уже и без этого число. Commented 20 окт. 2021 в 16:04
  • 1
    Три недостатка: много раз вычисляется product (линейная сложность -> квадратичная сложность; int(... / ...) теряет точность, лучше ... // ...; неправильно обрабатываются нули в списке. Commented 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
    Commented 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([temp_p // i for i in a])
6
  • 2
    Квадратичное время расчёта не есть гут, когда линейное сделать нетрудно
    – MBo
    Commented 31 мая 2023 в 11:40
  • Стало хуже. Лучше сделайте накопительные произведения слева и справа. Будет и коротко и быстро. Commented 31 мая 2023 в 12:23
  • Можно пример для облегчения понимания алгоритма? Commented 31 мая 2023 в 12:36
  • За линейное время можно сосчитать [prod(a[:1]), prod(a[:2]), prod(a[:3]), ...] - накопительные произведения слева. Аналогично считаются накопительные произведения справа. Из двух списков накопительных произведений за линейное время строится список неполных произведений. Commented 31 мая 2023 в 12:54
  • 1
    так есть гуд? - нет. Вы понимаете, что считаете одни и те же произведения много раз? Посчитайте lprod[i]=lprod[i-1]*a[i] слева направо и rprod[i]=rprod[i+1]*a[i] справа налево
    – MBo
    Commented 31 мая 2023 в 13:02

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

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