-6

数字 x があり、a*b*c のユニークな書き方をすべて見つけたいと考えています。一意とは、2*3*5 が 3*2*5 または 5*3*2 と同じであることを意味します。

x の素因数分解を行い、因数を 3 つのビンに分割する実用的なアルゴリズムがありますが、非常に遅くて野蛮であり、後で重複を削除する必要があるため、一意の組み合わせを生成するより高速な方法があるかどうかに興味があります。ここで直接。

720という数字を考えてみましょう。

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

1 に答える 1

1

Python の場合:

def trifactorgenerator(n):
  return (((i,j,n/(i*j)) 
           for i in range(1, int(n**.5)+1) if n%i==0 
             for j in range(i, int( (n/i)**.5)+1) if n%(i*j) == 0))

この関数には興味深い効果があります。

  • これは真のジェネレーターです。呼び出し元がそのようなリストを作成しない限り、リスト全体がメモリ内にあることはありません。
  • 各タプルはソートされます (例:(2,3,4)決して(2,4,3)
  • 重複を返しません
  • タプルは辞書順で返されます。

参照: https://stackoverflow.com/a/6800214/8747

于 2013-03-10T04:33:39.280 に答える