Допустим, у нас есть числовые множители, например 1260:
>>> factors(1260)
[2, 2, 3, 3, 5, 7]
Какой способ лучше всего использовать в комбинациях Python с каждым возможным подпродуктом из этих чисел, то есть со всеми факторингами, а не только с простыми факторами, с суммой факторов меньше, чем max_product?
Если я делаю комбинации из простых факторов, мне приходится рефакторить оставшуюся часть продукта, так как я не знаю оставшуюся часть не в комбинации.
Я также могу улучшить свою функцию divisors, чтобы она производила пары делителей вместо делителей в порядке их размера, но все равно это будет стоить мне сделать это для числа с произведением до 12000. Товар должен оставаться всегда одним и тем же.
Я был связан с подпрограммой divisor, но это не стоило усилий, чтобы доказать, что они адаптируются к моему другому коду. По крайней мере, моя функция делителя заметно быстрее, чем sympy:
def divides(number):
if number<2:
yield number
return
high = [number]
sqr = int(number ** 0.5)
limit = sqr+(sqr*sqr != number)
yield 1
for divisor in xrange(3, limit, 2) if (number & 1) else xrange(2, limit):
if not number % divisor:
yield divisor
high.append(number//divisor)
if sqr*sqr== number: yield sqr
for divisor in reversed(high):
yield divisor
Единственная проблема повторного использования этого кода состоит в том, чтобы связать делители с факторинговым ситом или сделать какой-то itertools.product делителей делителей в парах, которые я бы выдавал парами вместо сортировки по порядку.
Примеры результатов:
[4, 3, 3, 5, 7] (one replacement of two)
[5, 7, 36] (one replacement of three)
[3, 6, 14, 5] (two replacements)
Возможно, мне понадобится какой-то способ создать решения для сита или динамического программирования для меньших делителей, которые можно было бы связать с числами, делителями которых они являются. Хотя кажется, что избежать дублирования сложно. У меня есть одна готовая функция решета, которая хранит самый большой простой множитель для каждого числа для ускорения разложения без сохранения полных разложений каждого числа... возможно, это можно было бы адаптировать.
ОБНОВЛЕНИЕ. Сумма факторов должна быть близка к произведению, поэтому, вероятно, в ответе много факторов ‹= 10 (до 14 факторов).
ОБНОВЛЕНИЕ 2: Вот мой код, но я должен выяснить, как выполнить многократное удаление рекурсивно или итеративно для частей > 2 длиной и выкопать лексическое разбиение, чтобы заменить прыгающие битовые шаблоны, которые создают дубликаты (жалкое количество попаданий только для одной замены, и это не учитывает передачу «разделов одного элемента» внутри single_partition):
from __future__ import print_function
import itertools
import operator
from euler import factors
def subset(seq, mask):
""" binary mask of len(seq) bits, return generator for the sequence """
# this is not lexical order, replace with lexical order masked passing duplicates
return (c for ind,c in enumerate(seq) if mask & (1<<ind))
def single_partition(seq, n = 0, func = lambda x: x):
''' map given function to one partition '''
for n in range(n, (2**len(seq))):
result = tuple(subset(seq,n))
others = tuple(subset(seq,~n))
if len(result) < 2 or len(others) == 0:
#empty subset or only one or all
continue
result = (func(result),)+others
yield result
if __name__=='__main__':
seen, hits, count = set(), 0, 0
for f in single_partition(factors(13824), func = lambda x: reduce(operator.mul, x)):
if f not in seen:
print(f,end=' ')
seen.add(f)
else:
hits += 1
count += 1
print('\nGenerated %i, hits %i' %(count,hits))
УТОЧНЕНИЕ Я рад получить только факторинг с максимальным 5 факторами в части неосновного фактора. Я вручную обнаружил, что неубывающие схемы до 5 одинаковых множителей имеют следующую форму:
partitions of 5 applied to 2**5
1 1 1 1 1 2 2 2 2 2
1 1 1 2 2 2 2 4
1 1 1 3 2 2 8
1 2 2 2 4 4
1 4 2 16
2 3 4 8
РЕШЕНИЕ Я не удаляю принятый ответ из тонкого решения вниз, но он слишком сложен для работы. Из Project Euler я раскрываю только эту вспомогательную функцию из orbifold of NZ, она работает быстрее и не требует сначала простых множителей:
def factorings(n,k=2):
result = []
while k*k <= n:
if n%k == 0:
result.extend([[k]+f for f in factorings(n/k,k)])
k += 1
return result + [[n]]
Соответствующее решение проблемы 88 его запуска в Python 2.7 за 4,85 с моим декоратором времени и после оптимизации условия остановки с помощью найденного счетчика 3,4 с в 2.6.6 с помощью psyco , 3,7 с в 2,7 без псико. Скорость моего собственного кода увеличилась с 30 секунд с кодом в принятом ответе (добавленная мной сортировка удалена) до 2,25 с (2,7 без psyco) и 782 мс с psyco в Python 2.6.6.
