1

次の値を取ります。

0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0

合計が 1 である上記の 11 の値のすべてのセットを含む、256 要素のマトリックスである 64x4 マトリックスを生成する関数を作成したいと思います。

これを行うための最も効率的な方法に関するヘルプは非常に役立ちます。

4

2 に答える 2

2

次のコードは、あなたが求めていることを行います。浮動小数点の丸めエラーを回避するために、合計 10 までの整数を使用しました。より早くループを抜け出し、 を発生させる前にドリルダウンさせないようにすることで、おそらく高速に実行できますがStopIteration、コードが不明確になります。

def partitions(n=10, items=range(11), count=4) :
    if count == 0 and n == 0:
        yield []
    elif n < 0 or count < 0:
        raise StopIteration
    for j in xrange(len(items)) :
        ret = [items[j]]
        for k in partitions(n-items[j], items[j:], count-1) :
            yield ret + k

>>> [j for j in partitions()]
[[0, 0, 0, 10], [0, 0, 1, 9], [0, 0, 2, 8], [0, 0, 3, 7], [0, 0, 4, 6],
 [0, 0, 5, 5], [0, 1, 1, 8], [0, 1, 2, 7], [0, 1, 3, 6], [0, 1, 4, 5],
 [0, 2, 2, 6], [0, 2, 3, 5], [0, 2, 4, 4], [0, 3, 3, 4], [1, 1, 1, 7],
 [1, 1, 2, 6], [1, 1, 3, 5], [1, 1, 4, 4], [1, 2, 2, 5], [1, 2, 3, 4],
 [1, 3, 3, 3], [2, 2, 2, 4], [2, 2, 3, 3]]

そのようなサブセットが 64 あるという考えをどこで思いついたのか、よくわかりません。上記の関数は思い付きます

>>> len([j for j in partitions()])
23

4 要素の順序付けられたサブセット。サブセットを順序付けしたくない場合は、再帰呼び出しではなくpartitions、 full を使用して呼び出すことで取得できます。しかし、その後、あなたは得るitemsitems[j:]

>>> len([j for j in partitions()])
286

0そして、4 つの要素のサブセットに制限しない場合は、 (任意の数のゼロを使用して 10 まで追加する無限のサブセットがあります)を取り除く必要があり、10の分割を計算しています。生命、宇宙、そしてすべての究極の質問への答え、または正確に42です。

于 2013-03-12T13:03:32.350 に答える
1

ハイメが言ったように、動的プログラミングはおそらくここで役立つでしょう。この問題は、ツリー内の各ノードに事前に指定された要素の一部が含まれているツリーの再帰的検索として定義できます。ツリーの葉には、合計が 1 になるすべての組み合わせが含まれます。

したがって、検索の各ステップで:

  1. 合計が 1 を超えない次の数を選択します。
  2. この番号をこれまでの番号のセットに追加すると、このセットが次のノードになります。
  3. このノードから、Leave ノード (合計 == 1) に到達するまで繰り返します。

ノード N の下のすべてのノードが完全に探索されるか、N が離脱ノードになったら: 親ノードに移動し、手順 1 から 3 を繰り返します。

于 2013-03-12T08:06:20.337 に答える