Факторизация Python
Для меня это было то, что я должен был добавить i386 в список VALID_ARCHS. Странно, но это исправило мою проблему при сборке симулятора.
5 ответов
Ну, не только у вас есть 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
Я писал об этом в блоге, и самый быстрый чистый питон (без 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} .
Да. Если у вас есть алгоритм, который требует вложенных циклов for, вы обычно можете превратить его в рекурсивную функцию:
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)
Использование 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]
По сути, у вас есть набор, состоящий из каждого множителя целевого числа. В вашем примере набор будет {2 2 2 3 3 5} . Каждое строгое подмножество этого набора является факторизацией одного из делителей вашего числа, поэтому, если вы можете сгенерировать все подмножества этого набора, вы можете умножить элементы каждого подмножества вместе и получить все целочисленные делители.
код должен быть довольно очевиден оттуда: сгенерируйте список, содержащий факторизацию, сгенерируйте все подмножества этого списка (бонусные баллы за использование генератора; я думаю, что в стандартной библиотеке есть соответствующая функция). Затем размножайтесь и двигайтесь дальше. Ни в коем случае не оптимально эффективный, но красивый.