Listar todas las particiones ordenadas de n

23

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 1a ncuya 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]))):[[]]
driima
fuente
3
Bienvenido al sitio! Debe especificar un criterio ganador. Código de golf tal vez? Además, ¿tiene que estar en ese orden específico? Si es así, ¿cómo se define el orden en general? Creo que el orden lexicográfico sería más significativo; o mejor aún, permita cualquier orden. Es posible que desee utilizar el sandbox para futuros desafíos antes de publicarlos aquí
Luis Mendo,
3
@Fatalize Here [2 1 1] es diferente de [1 2 1], a diferencia de allí. Sospecho que los enfoques pueden ser significativamente diferentes
Luis Mendo
3
Para quienes cerraron como engañados: ¿están seguros de que la diferencia indicada en los comentarios no es relevante? No votaré para reabrir, ya que creo que el martillo también funcionaría en esa dirección
Luis Mendo
3
Sugeriría no aceptar una respuesta todavía (aunque puede cambiarla en cualquier momento) porque ver la pregunta aceptada en la portada puede hacer que la gente piense que se acabó y no participe.
xnor
55
El término habitual para estas particiones ordenadas es " composiciones ".
Greg Martin

Respuestas:

7

Pyth, 7 6 bytes

Solución de 7 bytes:

Pyth tiene una partición entera integrada ./, por lo que 5 de los 7 bytes están recibiendo los pedidos.

{s.pM./

Pruébalo en línea!

Explicación:

     ./  Integer partition (sorted by default)
  .pM    get all the orderings of each of the partitions as a nested list of lists of orderings
 s       Flatten by one layer
{        Remove duplicates

Solución de 6 bytes:

Si tienes una lista, ./ calculará con pedidos; todo lo que queda es hacer que las listas sean números nuevamente

lMM./m

Pruébalo en línea!

Explicación:

     m  Get lists by gathering a list of [0, 1,...input] (I could use U as well)

   ./   Partition with orderings
 MM     Map an operation across each of the orderings lists of elements
l       where that operation is the length of the sublists
Steven H.
fuente
Asombroso. ¡Este es el más pequeño que he visto hasta ahora!
driima
11

Haskell, 37 bytes

f 0=[[]]
f n=[a:x|a<-[1..n],x<-f$n-a]

xnor guardó dos bytes.

Lynn
fuente
1
Parece que cuanto más directo f n=[a:x|a<-[1..n],x<-f$n-a]es más corto.
xnor
no necesita el cheque cero ( given positive integer n ... numbers from 1 to n)
nyro_0
2
f 0=[[]]resulta ser un caso base más corto que f 1=[[1]]:)
Lynn
@xyLe_ Se utiliza un caso base recursivo.
xnor
ah claro, tienes razón, mi mal
nyro_0
10

Python, 56 bytes

f=lambda n:[x+[n-i]for i in range(n)for x in f(i)]or[[]]

Una solución recursiva: Las particiones ordenadas de nson una partición de algunos más pequeños icon 0<=i<n, seguido por el resto n-icomo el último elemento. Para un caso base, n=0solo tiene la partición vacía.

xnor
fuente
Simple, pequeño y aún increíblemente legible. Eso es lo que me encanta de Python.
driima
10

Python 2, 61 bytes

f=lambda n,s='1,':1/n*[eval(s)]or f(n-1,'1+'+s)+f(n-1,'1,'+s)

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

1+1+1+1,
1,1+1+1,
1+1,1+1,
1,1,1+1,
1+1+1,1,
1,1+1,1,
1+1,1,1,
1,1,1,1,

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

xnor
fuente
La mejor versión no recursiva que pude hacer fueimport re lambda n:map(lambda n:map(len,re.finall('10*',bin(n))),range(1<<n-1,1<<n))
Neil
1
Una explicación con el código realmente lo haría hermoso.
noman pouigt
8

JavaScript (Firefox 30-57), 63 bytes

f=n=>n?[for(i of Array(n).keys())for(a of f(i))[n-i,...a]]:[[]]
Neil
fuente
12
Firefox 30+ suena como un navegador especial para los usuarios más maduros de Internet.
Martin Ender
Probablemente no se
acorte
¿De alguna manera esto no se puede eliminar para JavaScript en otros navegadores?
driima
@Eternity que pueda puerto @ otra respuesta de XNOR para usted: f=n=>n<2?[[1]]:f(n-1).map(([n,...a])=>r.push([1+n,...a],[1,n,...a]),r=[])&&r.
Neil
6

Mathematica, 40 bytes

Join@@Permutations/@IntegerPartitions@#&

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.

Martin Ender
fuente
6

CJam , 17 14 bytes

ri"X)"m*{~]p}/

Prué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 ntiempos entre agregar a 1a 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.

ri      e# Read input and convert to integer N.
        e# Decrement.
"X)"m*  e# Get all strings of length N which consist of 'X' and ')'. If
        e# we treat these strings as CJam code then 'X' pushes a 1 and ')'
        e# increments the top of the stack.
        e# Note that some of these strings will begin with an increment that
        e# doesn't have anything on the stack to work with. This will result in
        e# an error and terminate the program. Luckily, the programs are ordered
        e# such that all programs starting with 'X' are first in the list, so
        e# we get to print all the 2^(N-1) permutations before erroring out.
{       e# For each of these programs (well for the first half of them)...
  ~     e#   Evaluate the string as CJam code. This leaves the partition as
        e#   individual integers on the stack.
  ]p    e#   Wrap the stack in a list and pretty-print it.
}/
Martin Ender
fuente
Miré esto y pensé " Eso no puede ser correcto, daría un error cuando evalúa la primera cadena que comienza con) ". Así que agregué edy probé. +1 por abuso creativo de error.
Peter Taylor
6

Gelatina , 7 6 bytes

-1 byte gracias a @Dennis (convertir de unario ḅ1, en lugar de suma para cada uno para cada uno S€€)

1ẋŒṖḅ1

TryItOnline

¿Cómo?

1ẋŒṖḅ1 - Main link: n          e.g. 4
1ẋ     - repeat 1 n times          [1,1,1,1]
  ŒṖ   - partitions of a list     [[[1],[1],[1],[1]], [[1],[1],[1,1]], [[1],[1,1],[1]],
                                   [[1],[1,1,1]],     [[1,1],[1],[1]], [[1,1],[1,1]],
                                   [[1,1,1],[1]],     [[1,1,1,1]]]
    ḅ1 - from base 1 (vectorises)  [[1,1,1,1],        [1,1,2],         [1,2,1],
                                   [1,3],             [2,1,1],         [2,2],
                                   [3,1],             [4]]
Jonathan Allan
fuente
5

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:

a=$[10**($1-1)]
eval echo \$[${a//0/{+,']\ $[}1'}],

Ideona

  • La primera línea es simplemente una expansión aritmética para crear una variable que $acontiene 1seguida den-1 ceros.
  • La primera expansión ${a//0/{+,']\ $[}1'}reemplaza cada 0en $alas copias de la cadena{+,']\ $[}1' . Así n = 4 obtenemos la cadena1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1'
  • Esto tiene el prefijo $[y el postfix con], para dar$[1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1]
  • Esta es una expansión de llaves que se expande a $[1+1+1+1], $[1+1+1] 1, $[1+1] $[1+1], $[1+1] 1 1,...
  • Esto finalmente se expande aritméticamente para dar el resultado requerido.

El uso cuidadoso de las comillas, la barra invertida se escapa y evalgarantiza que las expansiones ocurran en el orden correcto.

Trauma digital
fuente
4

Ruby, 61 bytes

f=->n{n<1?[[]]:(1..n).map{|i|f[n-i].map{|x|x<<i}}.flatten(1)}

sin golf

f=->n{
  n < 1 ?
    [[]]
  :
    (1..n).map { |i|
      f[n-i].map { |x|
        x << i
      }
    }.flatten(1)
}

uso

p f[4]
# => [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]
cia_rana
fuente
2
Hola ¿Podría agregar un poco de explicación para las personas (como yo) que no están familiarizadas con Ruby?
AdmBorkBork
x<<ies más corto que [i]+x.
m-chrzan
@TimmyD Agregué un código no protegido y el uso.
cia_rana
@ m-chrzan ¡Gracias por tu consejo! Yo edité eso.
cia_rana
¿Alguna razón .flatten(1)no lo es .flatten 1?
Cyoce
3

Brachylog , 20 bytes

~lL#++?,L:=f:{:0x}ad

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.

~lL                     L is a list of length Input
  L#+                   L is a list of non-negative integers
  L  +?,                The sum of the elements of L results in the Input
        L:=f            Find all values for the elements of L which satisfy those constraints
            :{:0x}a     Remove all 0s from each sublist of the result of Findall
                   d    Remove all duplicate sublists
Fatalizar
fuente
Creo que esto se propagaría mucho más rápido si te enfocas en números enteros positivos y dejas que la longitud Lesté entre 1 y entrada.
mat
@mat Esto es lo que hice originalmente pero es más largo . Como +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.
Fatalize
Por lo tanto, la cuestión clave es la falta de validez de las estructuras de datos: cuando una variable aparece como argumentos de operaciones que se vectorizan, no se puede saber si la variable representa un solo entero o una lista (posiblemente anidada). Este es un tema difícil, y puede haber una manera elegante de resolverlo, comenzando desde su versión original y buscando construcciones de lenguaje adecuadas que puedan simplificar esto. Buen trabajo en cualquier caso!
mat
3

CJam , 19 bytes

Lari{_1af.+1@f+|}*p

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 de nunidades y considerar todas las formas posibles de insertar separadores. Luego sumaremos la 1s en cada sección. Ejemplo para n = 3:

1 1 1 => 3
1 1|1 => 2|1
1|1 1 => 1|2
1|1|1 => 1|1|1

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 a 1(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:

La       e# Push [[]] onto the stack. The outer list will be the list of
         e# all possible partitions at the current iteration, and we initialise
         e# it to one empty partition (basically all partitions of 0).
ri       e# Read input and convert to integer N.
{        e# Repeat this N times...
  _      e#   Duplicate the list of partitions of i-1.
  1af.+  e#   Increment the first element in each of these. This is done
         e#   by performing a pairwise addition between the partition and [1].
         e#   There is the catch that in the first iteration this will turn
         e#   the empty array into [1], so it's equivalent to the next step.
  1@f+   e#   Pull up the other copy of the list of partitions of i-1 and
         e#   prepend a 1 to each of them.
  |      e#   Set union. This gets rid of the duplicate result from the first
         e#   iteration (in all other iterations this is equivalent to concatenating
         e#   the two lists).
         e#   Voilà, a list of all partitions of i.
}*
p        e# Pretty-print the result.
Martin Ender
fuente
3

T-SQL, 203 bytes

Golfizado:

USE master
DECLARE @ INT=12

;WITH z as( SELECT top(@)cast(number+1as varchar(max))a FROM spt_values WHERE'P'=type),c as(SELECT a*1a,a b FROM z UNION ALL SELECT c.a+z.a,b+','+z.a FROM c,z WHERE c.a+z.a*1<=@)SELECT b FROM c WHERE a=@

Sin golf:

USE master --needed to make sure it is executed from the correct database
DECLARE @ INT=12

;WITH z as
(
  SELECT top(@)cast(number+1as varchar(max))a
  FROM spt_values
  WHERE'P'=type
),c as
(
  SELECT a*1a,a b
  FROM z
  UNION ALL
  SELECT c.a+z.a,b+','+z.a
  FROM c,z
  WHERE c.a+z.a*1<=@
)
SELECT b 
FROM c
WHERE a=@

Violín

t-clausen.dk
fuente
3

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.

Nest[##&[{1,##},{#+1,##2}]&@@@#&,{{1}},#-1]&

Una forma más divertida, pero lamentablemente 2 bytes más larga de implementar la misma idea:

#@{1}&/@Tuples[Prepend[1]@*MapAt[#+1&,1],#-1]&
Feersum
fuente
@alephalpha No, eso no ayudaría ya que entonces tendría que cambiar el MapAtíndice a -1.
feersum
3

05AB1E , 14 12 bytes

Guardado 2 bytes gracias a Adnan

>G¹LNãvyO¹Q—

Explicación

>G              # for N in range(1..input)
  ¹L            # range(1, input)
    Nã          # cartesian product with N (all combinations of length N)
      v         # for each resulting list
       yO¹Q—    # if it's sum equals the input print it

Pruébalo en línea!

La solución correspondiente es 2 bytes más corta en 2sable .

2sable , 10 bytes

>GLNãvyOQ—

Pruébalo en línea!

Emigna
fuente
Puedes usar en lugar de iy,:).
Adnan
@Adnan: ¡Gracias! Olvidé de eso.
Emigna
3

Haskell, 41 bytes

f 1=[[1]]
f n=do a:b<-f$n-1;[1:a:b,a+1:b]

No es la solución más corta de Haskell, pero me gusta que no use [..]rangos. En cambio, calcula recursivamente las particiones de ncomo las particiones n-1con un nuevo 1 al comienzo o el primer valor uno más alto. Esto hace explícito por qué hay 2^(n-1)de ellos.

xnor
fuente
3

Mathematica, 53 bytes

No supera la respuesta de Martin Ender, que utiliza la IntegerPartitionsfunció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.

If[#<1,{{}},Join@@Table[#~Append~j&/@#0[#-j],{j,#}]]&

Genera recursivamente todas las composiciones, generando todos los números finales posibles jy luego invocando #-jdónde #está la entrada.

Greg Martin
fuente
Puede guardar algunos bytes definiendo un operador usando en Arraylugar de Tableevitarlo Appendusando una lista y Apply:±0={{}};±n_:=Join@@Array[{##,n-+##}&@@@±#&,n,0]
Martin Ender
¿Qué @@hacer?
Cyoce
Reemplaza la "cabeza" de una expresión. Por ejemplo, f@@g[a,b]evalúa a f[a,b]. Aquí estamos usando el hecho de que una lista como { { {1,1,1}, {2,1} } , { {1,2} }, { {3} } }invisiblemente tiene cabeza List; entonces Join@@{ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } }evalúa a Join@@List[ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } ]evalúa a Join[ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } ]evalúa a { {1,1,1}, {2,1}, {1,2}, {3} }.
Greg Martin
3

Retina , 32 bytes

El recuento de bytes supone la codificación ISO 8859-1.

.+
$*
+%1`1
!$'¶$`,!
!+
$.&
A`^,

Pruébalo en línea!

Explicación

Esto funciona de manera similar a mi respuesta de CJam . Pasamos por una lista Ny 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

+%1`1
!$'¶$`,!

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 parte 1delantera de la tecla de retroceso), y lo reemplaza con !(que usaremos como el dígito unario de nuestra salida), seguido del resto de 1s 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 en 1.

Etapa 3

!+
$.&

Esto convierte las ejecuciones de !enteros decimales reemplazándolos por su longitud.

Etapa 4

A`^,

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

Martin Ender
fuente
3

Perl, 44 bytes

Incluye +3 para -n(usos de código $'y, $0por lo tanto, no se puede ejecutar como-e línea de comando)

Dar número a la partición en STDIN:

partitions.pl <<< 4

partitions.pl

#!/usr/bin/perl -n
$_=$&-$_.",$_$'",do$0for/\d+/..$&-1;print

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

#!/usr/bin/perl -n
$_=$`-$_." $_ $'",do$0for/\s/..$_-1;say
Ton Hospel
fuente
3

Julia, 113 bytes

f(N)=unique(reduce(vcat,(map(x->[permutations(x)...],[vcat([1 for _=i+1:N],sum([1 for _=N-i:N-1])) for i=1:N]))))

Solución no recursiva.

Explicado:

  1. [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 ]])
  2. map(x->[permutations(x)...],) Calcular todas las permutaciones
  3. reduce(vcat,) combinarlos en una lista de listas
  4. unique() filtrar duplicados
nyro_0
fuente
Requerimos que las presentaciones sean programas o funciones completas, por lo que en este caso tendrá que tomar Ncomo entrada. Puede hacer una función lambda anteponiendo N->al costo de 3 bytes.
Alex A.
@AlexA. ah, lo siento, f(N)=se perdió al copiar, lo tuve al contar bytes
nyro_0
2

MATL , 15 bytes

:"G:@Z^t!XsG=Y)

Pruébalo en línea!

Explicación

Dada la entrada n, esto calcula el poder cartesiano con exponentes crecientes kde 1a n; y para cada exponente kselecciona las tuplas que tienen una suma igual a la entrada.

:       % Take input n implicitly and push range [1 2 ... n]
"       % For each k in that range
  G:    %   Push [1 2 ... n] again
  @     %   Push k
  Z^    %   Cartesian power. Gives 2D array, say A, with each k-tuple in a row.
  t     %   Duplicate
  !     %   Transpose
  Xs    %   Sum of each column. Gives a row vector
  G=    %   True for entries that equal the input
  Y)    %   Use as logical vector into the rows of array A
        % End implicitly
        % Display stack implicitly
Luis Mendo
fuente
1

Lua 214 203 182 bytes

function g(m, l, n,c)for i=1,m do if i+n < m then l[#l+1]=i;g(m,l,n+i,c+1)elseif i+n == m then l[#l+1]=i;print(unpack(l))end end for k=c,#l do l[k]=nil end end g(io.read()*1,{},0,0)

Versión sin resolver.

function g(m, l, n,c)
    for i=1,m do 
        if i+n < m then 
            l[#l+1]=i
            g(m,l,n+i,c+1)
        elseif i+n == m then 
            l[#l+1]=i
            print(unpack(l))
        end 
    end 
    for k=c,#l do 
        l[k]=nil 
    end 
end 
g(io.read()*1,{},0,0)

Encontró un espacio en blanco perdido y eliminó una variable innecesaria para proteger 11 bytes. Resulta que table.insert () es ineficiente en bytes

lenscas
fuente
1

PHP, 125 bytes

for($i=$n=$argv[1];$i<=str_repeat(1,$n);$i++)if(array_sum($a=str_split($i))==$n&!strpos($i,"0"))$r[]=$a;echo json_encode($r);

-4 bytes para print_r($r); lugar deecho json_encode($r); para la salida

una solución recursiva con 250 bytes

function f($n){global$a;foreach($a as$x)foreach(range(1,$n)as$y)$a[]=array_merge((array)$x,[$y]);if(--$n)f($n);}$a=range(1,$w=$argv[1]);f($w-1);foreach($a as$z)if(array_sum((array)$z)==$w)$c[join("-",(array)$z)]=$z;echo json_encode(array_values($c));
Jörg Hülsermann
fuente
1

Prolog, 81 bytes + 6 bytes para llamar

L*L.
[H|T]*L:-H>1,M is H-1,[M,1|T]*L.
[H,K|T]*L:-H>1,M is H-1,N is K+1,[M,N|T]*L.

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 llamada bagof(L,[4]*L,M).agrega 17 bytes para la llamada.

SQB
fuente
1

J , 30 26 bytes

#&1<@(+/;.1)~2#:@(+i.)@^<:

Funciona dividiendo la lista de n unarios utilizando los valores binarios de 2 n .

Pruébalo en línea!

Explicación

#&1<@(+/;.1)~2#:@(+i.)@^<:  Input: n
                        <:  Decrement n
             2         ^    Compute 2^(n-1)
                 (   )@     Operate on that
                   i.         Make the range [0, 1, ..., 2^(n-1)-1]
                  +           Add 2^(n-1) to each in that range
              #:@           Convert each in that range to binary
#&1                         Make n copies of 1 (n in unary)
     (     )~               Operate over each row on RHS and unary n on LHS
        ;.1                   Chop unary n starting at each 1
      +/                        Reduce by addition on each chop
   <@                           Box the sums of each chop
millas
fuente
0

En realidad, 17 16 bytes

Esta respuesta se basa parcialmente en la respuesta MATL de Luis Mendo . Sugerencias de golf bienvenidas. Pruébalo en línea!

;╗R`╜R∙i`M`Σ╜=`░

Ungolfing

         Implicit input n.
;╗       Duplicate n and save a copy of n to register 0.
R        Take the range of [1..n].
`...`M   Map the following function over the range. Variable k.
  ╛R       Push n from register 0 and take the range [1..n] again.
  ∙        Take the k-th Cartesian power of the range.
  i        Flatten that product.
`...`░   Push values of the previous map where the following function returns a truthy value.
          Variable L.
  Σ        Push sum(L).
  ╜        Push n from register 0.
  =        Check if sum(L) == n.
         Implicit return.
Sherlock9
fuente
0

En realidad, 17 16 15 bytes

Esta 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 ken el rango[1..n] .

En lugar de tratar de eliminar las composiciones adicionales, tomé el n-1poder cartesiano de "1u"anexar "1"al principio de cada cadena. Este truco da solo las composiciones de n. Desafortunadamente, es más largo que la respuesta de Martin.

Sugerencias de golf bienvenidas. Pruébalo en línea!

D"1u"∙`1@Σ£ƒk`M

Ungolfing

         Implicit input n.
D        Decrement n.
"1u"∙    Take the (n-1)th Cartesian power of the string "1u".
          In Actually, 1 pushes 1 to the stack and u is increment.
`...`M   Map the following function over the Cartesian power. Variable s.
  1@       Push a 1 to be used later.
  Σ        Summing a list of chars joins the chars into one string.
  £ƒ       Turn s into a function and call it immediately on the 1 in the stack.
  k        Take the whole stack and wrap in a list. This is a composition of n.
         Implicit return.
Sherlock9
fuente