Encontre os conjuntos de somas

15

Eu gostei de ler este site; Esta é a minha primeira pergunta. As edições são bem-vindas.

Dados inteiros positivos n e m , calcule todas as partições ordenadas de m em exatamente n partes partes inteiras positivas e imprima-as delimitadas por vírgulas e novas linhas. Qualquer ordem é boa, mas cada partição deve aparecer exatamente uma vez.

Por exemplo, dado m = 6 en = 2, as partições possíveis são pares de números inteiros positivos que somam 6:

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

Note que [1,5] e [5,1] são partições ordenadas diferentes. A saída deve estar exatamente no formato acima, com uma nova linha à direita opcional. (EDIT: A ordem exata das partições não importa). A entrada / saída é via E / S de código-golfe padrão .

Outro exemplo de saída 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

O menor código em bytes após 1 semana vence.

Novamente, edite se necessário.

Termo aditivo:

O @ TimmyD perguntou qual o tamanho da entrada inteira que o programa suporta. Não há um mínimo rígido além dos exemplos; de fato, o tamanho da saída aumenta exponencialmente, modelado aproximadamente por: lines = 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
cuniculus
fonte
As respostas precisam suportar números inteiros arbitrariamente grandes ou é adequado um limite superior razoável como 2 ^ 31-1?
AdmBorkBork
4
O termo "conjuntos" é confuso porque a ordem é importante. Eu acho que o termo que você está procurando é partições ordenadas.
Xnor
2
Embora não seja necessário alterar, geralmente temos um formato de saída mais flexível que esse.
lirtosiast
Alterei sua redação para permitir E / S por meio de argumentos de função, prompts e outros métodos de E / S que geralmente consideramos aceitáveis.
precisa saber é o seguinte
@TimmyD, o tamanho da saída cresce bastante explosiva para que ele não é prático tentar m e n passado algumas centenas, e muito menos 2 ^ 31-1.
Cuniculus

Respostas:

7

Pitão, 14 bytes

V^SQEIqsNQj\,N

Experimente on-line: Demonstration or Test Suite

Explicação:

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
fonte
Também 14 bytes, abordagem 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:])

Uma função recursiva que cria cada sequência de saída e a imprime. Tenta todos os primeiros números possíveis, recorrendo para baixo para encontrar uma solução com a soma diminuída correspondente ne um summand a menos me um prefixo de seqüência scom esse número. Se a soma necessária e o número de termos forem iguais a 0, atingimos a marca e imprimimos o resultado, cortando a vírgula inicial. Isso é verificado como m|nsendo 0 (Falsey).

79 caracteres no 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
fonte
4

CJam, 22 bytes

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

Experimente on-line no intérprete CJam .

Como 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
fonte
3

Pitão, 20 18 bytes

-2 bytes por @Dennis!

jjL\,fqQlT{s.pM./E

Isso leva ncomo a primeira linha de entrada e mcomo a segunda.

Experimente aqui .

lirtosiast
fonte
3

Haskell, 68 bytes

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

Exemplo de uso:

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

Como funciona: sequence $ replicate n listcria todas as combinações de nelementos desenhados da forma list. Levamos tudo isso xde [1..m]onde os sumiguais m. unlinese init$tail$showproduza o formato de saída necessário.

nimi
fonte
3

Dyalog APL , 33 bytes

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

Toma mcomo argumento à esquerda, ncomo argumento à direita.

Quase metade (entre {e ) é para a formatação necessária.

Adão
fonte
2

Mathematica, 65 bytes

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

IntegerPartitionsfaz a tarefa. O restante é apenas para pedir as tuplas e formatar o resultado.

LegionMammal978
fonte
2

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

Não administro um liner há algum tempo. :)

Morgan Thrapp
fonte
1

Python 2.7, 174 170 152 bytes

Resposta gorda. Pelo menos é legível :)

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
fonte
Você pode remover os espaços ao redor >, depois replacee depois da vírgula.
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

Essa é uma função que lê dois argumentos inteiros e grava os resultados em STDOUT com um único avanço de linha à direita.

Ungolfed:

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

Perl 6 , 54 bytes

Se a saída pudesse ser uma 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;

Do jeito que está escrito, tenho que adicionar um joinno 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
fonte