AボックスにN個のボールの可能な組み合わせをすべて列挙したいと思います。
例: 3 つのボックスで8 つのボールを処理する必要があります。
box_1 box_2 box_3
case-1 8 0 0
case-2 0 8 0
case-3 0 0 8
case-4 7 1 0
case-5 7 0 1
case-6 6 2 0
...
私の最初の問題は、これを実行するにはAループが必要ですが、 AとNをユーザーの入力にしたいということです。では、ユーザーが必要とする可能性のあるすべての可能なループ数を書かずにどうすればよいでしょうか?
aとNは 2 から ~800 の間の値になるため、計算時間が非常に長くなります。そのアルゴリズムを最適化する方法は?
Python言語を使用して私に答えていただければ幸いです。すべての貢献に感謝します!
これは python 2.6 から問題なく動作します (の 2.5 対応の実装itertools.permutationsも利用可能です)。
>>> import itertools
>>> boxes = 3
>>> balls = 8
>>> rng = list(range(balls + 1)) * boxes
>>> set(i for i in itertools.permutations(rng, boxes) if sum(i) == balls)
{(0, 1, 7), (3, 1, 4), (0, 4, 4), (1, 0, 7), (4, 0, 4), (3, 0, 5), (1, 2, 5), (1, 7, 0), (0, 8, 0), (1, 4, 3), (6, 0, 2), (4, 3, 1), (3, 3, 2), (0, 5, 3), (5, 3, 0), (5, 1, 2), (2, 4, 2), (4, 4, 0), (3, 2, 3), (7, 1, 0), (5, 2, 1), (0, 6, 2), (6, 1, 1), (2, 2, 4), (1, 1, 6), (0, 2, 6), (7, 0, 1), (2, 1, 5), (0, 0, 8), (2, 0, 6), (2, 6, 0), (5, 0, 3), (2, 5, 1), (1, 6, 1), (8, 0, 0), (4, 1, 3), (6, 2, 0), (3, 5, 0), (0, 3, 5), (4, 2, 2), (1, 3, 4), (0, 7, 1), (1, 5, 2), (2, 3, 3), (3, 4, 1)}
擬似コード:
Enumerate(Balls, Boxes)
if Boxes<=0
Error
elseif Boxes=1
Box[1] = Balls
PrintBoxes
else
forall b in 0..Balls
Box[Boxes] = b
Enumerate(Balls-b, Boxes-1)
endfor
endif
end
説明
最初のボックスから始めて、ボックスがない場合は、文句を言って終了します。それが満たされる最後のボックスである場合は、残りのすべてのボールをドロップし、結果を表示します。それ以上のボックスがある場合は、最初に 0 個のボールを追加し、他のボックスで手順を繰り返します。次に、ボールがなくなるまで、1、ボール 2 ボールを追加します。
アルゴリズムが機能することを示すために、実数値、3 つのボール、2 つのボックスの例を示します。
Box と呼ばれるボックスの配列があり、各ボックスには任意の数のボール (値) を入れることができます。PrintBoxes は、ボックスの現在の値を出力します。
Box = (0,0)
Enumerate(3, 2)
b=0
Box = (0,0)
Enumerate(3,1)
Box = (3,0)
Print!
b=1
Box = (0,1)
Enumerate(2,1)
Box = (2,1)
Print!
b=2
Box = (0,2)
Enumerate(1,1)
Box = (1,2)
Print!
b=3
Box = (0,3)
Enumerate(0,1)
Box = (0,3)
Print!
Output:
(3,0)
(2,1)
(1,2)
(0,3)
Which are all the combinations.
3 つのボックスと 3 つのボールの別の例:
Box = (0,0,0)
Enumerate(3, 3)
b=0
Box = (0,0,0)
Enumerate(3,2)
b=0
Box = (0,0,0)
Enumerate(3,1)
Box = (3,0,0)
b=1
Box = (0,1,0)
Enumerate(2,1)
Box = (2,1,0)
b=2
Box = (0,2,0)
Enumerate(1,1)
Box = (1,2,0)
b=3
Box = (0,3,0)
Enumerate(0,1)
Box = (0,3,0)
b=1
Box = (0,0,1)
Enumerate(2,2)
b=0
Box = (0,0,1)
Enumerate(2,1)
Box = (2,0,1)
b=1
Box = (0,1,1)
Enumerate(1,1)
Box = (1,1,1)
b=2
Box = (0,2,1)
Enumerate(0,1)
Box = (0,2,1)
b=2
Box = (0,0,2)
Enumerate(1,2)
b=0
Box = (0,0,2)
Enumerate(1,1)
Box = (1,0,2)
b=1
Box = (0,1,2)
Enumerate(0,1)
Box = (0,1,2)
b=3
Box = (0,0,3)
Enumerate(0,2)
b=0
Box = (0,0,3)
Enumerate(0,1)
Box = (0,0,3)
Output
(3,0,0)
(2,1,0)
(1,2,0)
(0,3,0)
(2,0,1)
(1,1,1)
(0,2,1)
(1,0,2)
(0,1,2)
(0,0,3)
Python で書かれた例については、3.1 のitertools.combinations_with_replacementを参照してください。さらに、組み合わせ論では置換を伴う組み合わせ問題を通常の置換を伴わない組み合わせ問題に変換するのが一般的であり、これは既に 2.6 itertools に組み込まれています。これには、積や順列に基づくソリューションのように、破棄されたタプルを生成しないという利点があります。標準の (n, r) 用語を使用した例を次に示します。この例では (A, N) になります。
import itertools, operator
def combinations_with_replacement_counts(n, r):
size = n + r - 1
for indices in itertools.combinations(range(size), n-1):
starts = [0] + [index+1 for index in indices]
stops = indices + (size,)
yield tuple(map(operator.sub, stops, starts))
>>> list(combinations_with_replacement_counts(3, 8))
[(0, 0, 8), (0, 1, 7), (0, 2, 6), (0, 3, 5), (0, 4, 4), (0, 5, 3), (0, 6, 2), (0, 7, 1), (0, 8, 0), (1, 0, 7), (1, 1, 6), (1, 2, 5), (1, 3, 4), (1, 4, 3), (1, 5, 2), (1, 6, 1), (1, 7, 0), (2, 0, 6), (2, 1, 5), (2, 2, 4), (2, 3, 3), (2, 4, 2), (2, 5, 1), (2, 6, 0), (3, 0, 5), (3, 1, 4), (3, 2, 3), (3, 3, 2), (3, 4, 1), (3, 5, 0), (4, 0, 4), (4, 1, 3), (4, 2, 2), (4, 3, 1), (4, 4, 0), (5, 0, 3), (5, 1, 2), (5, 2, 1), (5, 3, 0), (6, 0, 2), (6, 1, 1), (6, 2, 0), (7, 0, 1), (7, 1, 0), (8, 0, 0)]
上記のように python ジェネレーターを使用することをお勧めしますが、より簡単な (効率については不明) バージョンを次に示します。
def balls_in_baskets(balls=1, baskets=1):
if baskets == 1:
yield [balls]
elif balls == 0:
yield [0]*baskets
else:
for i in xrange(balls+1):
for j in balls_in_baskets(balls-i, 1):
for k in balls_in_baskets(i, baskets-1):
yield j+k
for i in balls_in_baskets(8,3):
print i
次のように、ネストしたい「forループ」ごとにサブジェネレーターを作成する再帰ジェネレーターを定義できます。
def ballsAndBoxes(balls, boxes, boxIndex=0, sumThusFar=0):
if boxIndex < (boxes - 1):
for counter in xrange(balls + 1 - sumThusFar):
for rest in ballsAndBoxes(balls, boxes,
boxIndex + 1,
sumThusFar + counter):
yield (counter,) + rest
else:
yield (balls - sumThusFar,)
これを最上位で呼び出すと、'balls' と 'boxes' 引数のみが必要になります。他の引数はデフォルトとしてそこにあるため、再帰呼び出しで別のものを渡すことができます。あなたの値である（長さ「ボックス」の）整数のタプルを生成します。
この投稿の冒頭で指定した正確なフォーマットを取得するには、次のように呼び出すことができます。
BALLS = 8
BOXES = 3
print '\t',
for box in xrange(1, BOXES + 1):
print '\tbox_%d' % (box,),
print
for position, value in enumerate(ballsAndBoxes(BALLS, BOXES)):
print 'case-%d\t\t%s' % (position + 1,
"\t".join((str(v) for v in value)))
可能性のリストではなく、単に可能性の数を知りたい場合は、次の式が機能します。
可能性 = (N+A-1) CN = (N+A-1)!/(N!x(A-1)!)
aCb (a choose b) は、サイズ a のセットからサイズ b の組み合わせを選択する方法の数です。
! 階乗、すなわち 5!=5*4*3*2*1, n!=n*(n-1)*(n-2)*...*3*2*1 を示します。卵の吸い方を教えてたらごめんなさい。
パイソンでは：
from math import factorial as f
balls=N
boxes=A
def p(balls,boxes):
return f(balls+boxes-1)/f(balls)/f(boxes-1)
p(3,2)
4
p(3,3)
10
これは Gamecat の例と一致します。
式が機能する理由を説明するために、5 つのボールと 3 つのボックスを見てみましょう。ボールはアスタリスクで示します。3-1=2 分割線を配置して、ボールを 3 つの区画に分割します。
たとえば、
* | * | * * * (1,1,3)
* * | * * * | (2,3,0)
* * * * * | | (5,0,0)
7 つのシンボルは、7!=5040 通りの順序で並べることができます。すべてのボールが同じなので、ボールの順序は気にしないので、5! で割ります。同様に、分割線の順序は気にしないので、2! で分割します。これにより、7C5=7!/(5!*2!)=21 の可能性が得られます。
組み合わせに関するウィキペディアの記事には、「繰り返しのある組み合わせの数」というセクションがあり、組み合わせの数を数える質問をよりおいしい方法 (ボールの代わりにドーナツと果物) に言い換えています。
組み合わせを一覧表示する場合は、数が急速に増えることに注意してください。20 個のボールと 9 個のボックスの場合、300 万を超える可能性があります。
編集:私の以前の回答では、この問題を整数パーティションと比較して、可能性の数がどれほど急速に増加するかを示しました。私の新しい答えは、元の質問により関連しています。
独自の関数 answer by Gamecat を使用する場合はhttp://probstat.sourceforge.net/を使用するか、非常に高速です (c で記述)
またはpython 2.6のitertools