Encuentra los conjuntos de sumas

15

He disfrutado leyendo este sitio; Esta es mi primera pregunta. Las ediciones son bienvenidas.

Dados los enteros positivos n y m , calcule todas las particiones ordenadas de m en exactamente n partes enteras positivas, e imprímalas delimitadas por comas y líneas nuevas. Cualquier orden está bien, pero cada partición debe aparecer exactamente una vez.

Por ejemplo, dados m = 6 yn = 2, las posibles particiones son pares de enteros positivos que suman 6:

1,5
2,4
3,3
4,2
5,1

Tenga en cuenta que [1,5] y [5,1] son ​​particiones ordenadas diferentes. La salida debe estar exactamente en el formato anterior, con una nueva línea final opcional. (EDITAR: el orden exacto de las particiones no importa). La entrada / salida se realiza mediante E / S de código de golf estándar .

Otro ejemplo de salida para m = 7, n = 3:

1,1,5
1,2,4
2,1,4
1,3,3
2,2,3
3,1,3
1,4,2
2,3,2
3,2,2
4,1,2
1,5,1
2,4,1
3,3,1
4,2,1
5,1,1

El código más pequeño en bytes después de 1 semana gana.

Nuevamente, edite si es necesario.

Apéndice:

@TimmyD preguntó qué tamaño de entrada de entero tiene que soportar el programa. No hay un mínimo estricto más allá de los ejemplos; de hecho, el tamaño de salida aumenta exponencialmente, modelado aproximadamente por: líneas = e ^ (0.6282 n - 1.8273).

n | m | lines of output
2 | 1 | 1
4 | 2 | 2
6 | 3 | 6
8 | 4 | 20
10 | 5 | 70
12 | 6 | 252
14 | 7 | 924
16 | 8 | 3432
18 | 9 | 12870
20 | 10 | 48620
22 | 11 | 184756
24 | 12 | 705432
cunículo
fuente
¿Las respuestas deben admitir enteros arbitrariamente grandes, o es adecuado un límite superior razonable como 2 ^ 31-1?
AdmBorkBork
44
El término "conjuntos" es confuso porque el orden importa. Creo que el término que estás buscando es particiones ordenadas.
xnor
2
Aunque no es necesario cambiar, generalmente tenemos un formato de salida más flexible que este.
lirtosiast
He cambiado su redacción para permitir E / S a través de argumentos de función, indicaciones y otros métodos de E / S que generalmente consideramos aceptables.
lirtosiast
@TimmyD, el tamaño de la producción crece de forma explosiva en lugar de modo que no es práctico intentar m y n allá de unos pocos cientos, por no hablar de 2 ^ 31-1.
cuniculus

Respuestas:

7

Pyth, 14 bytes

V^SQEIqsNQj\,N

Pruébelo en línea: Demostración o conjunto de pruebas

Explicación:

V^SQEIqsNQj\,N   implicit: Q = first input number
  SQ             create the list [1, 2, ..., Q]
    E            read another number
 ^               cartesian product of the list
                 this creates all tuples of length E using the numbers in SQ
V                for each N in ^:
     IqsNQ          if sum(N) == Q:
          j\,N         join N by "," and print
Jakube
fuente
También 14 bytes, enfoque diferente: jjL\,fqsTQ^SQE.
PurkkaKoodari
6

Python 3, 77 bytes

def f(n,m,s=''):[f(i,m-1,',%d'%(n-i)+s)for i in range(n)];m|n or print(s[1:])

Una función recursiva que construye cada cadena de salida y la imprime. Intenta cada primer número posible, recurriendo hacia abajo para encontrar una solución con la suma disminuida correspondiente n, y un sumando menos m, y un prefijo de cadena scon ese número. Si tanto la suma requerida como el número de términos son iguales a 0, hemos dado en el blanco, por lo que imprimimos el resultado, cortando la coma inicial. Esto se m|nmarca como 0 (Falsey).

79 caracteres en Python 2:

def f(n,m,s=''):
 if m|n==0:print s[1:]
 for i in range(n):f(i,m-1,','+`n-i`+s)
xnor
fuente
4

CJam, 22 bytes

q~:I,:)m*{:+I=},',f*N*

Pruébelo en línea en el intérprete de CJam .

Cómo funciona

q~                      Read and evaluate all input. Pushes n and m.
  :I                    Save m in I.
    ,:)                 Turn it into [1 ... I].
       m*               Push all vectors of {1 ... I}^n.
         {    },        Filter; for each vector:
          :+I=            Check if the sum of its elements equals I.
                        Keep the vector if it does.
                ',f*    Join all vectors, separating by commas.
                    N*  Join the array of vectors, separating by linefeeds.
Dennis
fuente
3

Pyth, 20 18 bytes

-2 bytes por @Dennis!

jjL\,fqQlT{s.pM./E

Esto toma ncomo la primera línea de entrada y mcomo la segunda.

Pruébalo aquí .

lirtosiast
fuente
3

Haskell, 68 bytes

n#m=unlines[init$tail$show x|x<-sequence$replicate n[1..m],sum x==m]

Ejemplo de uso:

*Main> putStr $ 2#6
1,5
2,4
3,3
4,2
5,1

Cómo funciona: sequence $ replicate n listcrea todas las combinaciones de nelementos dibujados de forma list. Tomamos todo lo xde [1..m]donde sumes igual m. unlinesy init$tail$showproducir el formato de salida requerido.

nimi
fuente
3

Dyalog APL , 33 bytes

{↑1↓¨,/',',¨⍕¨↑⍺{⍵/⍨⍺=+/¨⍵},⍳⍵/⍺}

Toma mcomo argumento izquierdo,n como argumento derecho.

Casi la mitad (entre {y ) corresponde al formato requerido.

Adán
fuente
2

Mathematica, 65 bytes

StringRiffle[Permutations/@#~IntegerPartitions~{#2},"
","
",","]&

IntegerPartitionshace la tarea El resto es solo para ordenar las tuplas y formatear el resultado.

LegionMammal978
fuente
2

Pitón 3, 112

from itertools import*
lambda m,n:'\n'.join(','.join(map(str,x))for x in product(range(m),repeat=n)if sum(x)==m)

No he logrado un trazador de líneas 1 en un tiempo. :)

Morgan Thrapp
fuente
1

Python 2.7, 174 170 152 bytes

Respuesta gorda. Al menos es legible :)

import sys,itertools
m=int(sys.argv[1])
for k in itertools.product(range(1,m),repeat=int(sys.argv[2])):
    if sum(k)==m:print str(k)[1:-1].replace(" ","")
Gabriele D'Antona
fuente
Puede eliminar los espacios alrededor >, después replacey después de la coma.
Alex A.
1

Julia, 105 bytes

f(m,n)=for u=∪(reduce(vcat,map(i->collect(permutations(i)),partitions(m,n)))) println("$u"[2:end-1])end

Esta es una función que lee dos argumentos enteros y escribe los resultados en STDOUT con un solo avance de línea final.

Sin golf:

function f(m::Integer, n::Integer)
    # Get the integer partitions of m of length n
    p = partitions(m, n)

    # Construct an array of all permutations
    c = reduce(vcat, map(i -> collect(permutations(i)), p))

    # Loop over the unique elements
    for u in unique(c)
        # Print the array representation with no brackets
        println("$u"[2:end-1])
    end
end
Alex A.
fuente
0

Perl 6 , 54 bytes

Si el resultado podría ser una lista de listas

{[X] (1..$^m)xx$^n .grep: $m==*.sum} # 36 bytes
my &code = {[X] (1..$^m)xx$^n .grep: $m==*.sum}
say .join(',') for code 7,3;

Por la forma en que está redactado actualmente, tengo que agregar un joina la lambda.

{say .join(',')for [X] (1..$^m)xx$^n .grep: $m==*.sum} # 54 bytes
{...}( 7,3 );
1,1,5
1,2,4
1,3,3
1,4,2
1,5,1
2,1,4
2,2,3
2,3,2
2,4,1
3,1,3
3,2,2
3,3,1
4,1,2
4,2,1
5,1,1
Brad Gilbert b2gills
fuente