Bares y estrellas en general.

Tengo el siguiente algoritmo de “barras y estrellas” , implementado en Python, que imprime toda la descomposición de una sum en 3 bandejas, para sums de 0 a 5. Me gustaría generalizar mi código para que funcione. N contenedores (donde N menos que la sum máxima, es decir, 5 aquí). El patrón es que si tiene 3 bins, necesita 2 bucles nesteds, si tiene N bins, necesita bucles nesteds N-1.

¿Puede alguien pensar en una forma genérica de escribir esto, posiblemente sin usar bucles?

# bars and stars algorithm N=5 for n in range(0,N): x=[1]*n for i in range(0,(len(x)+1)): for j in range(i,(len(x)+1)): print sum(x[0:i]), sum(x[i:j]), sum(x[j:len(x)]) 

Related of "Bares y estrellas en general."

Dale un paso a la vez.

Primero, elimine las sum() llamadas. No los necesitamos:

 N=5 for n in range(0,N): x=[1]*n for i in range(0,(n+1)): # len(x) == n for j in range(i,(n+1)): print i, j - i, n - j 

Observe que x es una variable no utilizada:

 N=5 for n in range(0,N): for i in range(0,(n+1)): for j in range(i,(n+1)): print i, j - i, n - j 

Es hora de generalizar. El algoritmo anterior es correcto para N estrellas y tres barras, por lo que solo necesitamos generalizar las barras.

Haga esto recursivamente. Para el caso base, tenemos cero barras o cero estrellas, que son triviales. Para el caso recursivo, ejecute todas las posiciones posibles de la barra situada más a la izquierda y repare en cada caso:

 from __future__ import print_function def bars_and_stars(bars=3, stars=5, _prefix=''): if stars == 0: print(_prefix + ', '.join('0'*(bars+1))) return if bars == 0: print(_prefix + str(stars)) return for i in range(stars+1): bars_and_stars(bars-1, stars-i, '{}{}, '.format(_prefix, i)) 

Para los puntos de bonificación, podríamos cambiar el range() a xrange() , pero eso solo te dará problemas cuando xrange() a Python 3.

Si esto no es simplemente un ejercicio de aprendizaje, entonces no es necesario que desarrolle su propio algoritmo para generar las particiones: la biblioteca estándar de Python ya tiene la mayoría de lo que necesita, en la forma de la función itertools.combinations .

Desde el Teorema 2 en la página de Wikipedia a la que te vinculaste, hay n+k-1 choose k-1 formas de particionar n elementos en k contenedores, y la prueba de ese teorema da una correspondencia explícita entre las combinaciones y las particiones. Entonces, todo lo que necesitamos es (1) una forma de generar esas combinaciones, y (2) código para traducir cada combinación a la partición correspondiente. La función itertools.combinations ya proporciona el primer ingrediente. Para el segundo, cada combinación da las posiciones de los divisores; Las diferencias entre las posiciones de divisor sucesivas (menos una) dan los tamaños de partición. Aquí está el código:

 import itertools def partitions(n, k): for c in itertools.combinations(range(n+k-1), k-1): yield [ba-1 for a, b in zip((-1,)+c, c+(n+k-1,))] # Example usage for p in partitions(5, 3): print(p) 

Y aquí está la salida de ejecutar el código anterior.

 [0, 0, 5] [0, 1, 4] [0, 2, 3] [0, 3, 2] [0, 4, 1] [0, 5, 0] [1, 0, 4] [1, 1, 3] [1, 2, 2] [1, 3, 1] [1, 4, 0] [2, 0, 3] [2, 1, 2] [2, 2, 1] [2, 3, 0] [3, 0, 2] [3, 1, 1] [3, 2, 0] [4, 0, 1] [4, 1, 0] [5, 0, 0] 

Otra variante recursiva, que utiliza una función de generador, es decir, en lugar de imprimir inmediatamente los resultados, los yield uno tras otro, para que los imprima el llamante.

La forma de convertir tus bucles en un algoritmo recursivo es la siguiente:

  • Identifique el “caso base”: cuando no haya más barras, simplemente imprima las estrellas
  • para cualquier número de estrellas en el primer segmento, determine recursivamente las posibles particiones del rest y combínelas

También puede convertir esto en un algoritmo para dividir secuencias arbitrarias en fragmentos:

 def partition(seq, n, min_size=0): if n == 0: yield [seq] else: for i in range(min_size, len(seq) - min_size * n + 1): for res in partition(seq[i:], n-1, min_size): yield [seq[:i]] + res 

Ejemplo de uso:

 for res in partition("*****", 2): print "|".join(res) 

Esto se puede resolver recursivamente en el siguiente enfoque:

 #n bins, k stars, def F(n,k): #n bins, k stars, list holds how many elements in current assignment def aux(n,k,list): if n == 0: #stop clause print list elif n==1: #making sure all stars are distributed list[0] = k aux(0,0,list) else: #"regular" recursion: for i in range(k+1): #the last bin has i stars, set them and recurse list[n-1] = i aux(n-1,ki,list) aux(n,k,[0]*n) 

La idea es “adivinar” cuántas estrellas hay en la última bandeja, asignarlas y responder a un problema menor con menos estrellas (la cantidad que se asignó) y una bandeja menos.


Nota: Es fácil reemplazar la línea.

 print list 

con cualquier formato de salida que desee cuando se establece el número de estrellas en cada contenedor.

Necesitaba resolver el mismo problema y encontré esta publicación, pero realmente quería un algoritmo de propósito general no recursivo que no dependiera de itertools y no pudiera encontrar uno, así que se me ocurrió esto.

De forma predeterminada, el generador produce la secuencia en cualquier orden léxico (como en el ejemplo recursivo anterior), pero también puede producir la secuencia de orden inverso al establecer el indicador “invertido”.

 def StarsAndBars(bins, stars, reversed=False): if bins < 1 or stars < 1: raise ValueError("Number of bins and objects must both be greater than or equal to 1.") if bins == 1: yield stars, return bars = [ ([0] * bins + [ stars ], 1) ] if reversed: while len(bars)>0: b = bars.pop() if b[1] == bins: yield tuple(b[0][y] - b[0][y-1] for y in range(1, bins+1)) else: bar = b[0][:b[1]] for x in range(b[0][b[1]], stars+1): newBar = bar + [ x ] * (bins - b[1]) + [ stars ] bars.append( (newBar, b[1]+1) ) bars = [ ([0] * bins + [ stars ], 1) ] else: while len(bars)>0: newBars = [] for b in bars: for x in range(b[0][-2], stars+1): newBar = b[0][1:bins] + [ x, stars ] if b[1] < bins-1 and x > 0: newBars.append( (newBar, b[1]+1) ) yield tuple(newBar[y] - newBar[y-1] for y in range(1, bins+1)) bars = newBars 

Este problema también se puede resolver de forma algo menos verbal que las respuestas anteriores con una lista de comprensión:

 from numpy import array as ar from itertools import product number_of_stars = M number_of_bins = N decompositions = ar([ar(i) for i in product(range(M+1), repeat=N) if sum(i)==M]) 

Aquí, el itertools.product () produce una lista que contiene el producto cartesiano del rango de la lista (M + 1) consigo mismo, donde el producto se ha aplicado (se repite =) N veces. La instrucción if elimina las combinaciones donde el número no se sum al número de estrellas, por ejemplo, una de las combinaciones es de 0 con 0 con 0 o [0,0,0]. Si estamos contentos con una lista de listas, simplemente podemos eliminar las np.array () (solo ar para brevedad en el ejemplo). Aquí hay un ejemplo de salida para 3 estrellas en 3 contenedores:

 array([[0, 0, 3], [0, 1, 2], [0, 2, 1], [0, 3, 0], [1, 0, 2], [1, 1, 1], [1, 2, 0], [2, 0, 1], [2, 1, 0], [3, 0, 0]]) 

¡Espero que esta respuesta ayude!

Ya que el código en la mayoría de las respuestas me resultó bastante difícil de seguir, es decir, preguntándome a mí mismo cómo se relacionan los algoritmos mostrados con el problema real de las estrellas y las barras, hagámoslo paso a paso:

Primero definimos una función para insertar una barra | en una cadena de stars en una posición dada p :

 def insert_bar(stars, p): head, tail = stars[:p], stars[p:] return head + '|' + tail 

Uso:

 insert_bar('***', 1) # returns '*|**' 

Para insertar múltiples barras en diferentes posiciones, por ejemplo (1,3) una forma simple es usar reduce (desde functools )

 reduce(insert_bar, (1,3), '***') # returns '*|*|*' 

Si ramificamos la definición de insert_bar para manejar ambos casos, obtendremos una función agradable y reutilizable para insertar cualquier cantidad de barras en una cadena de estrellas

 def insert_bars(stars, p): if type(p) is int: head, tail = stars[:p], stars[p:] return head + '|' + tail else: return reduce(insert_bar, p, stars) 

Como @Mark Dickinson explica en su respuesta itertools.combinations nos permite producir n + k-1 elegir k-1 combinaciones de posiciones de barra.

Lo que queda por hacer ahora es crear una cadena de '*' de longitud n , insertar las barras en las posiciones dadas, dividir la cadena en las barras y calcular la longitud de cada bandeja resultante. La implementación a continuación es, literalmente, una traducción literal de la statement del problema en código

 def partitions(n, k): for positions in itertools.combinations(range(n+k-1), k-1): yield [len(bin) for bin in insert_bars(n*"*", positions).split('|')]