Enumération de combinaisons de N balles dans des boîtes A?

Question

Je veux énumérer toutes les combinaisons possibles de N balles dans A boîtes.

exemple: Je balles pour traiter dans boîtes:

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

Mon premier problème est que j'ai besoin A des boucles pour cela, mais je veulent que A et N être des entrées de l'utilisateur. Alors, comment faire sans écrire tout le nombre possible de boucles dont les utilisateurs pourraient avoir besoin?

un et N aura valeur entre 2 et ~ 800, il sera donc fortement exigeante en temps de calcul ainsi. Comment optimiser cet algorithme?

Je vous serais reconnaissant si vous me répondez en utilisant le langage python. merci pour toutes les contributions!

Answer 1

pseudocode:

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 

Explication

Démarrer à la première case, s'il n'y a pas de boîtes, se plaignent et quitter. S'il s'agit de la dernière case à remplir, laissez tomber toutes les billes restantes et montrez le résultat. S'il y a plus de cases, ajoutez d'abord 0 balles et répétez la procédure avec les autres cases. Ensuite, ajoutez 1, ball 2 balles jusqu'à ce qu'il n'y ait plus de billes.

Pour montrer, que l'algorithme fonctionne, je donne un exemple avec des valeurs réelles, 3 balles et 2 cases.

Nous avons un tableau de boîtes appelé Box, et chaque boîte peut contenir un nombre quelconque de billes (la valeur). PrintBoxes imprime la valeur actuelle des boîtes.

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. 

Un autre exemple avec 3 boîtes et 3 balles:

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

si vous voulez utiliser votre propre réponse de fonction par Gamecat peut travailler autre soit utiliser http://probstat.sourceforge.net/, il est très rapide (écrit en c)

ou itertools en python 2.6

Answer 3

Cela fonctionne très bien en commençant par 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

Vous pouvez définir une generator récursif qui crée un sous-générateur pour chaque « boucle » que vous souhaitez nicher, comme celui-ci:

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

Lorsque vous appelez ceci au niveau supérieur, il faudra seulement un argument 'balles' et 'cases', les autres sont là par défaut pour que l'appel récursif puisse passer des choses différentes. Il produira des tuples d'entiers (de longueur 'boxes') qui sont vos valeurs.

Pour obtenir la mise en forme exacte que vous avez spécifié en haut de ce poste, vous pourriez l'appeler quelque chose comme ceci:

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

Si vous voulez simplement connaître le nombre de possibilités, au lieu de les énumérer, puis la formule suivante fonctionnera:

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

Où aCb (a choisir b) est le nombre de façons de choisir les combinaisons de taille b d'un ensemble de taille a.

! désigne la factorielle soit 5! = 5 * 4 * 3 * 2 * 1, n! = n * (n-1) * (n-2) * ... * 3 * 2 * 1. Désolé si je vous apprends à sucer des oeufs.

En python:

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 

qui est d'accord avec les exemples de Gamecat.

Pour expliquer pourquoi la formule fonctionne, regardons cinq balles et 3 boîtes. Dénoter les balles comme des astérisques. Nous voulons placer 3-1 = 2 lignes de division pour diviser les balles en 3 compartiments.

Par exemple, nous pourrions avoir

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

7 symboles peuvent être commandés à 7! = 5040 façons possibles. Puisque toutes les balles sont les mêmes, nous ne nous inquiétons pas de l'ordre des balles, donc nous divisons par 5! De même, nous ne sommes pas préoccupés par l'ordre des lignes de division, donc nous divisons par 2! Cela nous donne 7C5 = 7!/(5! * 2!) = 21 possibilités.

L'article de Wikipedia sur Combinations a une section "Nombre de combinaisons avec répétition" qui est la question de combinaisons de comptage reformulée d'une manière plus savoureuse (beignets et morceaux de fruits au lieu de boules).

Si vous voulez la liste des combinaisons, méfiez-vous de la rapidité du nombre croît. Pour 20 balles et 9 cases, il y a plus de 3 millions de possibilités!

edit: ma réponse précédente comparait ce problème à des partitions entières pour montrer à quelle vitesse le nombre de possibilités augmente. Ma nouvelle réponse est plus pertinente à la question initiale.

Answer 6

Voir itertools.combinations_with_replacement en 3.1 pour un exemple écrit en python. De plus, il est courant en combinatoire de transformer un problème de combinaison-remplacement en un problème de combinaison-sans-remplacement habituel, déjà intégré dans 2.6 itertools. Ceci a l'avantage de ne pas générer de tuples mis au rebut, comme des solutions basées sur le produit ou la permutation. Voici un exemple utilisant la terminologie standard (n, r), qui serait (A, N) dans votre exemple.

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

Il est recommandé d'utiliser le générateur de python, comme cela a été fait ci-dessus, mais ici est une version plus simple (pas sûr 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 

Ceci est une solution en python qui fournit efficacement toutes les assignations possibles de N balles à K buckets dans la mémoire O (K) et le temps O (# affectations possibles). Commencez par une affectation où toutes les balles se trouvent dans le compartiment le plus à gauche (à des fins de compréhension, supposons que toutes les compartiments sont disposés de gauche à droite). (1) Si la balle la plus à droite se trouve dans le seau le plus à droite, trouvez la prochaine balle la plus à droite et déplacez les deux balles à droite. Déplacez les balles vers la droite de la manière suivante:

(1) dans les godets un à la droite de la prochaine balle la plus à droite (2) Si la balle la plus à droite est ailleurs, déplacez-la d'un seau vers la droite

De ce schéma, il est clair de voir pourquoi cela seulement génère des combinaisons uniques. Il faut un peu plus de réflexion pour voir pourquoi cela produit toutes les combinaisons uniques. Je peux essayer de formaliser une preuve si les gens sont intéressés, mais je saute pour l'instant :)