Продукт Python произвольного числа переменных

Question

EDIT: Хотя я и сказал в оригинальной публикации, что хотел бы использовать понимание списка, я с радостью принимаю любое решение. Я просто предполагал, что понимание списков было бы самым простым способом сделать это.

---

Я работаю над проблемой, связанной с простой факторизацией, и столкнулся с проблемой понимания списка.

У меня есть список простых факторов числа, и, конечно, в списке может быть любое количество чисел. Это может быть [2,3,5] или просто [2], или [2,3,11,17] и т. Д.

Что бы я хотел, таких чисел, что произведение меньше или равно 100 000. Так, например, если моя простая факторизация [2,3,5], я хотел бы иметь все числа вида (2^a) (3^b) (5^c) для натуральных чисел a, b, c, (2^а) (3^Ь) (5^с) < = 100 000.

Есть ли способ сделать это со списком, учитывая, что число простых факторов является произвольной длиной?

Answer 1

Проверьте это.

import math 

Nmax = 100 
primeLst = [2, 3, 5] 


result = [] 
enumMax = [int(math.floor(math.log(Nmax)/math.log(i))) for i in primeLst] 

def prod(i, curRes): 
    if curRes > Nmax: 
     return 
    if i==len(primeLst): 
     result.append(curRes) 
    else: 
     for j in range(enumMax[i]+1): 
      prod(i+1, curRes * (primeLst[i]**j)) 

prod(0, 1) 

# result: [1, 5, 25, 3, 15, 75, 9, 45, 27, 81, 2, 10, 50, 6, 30, 18, 90, 54, 4, 20, 100, 12, 60, 36, 8, 40, 24, 72, 16, 80, 48, 32, 96, 64] 

Answer 2

Вы можете использовать рекурсивную функцию, которая выбирает один из факторов и умножает текущую сумму до тех пор, пока общая сумма выше предела. Для каждой итерации вы можете тогда рекурсивно называть одну и ту же функцию при переходе к следующему коэффициенту. После того, как вы исчерпали все факторы только дают текущую сумму:

def prods(factors, limit, index = 0, total = 1): 
    # Base case, yield current number 
    if index >= len(factors): 
     yield total 
     return 

    while total <= limit: 
     # Python 3 yield from could be used 
     for res in prods(factors, limit, index + 1, total): 
      yield res 
     total *= factors[index] 

print list(prods([2, 3, 5], 100)) 

Выход:

[1, 5, 25, 3, 15, 75, 9, 45, 27, 81, 2, 10, 50, 6, 30, 18, 90, 54, 4, 20, 100, 12, 60, 36, 8, 40, 24, 72, 16, 80, 48, 32, 96, 64] 

Answer 3

Эта модификация ответ @ niemmi использует heapq.merge слиться каждой из последовательностей от каждого из рекурсивных вызовов производить продукцию в порядке возрастания:

from heapq import merge 

def prods(factors, limit, index = 0, total = 1): 
    # Base case, yield current number 
    if index >= len(factors): 
     yield total 
     return 
    iters = [] 
    while total < limit: 
     iters.append(prods(factors, limit, index + 1, total)) 
     total *= factors[index] 
    for res in merge(*iters): 
     yield res 

print list(prods([2, 3, 5], 100)) 

Там находится выход:

>>> print list(prods([2, 3, 5], 100)) 
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96]