1

私は、パズルの拡張への組み合わせを見つけようとする力ずくのアプローチを行っています。

多数の組み合わせを取得してから、各組み合わせをテストして、特定の基準に適合するかどうかを確認しようとしています。Python の優れた itertools を使用して組み合わせを生成します。基本的に、これにより、それぞれを調べてテストできる反復子が得られます。

これはすぐに返され、 91390の組み合わせを確認できます。

itertools.combinations(range(1, 40), 4)

これには数分かかり、198792594の組み合わせをテストできます。

itertools.combinations(range(1, 122), 5)

次のレベルに到達したら、これに対する答えが必要です。

itertools.combinations(range(1, 365), 6)

364個のセットの6通りの組み合わせになると...非常に時間がかかります。時代。私は本質的に多くの組み合わせを求めていますか? どのようにスケーリングしますか?

4

3 に答える 3

6

365 を求めています 6 = (365 * 364 * ... * 360) / (6 * 5 * ... * 2 * 1) = 3,151,277,509,380 の組み合わせを選択します。それはたくさんあります。3 兆を超える要素をループすることは、Python のデスクトップでは起こりません。

あるはずの数を探しているだけの場合は、すべてを考慮せずにこれを直接計算する式がWikipediaにあります。

編集：私は問題を見ただけで、重みのすべての可能な組み合わせを考慮し、それらが機能するかどうかを確認することで、問題を解決しようとしているようです. この状況では、総当りは明らかに機能しません。より賢い解決策を考える必要があります。

于 2011-10-29T22:26:51.483 に答える
2

これらの数値は次のように計算します。

  1. google.com にアクセス
  2. 「40 choose 4」と入力します
  3. 「121 選択 5」と入力します
  4. 「364 choose 6」と入力

実際の式についてはウィキペディアを参照してください。

階乗関数のようにスケーリングします。

于 2011-10-29T22:25:04.533 に答える
0

itertools のドキュメントによると、number of items returned is n! / r! / (n-r)! when 0 <= r <= n or zero when r > n.

メモリの使用量は少なく、n 個の項目のプールと長さ r の結果のタプルを格納するのに十分です。

于 2011-10-30T00:11:04.547 に答える