¿Enumeración de combinaciones de N bolas en cajas A?

Quiero enumerar todas las combinaciones posibles de N bolas en A cajas.

Ejemplo: Tengo 8 bolas para repartir en 3 cajas:

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

Mi primer problema es que necesito bucles A para realizar esto, pero quiero que A y N sean las entradas del usuario. Entonces, ¿cómo hacer sin escribir todo el número posible de bucles que los usuarios podrían necesitar?

a y N tendrán un valor entre 2 y ~ 800, por lo que será muy exigente en el tiempo de cálculo. ¿Cómo optimizar ese algoritmo?

Te agradecería que me contestaras usando el lenguaje python. ¡Gracias por todas las contribuciones!

    Pseudocódigo

     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 

    Explicación

    Comience en la primera casilla, si no hay casillas, quejarse y renunciar. Si es la última casilla que debe llenarse, suelte todas las bolas restantes y muestre el resultado. Si hay más cuadros, primero agregue 0 bolas y repita el procedimiento con los otros cuadros. Luego agrega 1, bola 2 bolas hasta que no queden bolas.

    Para mostrar que el algoritmo funciona, doy un ejemplo con valores reales, 3 bolas y 2 cajas.

    Tenemos una matriz de cajas llamada Caja, y cada caja puede contener cualquier número de bolas (el valor). PrintBoxes imprime el valor actual de las cajas.

     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. 

    Otro ejemplo con 3 cajas y 3 bolas:

     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) 

    Esto funciona bien comenzando con Python 2.6, (la implementación de itertools.permutations es fácil para 2.5 ) también :

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

    Vea itertools.combinations_with_replacement en 3.1 para ver un ejemplo escrito en python. Además, es común en la combinatoria transformar un problema de combinación con reemplazo en el problema habitual de combinación sin reemplazo, que ya está incorporado en 2.6 itertools. Esto tiene la ventaja de no generar tuplas desechadas, como soluciones basadas en el producto o la permutación. Aquí hay un ejemplo que usa la terminología estándar (n, r), que sería (A, N) en su ejemplo.

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

    Puede definir un generador recursivo que crea un subgenerador para cada ‘for loop’ que desea anidar, como esto:

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

    Cuando llama a esto en el nivel superior, solo tomará un argumento de "bolas" y "casillas", los otros están allí por defecto para que la llamada recursiva pueda pasar cosas diferentes. Producirá tuplas de enteros (de 'cajas' de longitud) que son sus valores.

    Para obtener el formato exacto que especificó en la parte superior de esta publicación, podría llamarlo algo como esto:

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

    Es una buena idea usar el generador Python, como se hizo anteriormente, pero aquí hay una versión más sencilla (no estoy seguro de la eficiencia):

     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 

    Si quiere usar su propia función, la respuesta de Gamecat puede funcionar de otro modo, ya sea que use http://probstat.sourceforge.net/ , es muy rápido (escrito en c)

    o itertools en python 2.6

    Si simplemente desea conocer el número de posibilidades, en lugar de enumerarlas, la siguiente fórmula funcionará:

    Posibilidades = (N + A-1) CN = (N + A-1)! / (N! X (A-1)!)

    Donde aCb (a elegir b) es el número de formas de elegir combinaciones de tamaño b de un conjunto de tamaño a.

    ! denota el factorial, es decir, 5! = 5 * 4 * 3 * 2 * 1, n! = n * (n-1) * (n-2) * … * 3 * 2 * 1. Lo siento si te estoy enseñando a chupar los huevos.

    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 

    Lo que concuerda con los ejemplos de Gamecat.

    Para explicar por qué funciona la fórmula, veamos cinco bolas y 3 cajas. Denota las bolas como asteriscos. Queremos colocar 3-1 = 2 líneas divisorias para dividir las bolas en 3 compartimentos.

    Por ejemplo, podríamos tener

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

    Se pueden ordenar 7 símbolos de 7! = 5040 formas posibles. Dado que todas las bolas son iguales, no nos preocupa el orden de las bolas, por lo que dividimos por 5! De manera similar, no nos preocupa el orden de las líneas divisorias, ¡así que dividimos por 2! Esto nos da 7C5 = 7! / (5! * 2!) = 21 posibilidades.

    El artículo de Wikipedia en Combinaciones tiene una sección “Número de combinaciones con repetición”, que es la pregunta de combinaciones de recuento reformulada de una manera más sabrosa (donas y trozos de fruta en lugar de bolas).

    Si desea enumerar las combinaciones, tenga cuidado con la rapidez con que crece el número. ¡Por 20 bolas y 9 cajas, hay más de 3 millones de posibilidades!

    edición: mi respuesta anterior comparó este problema con particiones enteras para mostrar qué tan rápido crece el número de posibilidades. Mi nueva respuesta es más relevante para la pregunta original.

     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 

    Esta es una solución en Python que proporciona de manera eficiente todas las asignaciones posibles de N bolas a K cubos en la memoria O (K) y el tiempo O (# asignaciones posibles).

    Comience con una tarea en la que todas las bolas estén en el cubo de la izquierda (para los propósitos de la comprensión, suponga que todos los cubos están dispuestos de izquierda a derecha). Genere todas las tareas posteriores moviendo las bolas progresivamente hacia la derecha de la siguiente manera:

    (1) si la bola que está más a la derecha está en el cubo que está más a la derecha, encuentre la siguiente bola que está más a la derecha y mueva estas dos bolas a los grupos uno a la derecha de la siguiente bola que está más a la derecha (2) Si la derecha -La mayoría de las bolas están en cualquier otro lugar, muévelas un cubo hacia la derecha.

    A partir de este esquema, queda claro por qué esto solo genera combinaciones únicas. Se necesita un poco más de reflexión para ver por qué esto produce todas las combinaciones únicas. Puedo intentar formalizar una prueba si la gente está interesada, pero me estoy saltando por ahora 🙂