El desafío es enumerar todas las particiones ordenadas (composición (combinatoria)) de un entero positivo dado n
. Estas son las listas de números de 1
a n
cuya suma es n
. Por ejemplo, dada la entrada n = 4
, el resultado debería ser:
4
1, 3
3, 1
2, 2
2, 1, 1
1, 2, 1
1, 1, 2
1, 1, 1, 1
El resultado puede estar en cualquier orden, pero debe contener cada partición ordenada una vez. Esto significa que para n = 4
, [1, 1, 2]
, [1, 2, 1]
y [2, 1, 1]
deben ser parte del resultado.
Aquí está mi propio código JavaScript que logra esto:
function range(n) {
for (var range = [], i = 0; i < n; range.push(++i));
return range;
}
function composition(n) {
return n < 1 ? [[]] : range(n).map(function(i) {
return composition(n - i).map(function(j) {
return [i].concat(j);
});
}).reduce(function(a, b) {
return a.concat(b);
});
}
Golfizado, ES6 ( 169 167 119 109 105 89 85 bytes ):
n=>n?[].concat(...[...Array(n)].map((x,i)=>i+1).map(b=>m(n-b).map(a=>[b,...a]))):[[]]
Respuestas:
Pyth,
76 bytesSolución de 7 bytes:
Pyth tiene una partición entera integrada
./
, por lo que 5 de los 7 bytes están recibiendo los pedidos.Pruébalo en línea!
Explicación:
Solución de 6 bytes:
Si tienes una lista,
./
calculará con pedidos; todo lo que queda es hacer que las listas sean números nuevamentePruébalo en línea!
Explicación:
fuente
Haskell, 37 bytes
xnor guardó dos bytes.
fuente
f n=[a:x|a<-[1..n],x<-f$n-a]
es más corto.given positive integer n ... numbers from 1 to n
)f 0=[[]]
resulta ser un caso base más corto quef 1=[[1]]
:)Python, 56 bytes
Una solución recursiva: Las particiones ordenadas de
n
son una partición de algunos más pequeñosi
con0<=i<n
, seguido por el reston-i
como el último elemento. Para un caso base,n=0
solo tiene la partición vacía.fuente
Python 2, 61 bytes
Este no es el más corto, pero realmente me gusta el método porque es muy extraño.
Recursivamente genera y evalúa
2**(n-1)
cadenas, comopara
n=4
. Estas cadenas evalúan las tuplas que representan todas las particiones. Entre cualesquiera dos 1 es o+
, uniéndolos en un solo número, o a,
, dividiendo secciones adyacentes.fuente
import re
lambda n:map(lambda n:map(len,re.finall('10*',bin(n))),range(1<<n-1,1<<n))
JavaScript (Firefox 30-57), 63 bytes
fuente
f=n=>n<2?[[1]]:f(n-1).map(([n,...a])=>r.push([1+n,...a],[1,n,...a]),r=[])&&r
.Mathematica, 40 bytes
La función integrada de Mathematica para particiones enteras no proporciona todas las particiones ordenadas , por lo que debemos generar todas las permutaciones posibles de cada una de ellas y luego aplanar el resultado.
fuente
CJam ,
1714 bytesPruébalo en línea!
Explicación
Sé que dije que usar el producto cartesiano es más largo, pero terminé encontrando una manera de usarlo de manera más eficiente. Creo que ambos enfoques son interesantes por derecho propio, así que los pongo en publicaciones separadas.
Esto todavía se basa en la idea de que podemos elegir
n
tiempos entre agregar a1
a la partición actual o incrementar el último elemento de la partición actual. En esta solución, hacemos esto generando 2 n-1 programas diferentes que corresponden a estas diferentes opciones.fuente
)
". Así que agreguéed
y probé. +1 por abuso creativo de error.Gelatina ,
76 bytes-1 byte gracias a @Dennis (convertir de unario
ḅ1
, en lugar de suma para cada uno para cada unoS€€
)TryItOnline
¿Cómo?
fuente
Pure Bash, 51
Este es un puerto de la brillante respuesta de @ xnor , que utiliza múltiples niveles de expansiones de bash para lograr el resultado deseado:
Ideona
$a
contiene1
seguida den-1
ceros.${a//0/{+,']\ $[}1'}
reemplaza cada0
en$a
las copias de la cadena{+,']\ $[}1'
. Así n = 4 obtenemos la cadena1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1'
$[
y el postfix con],
para dar$[1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1]
$[1+1+1+1], $[1+1+1] 1, $[1+1] $[1+1], $[1+1] 1 1,...
El uso cuidadoso de las comillas, la barra invertida se escapa y
eval
garantiza que las expansiones ocurran en el orden correcto.fuente
Ruby, 61 bytes
sin golf
uso
fuente
x<<i
es más corto que[i]+x
..flatten(1)
no lo es.flatten 1
?Brachylog , 20 bytes
Pruébalo en línea!
Explicación
Esta es una situación en la que pensaría que los lenguajes declarativos funcionarían bien, pero debido a la sobrecarga
+
y la dificultad de escribir un predicado sumador que propague las restricciones correctamente, no lo hacen.fuente
L
esté entre 1 y entrada.+
también funciona en un solo entero, necesito forzar.
a ser una lista##
, y dado que+
también funciona en una lista de listas, necesito imponer que los elementos de.
sean enteros:#$a
.CJam , 19 bytes
Pruébalo en línea!
Explicación
CJam no tiene una combinatoria útil incorporada para particiones enteras. Entonces haremos esto manualmente. Para encontrar todas las particiones ordenadas de un número entero
n
, podemos mirar una lista den
unidades y considerar todas las formas posibles de insertar separadores. Luego sumaremos la1
s en cada sección. Ejemplo paran = 3
:Intenté usar un producto cartesiano para generar todos estos separadores, pero eso terminó en 21 bytes. En cambio, volví a esta vieja técnica para generar conjuntos de potencia (esto se basa en una vieja respuesta de Dennis pero no puedo encontrarla en este momento). La idea es esta: para generar todas las particiones podemos comenzar desde una lista vacía. Luego
n
, podemos tomar una decisión binaria: agregamos a1
(corresponde a un separador en el ejemplo anterior) o incrementamos el último valor de la lista (corresponde a no tener un separador). Para generar todas las particiones, simplemente realizamos ambas operaciones en cada paso y guardamos todas las salidas posibles para el siguiente paso. Resulta que en CJam, anteponer e incrementar el primer elemento es más corto, pero el principio sigue siendo el mismo:fuente
T-SQL, 203 bytes
Golfizado:
Sin golf:
Violín
fuente
Mathematica 10.0, 44 bytes
Un intento sin usar componentes internos relacionados con la partición. De cada partición ordenada de tamaño k , se generan dos particiones sucesoras de k + 1 : una anteponiendo 1 y la otra incrementando el primer valor.
Una forma más divertida, pero lamentablemente 2 bytes más larga de implementar la misma idea:
fuente
MapAt
índice a -1.05AB1E ,
1412 bytesGuardado 2 bytes gracias a Adnan
Explicación
Pruébalo en línea!
La solución correspondiente es 2 bytes más corta en 2sable .
2sable , 10 bytes
Pruébalo en línea!
fuente
—
lugar deiy,
:).Haskell, 41 bytes
No es la solución más corta de Haskell, pero me gusta que no use
[..]
rangos. En cambio, calcula recursivamente las particiones den
como las particionesn-1
con un nuevo 1 al comienzo o el primer valor uno más alto. Esto hace explícito por qué hay2^(n-1)
de ellos.fuente
Mathematica, 53 bytes
No supera la respuesta de Martin Ender, que utiliza la
IntegerPartitions
función incorporada (y las incorporadas están totalmente bien para mí). (Tampoco supera la respuesta de feersum, que no vi hasta demasiado tarde). Pero quería practicar una función recursiva de golf.Genera recursivamente todas las composiciones, generando todos los números finales posibles
j
y luego invocando#-j
dónde#
está la entrada.fuente
Array
lugar deTable
evitarloAppend
usando una lista yApply
:±0={{}};±n_:=Join@@Array[{##,n-+##}&@@@±#&,n,0]
@@
hacer?f@@g[a,b]
evalúa af[a,b]
. Aquí estamos usando el hecho de que una lista como{ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } }
invisiblemente tiene cabezaList
; entoncesJoin@@{ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } }
evalúa aJoin@@List[ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } ]
evalúa aJoin[ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } ]
evalúa a{ {1,1,1}, {2,1}, {1,2}, {3} }
.Retina , 32 bytes
El recuento de bytes supone la codificación ISO 8859-1.
Pruébalo en línea!
Explicación
Esto funciona de manera similar a mi respuesta de CJam . Pasamos por una lista
N
y en cada posición tomamos ambas ramas de la decisión binaria a) incrementamos el último valor ob) iniciamos un nuevo valor en 1.Nivel 1
Convierta la entrada a unario.
Etapa 2
El
+
le dice a Retina que ejecute esta etapa en un bucle hasta que la salida deje de cambiar. El%
le dice que divide la entrada en las líneas antes de aplicar el escenario y unirse a ellos de nuevo juntos después. Al poner el%
después de+
, Retina se divide y vuelve a unirse después de cada iteración. Una iteración de la etapa toma una de esas decisiones que mencioné y, por lo tanto, bifurca el conjunto actual de particiones.Lo que realmente funciona es que coincide con un
1
(pero solo el primero como se indica en la parte1
delantera de la tecla de retroceso), y lo reemplaza con!
(que usaremos como el dígito unario de nuestra salida), seguido del resto de1
s en esta fila (esto incrementa el último valor). Luego, en otra línea (¶
) imprime el prefijo de la línea actual, seguido de,!
, que inserta un separador y luego comienza el siguiente valor en1
.Etapa 3
Esto convierte las ejecuciones de
!
enteros decimales reemplazándolos por su longitud.Etapa 4
Y finalmente, nos damos cuenta de que hemos generado el doble de líneas de las que queríamos, y la mitad de ellas comienzan con una
,
(aquellas en las que inicialmente tomamos la decisión de dividirnos, a pesar de que todavía no había nada para dividir). Por lo tanto, descartamos todas las líneas que comienzan con un,
.fuente
Perl, 44 bytes
Incluye +3 para
-n
(usos de código$'
y,$0
por lo tanto, no se puede ejecutar como-e
línea de comando)Dar número a la partición en STDIN:
partitions.pl
Si no le importa espacios adicionales al final de una línea y una nueva línea adicional, esta solución de 42 bytes también funciona (ejecutar como
perl -M5.010 partitions.pl
):fuente
Julia, 113 bytes
Solución no recursiva.
Explicado:
[vcat([1 for _=i+1:N],sum([1 for _=N-i:N-1])) for i=1:N]
construya un conjunto de listas que sumen N, cuyas permutaciones se parecerán a la solución (por ejemplo, para N = 4: [[1,1,1,1], [1,1,2], [1,3], [4 ]])map(x->[permutations(x)...],)
Calcular todas las permutacionesreduce(vcat,)
combinarlos en una lista de listasunique()
filtrar duplicadosfuente
N
como entrada. Puede hacer una función lambda anteponiendoN->
al costo de 3 bytes.f(N)=
se perdió al copiar, lo tuve al contar bytesMATL , 15 bytes
Pruébalo en línea!
Explicación
Dada la entrada
n
, esto calcula el poder cartesiano con exponentes crecientesk
de1
an
; y para cada exponentek
selecciona las tuplas que tienen una suma igual a la entrada.fuente
Lua
214203182 bytesVersión sin resolver.
Encontró un espacio en blanco perdido y eliminó una variable innecesaria para proteger 11 bytes. Resulta que table.insert () es ineficiente en bytes
fuente
PHP, 125 bytes
-4 bytes para
print_r($r);
lugar deecho json_encode($r);
para la salidauna solución recursiva con 250 bytes
fuente
Prolog, 81 bytes + 6 bytes para llamar
Pruébalo en línea!
Llame con
[4]*L.
, repita con;
hasta que se hayan presentado todas las soluciones.Alternativamente, si presionar repetidamente
;
no está bien (o debe agregarse al conteo de bytes), la llamadabagof(L,[4]*L,M).
agrega 17 bytes para la llamada.fuente
J ,
3026 bytesFunciona dividiendo la lista de n unarios utilizando los valores binarios de 2 n .
Pruébalo en línea!
Explicación
fuente
En realidad,
1716 bytesEsta respuesta se basa parcialmente en la respuesta MATL de Luis Mendo . Sugerencias de golf bienvenidas. Pruébalo en línea!
Ungolfing
fuente
En realidad,
171615 bytesEsta es una bifurcación interesante de la respuesta CJam de Martin Ender (la que tiene el producto cartesiano), con una diferencia en la implementación que me pareció interesante. Cuando una de las cadenas de Martin comienza con un incremento, los errores impiden que se evalúe esa cadena. En En realidad, el error se suprime y la cadena se evalúa de todos modos. Esto termina dando las composiciones de todos
k
en el rango[1..n]
.En lugar de tratar de eliminar las composiciones adicionales, tomé el
n-1
poder cartesiano de"1u"
anexar"1"
al principio de cada cadena. Este truco da solo las composiciones den
. Desafortunadamente, es más largo que la respuesta de Martin.Sugerencias de golf bienvenidas. Pruébalo en línea!
Ungolfing
fuente