N個のボールをAボックスに組み合わせて列挙しますか？

Question

私はでNボールボックスのすべての可能な組み合わせを列挙します。

例： 私は箱に対処するためのボール持っている：

  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 
... 

を私の第一の問題は、私はこれを実行するには、ループを必要とするが、私ということです欲しいものですとNをユーザの入力とする。だから、ユーザーが必要とする可能性のあるループの数をすべて書き込まずにやる方法は？それは強くので計算時間に厳しいされますので、

とNは、2〜800の間の値になります。アルゴリズムを最適化するには？

私がPython言語で私に答えると感謝します。 すべての貢献に感謝します！

Answer 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のボールを1つ追加します。

アルゴリズムが動作することを示すには、実際の値、ボール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) 

Answer 2

あなたが他の どちらかがhttp://probstat.sourceforge.net/を使用して動作することがありGamecatすることにより、独自の機能の答えを使用したい場合は、それは非常に高速である（で書かれましたC）のpython 2.6

Answer 3

で

やitertoolsこれは、Python 2とうまく起動し動作します。6、（2.5-friendly implementation of itertools.permutations is available as well）：

>>> 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)} 

Answer 4

あなたはこのようなあなたが巣を望む、 'forループ' 各サブジェネレータを作成するgenerator再帰的に定義することができます：あなたが呼び出すと

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 = 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))) 

Answer 5

あなたは、単に代わりにリストの、可能性の数を知りたい場合は、次の式が働く：

Possibilities = (N+A-1) C N = (N+A-1)!/(N!x(A-1)!)

ここで、aCb（aはb）は、サイズaのセットからサイズbの組み合わせを選択する方法の数です。

！ 5 * 4 * 3 * 2 * 1、n！= n *（n-1）*（n-2）* ... * 3 * 2 * 1である。私が卵を吸う方法を教えている場合は申し訳ありません。 Pythonで

：Gamecatの例と一致している

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 

。

なぜ数式が動作するのかを説明するために、5つのボールと3つのボックスを見てみましょう。ボールをアスタリスクで表します。ボールを3つの区画に分割するために3-1 = 2の分割線を配置したい。例えば

、我々は

* | * | * * *  (1,1,3) 
* * | * * * |  (2,3,0) 
* * * * * | | (5,0,0) 

7シンボルが7！= 5040個の可能性のある方法で注文することができる可能性があります。すべてのボールが同じなので、ボールの順番を心配していないので、5で割ります！同様に、私たちは分割線の順序を心配していないので、2で割ります。これは、7C5 = 7！/（5！* 2！）= 21の可能性を与える。

Combinationsのウィキペディアの記事には、「組み合わせの繰り返し数」というセクションがあります。この組み合わせの数は、味わい深い言い方で言い換えられます（ドーナツとボールの代わりに果物）。

組み合わせを表示する場合は、数字がどのくらい速く成長するかに注意してください。 20個のボールと9個のボックスには、300万以上の可能性があります！

編集：私の以前の回答は、この問題を整数パーティションに比較して、可能性の数がどれほど急速に増加するかを示しています。私の新しい答えは元の質問にもっと関連しています。

Answer 6

pythonで書かれた例については、3.1のitertools.combinations_with_replacementを参照してください。さらに、コンビナトリアルでは、コンビネーションと交換の問題を、2.6 itertoolsに既に組み込まれている通常のコンビネーション交換なしの問題に変換するのが一般的です。これには、製品または置換に基づくソリューションのように、破棄されたタプルを生成しないという利点があります。あなたの例では（A、N）という標準（n、r）の用語を使った例です。

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)] 

Answer 7

それは上記行ったように、Pythonのジェネレータを使用することは良いアイデアですが、ここ（efficencyわからない）方が簡単であるバージョン：

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 

Answer 8

def iterate_assignments(N, K): 
    buckets = [0] * K 
    buckets[0] = K 
    while True: 
     yield buckets 
     if buckets[-1] == N: 
      return 
     non_empty_buckets = sorted([i for i, count in enumerate(buckets) if count > 0]) 
     if non_empty_buckets[-1] == K - 1: 
      temp = buckets[-1] 
      buckets[-1] = 0 
      buckets[non_empty_buckets[-2] + 1] = temp + 1 
      buckets[non_empty_buckets[-2]] -= 1 
     else: 
      buckets[non_empty_buckets[-1]] -= 1 
      buckets[non_empty_buckets[-1] + 1] += 1 

これは、Pythonでのソリューションですこれは、O（K）メモリおよびO（可能な割り当て）時間で、K個のバケットに対するN個のボールのすべての可能な割り当てを効率的にもたらす。

すべてのボールが一番左のバケットにある割り当てから始めます（理解のため、すべてのバケットが左から右に配置されていることを前提としています）。

（1）一番右のボールが一番右のバケットにある場合は、右から2番目のボールを見つけて両方のボールを移動させてください（2）一番右のボールが他の場所にある場合は、バケットを右に1つ動かします。

このスキームから、なぜこれだけの理由が分かりますか独自の組み合わせを生成します。これがなぜ生じるのかを少し考えてみてくださいすべてユニークな組み合わせ。人々が興味を持っている場合、私は証拠を正式しようとすることができますが、私は今:)