Факторизация Python

Question

Мне просто хотелось бы узнать, как лучше всего перечислить все целочисленные факторы числа, учитывая словарь его основных факторов и их показателей.
Например, если у нас есть {2: 3, 3: 2, 5: 1} (2 ^ 3 * 3 ^ 2 * 5 = 360)
Тогда я мог бы написать:

for i in range(4):
  for j in range(3):
    for k in range(1):
      print 2**i * 3**j * 5**k

Но здесь у меня есть 3 ужасных петли. Можно ли абстрагировать это в функцию с учетом факторизации в качестве аргумента объекта словаря?

Answer 1

Я написал об этом , и самый быстрый чистый python (без itertools) приходит из сообщения Тима Питерса в список python и использует вложенные рекурсивные генераторы:

def divisors(factors) :
    """
    Generates all divisors, unordered, from the prime factorization.
    """
    ps = sorted(set(factors))
    omega = len(ps)

    def rec_gen(n = 0) :
        if n == omega :
            yield 1
        else :
            pows = [1]
            for j in xrange(factors.count(ps[n])) :
                pows += [pows[-1] * ps[n]]
            for q in rec_gen(n + 1) :
                for p in pows :
                    yield p * q

    for p in rec_gen() :
        yield p

Заметьте, что при написании, он принимает список основных факторов, а не словарь, то есть [2, 2, 2, 3, 3, 5] вместо {2 : 3, 3 : 2, 5 : 1}.

Answer 2

Использование itertools.product из Python 2.6:

#!/usr/bin/env python
import itertools, operator

def all_factors(prime_dict):
    series = [[p**e for e in range(maxe+1)] for p, maxe in prime_dict.items()]
    for multipliers in itertools.product(*series):
        yield reduce(operator.mul, multipliers)

Пример:

print sorted(all_factors({2:3, 3:2, 5:1}))

Выход:

[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60,
 72, 90, 120, 180, 360]

Answer 3

Ну, не только у вас есть 3 цикла, но этот подход не будет работать, если у вас более 3 факторов:)

Один из возможных способов:

def genfactors(fdict):    
    factors = set([1])

    for factor, count in fdict.iteritems():
        for ignore in range(count):
            factors.update([n*factor for n in factors])
            # that line could also be:
            # factors.update(map(lambda e: e*factor, factors))

    return factors

factors = {2:3, 3:2, 5:1}

for factor in genfactors(factors):
    print factor

Кроме того, вы можете избежать дублирования некоторой работы во внутреннем цикле: если ваш рабочий набор равен (1,3) и вы хотите применить к 2 ^ 3 факторам, мы выполняем:

• (1,3) U (1,3)*2 = (1,2,3,6)
• (1,2,3,6) U (1,2,3,6)*2 = (1,2,3,4,6,12)
• (1,2,3,4,6,12) U (1,2,3,4,6,12)*2 = (1,2,3,4,6,8,12,24)

Посмотрите, сколько дубликатов у нас во вторых наборах?

Но мы можем сделать вместо:

• (1,3) + (1,3)*2 = (1,2,3,6)
• (1,2,3,6) + ((1,3)*2)*2 = (1,2,3,4,6,12)
• (1,2,3,4,6,12) + (((1,3)*2)*2)*2 = (1,2,3,4,6,8,12,24)

Решение выглядит еще лучше без комплектов:

def genfactors(fdict):
    factors = [1]

    for factor, count in fdict.iteritems():
        newfactors = factors
        for ignore in range(count):
            newfactors = map(lambda e: e*factor, newfactors)
            factors += newfactors

    return factors

Answer 4

Да. Если у вас есть алгоритм, который требует n вложенных циклов, вы обычно можете превратить его в рекурсивную функцию:

def print_factors(d, product=1):
    if len(d) == 0:      # Base case: we've dealt with all prime factors, so
        print product    # Just print the product
        return
    d2 = dict(d)         # Copy the dict because we don't want to modify it
    k,v = d2.popitem()   # Pick any k**v pair from it
    for i in range(v+1): # For all possible powers i of k from 0 to v (inclusive)
                         # Multiply the product by k**i and recurse.
        print_factors(d2, product*k**i)

d = {2:3, 3:2, 5:1}
print_factors(d)

Answer 5

По сути, у вас есть набор, состоящий из каждого фактора целевого числа. В вашем примере набор будет {2 2 2 3 3 5}. Каждое строгое подмножество этого набора является факторизацией одного из делителей вашего числа, поэтому, если вы можете сгенерировать все подмножества этого набора, вы можете умножить элементы каждого подмножества вместе и получить все целочисленные делители.

Код должен быть довольно очевиден: сгенерировать список, содержащий факторизацию, сгенерировать все подмножества этого списка (бонусные баллы за использование генератора; я думаю, что в стандартной библиотеке есть соответствующая функция). Затем умножьте и идите оттуда. Не совсем эффективно, но приятно выглядит.