たとえば、1260のように数値係数があるとします。
>>> factors(1260)
[2, 2, 3, 3, 5, 7]
これらの数値から可能なすべてのサブプロダクト、つまり素数分解だけでなく、因子の合計がmax_product未満のすべての因数分解を使用して、Pythonの組み合わせで行うのに最適な方法はどれですか？
素因数から組み合わせを行う場合、組み合わせていない残りの部分がわからないため、製品の残りの部分をリファクタリングする必要があります。
除数関数を改良して、サイズ順に除数の代わりに除数のペアを生成することもできますが、それでも12000までの製品の数に対してこれを行うにはコストがかかります。製品は常に同じでなければなりません。
私は除数ルーチンにリンクされていましたが、他のコードに採用することを証明するために努力する価値はありませんでした。少なくとも私の除数関数は、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)
おそらく、除数が数である数にリンクできる、より小さな除数用のふるいまたは動的計画法ソリューションを作成するための何らかの方法が必要になるでしょう。ただし、重複を避けるのは難しいようです。すべての数の完全な因数分解を保存せずに因数分解を高速化するために、各数の最大の素因数を格納する1つのふるい関数を用意しています...おそらくそれを適応させることができます。
更新：因子の合計は積に近いはずなので、おそらく答えには10未満の因子が多数あります（最大14因子）。
UPDATE2： これが私のコードですが、2を超える部分に対して再帰的または反復的に複数の削除を行う方法を理解し、字句分割を掘り下げて、重複を生成するジャンプビットパターンを置き換える必要があります（1回の置換でのみ哀れなヒット数、 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
解決 策私は受け入れられた答えを細かい解決策から削除しませんが、それは仕事にとって非常に複雑です。プロジェクトオイラーから、ニュージーランドのオービフォールドからのこのヘルパー関数のみを明らかにします。これは、最初に素因数を必要とせずに、より高速に動作します。
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]]
私のタイミングデコレータによるPython2.7での4.85秒での彼の実行の問題88に関連する解決策と、サイコを使用した場合は2.6.6で、サイコを使用しない場合は2.7で3.7秒のカウンタを検出して停止条件を最適化した後。私自身のコードの速度は、受け入れられた回答のコード（私が追加したソートを削除）の30秒から、Python 2.6.6の2.25秒（psycoなしの2.7）およびpsycoの782ミリ秒になりました。