Seu desafio é simples: dado um inteiro N , ouput cada lista de inteiros positivos que os montantes para N . Por exemplo, se a entrada for 5, você deverá enviar
[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 4]
[2, 3]
[5]
Essas listas não precisam ser exibidas em nenhuma ordem específica, nem os números dentro de cada lista. Por exemplo, isso também seria uma saída aceitável para '5':
[1, 1, 1, 2]
[5]
[3, 1, 1]
[2, 1, 2]
[4, 1]
[1, 1, 1, 1, 1]
[2, 3]
Você pode assumir com segurança que a entrada será um número inteiro positivo e pode levar esse número em qualquer formato razoável.
Você não pode usar nenhuma função interna que faça isso.
Se o seu programa falhar ou demorar muito para N grande, tudo bem, mas você deve, no mínimo, produzir a saída correta para os primeiros 15.
As brechas padrão se aplicam e a resposta mais curta em bytes vence!
Teste de E / S
1:
[[1]]
2:
[[1, 1], [2]]
3:
[[1, 1, 1], [1, 2], [3]]
4:
[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]
5:
[[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 4], [2, 3], [5]]
7:
[[1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 3], [1, 1, 1, 2, 2], [1, 1, 1, 4], [1, 1, 2, 3], [1, 1, 5], [1, 2, 2, 2], [1, 2, 4], [1, 3, 3], [1, 6], [2, 2, 3], [2, 5], [3, 4], [7]]
10:
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 6], [1, 1, 1, 2, 2, 3], [1, 1, 1, 2, 5], [1, 1, 1, 3, 4], [1, 1, 1, 7], [1, 1, 2, 2, 2, 2], [1, 1, 2, 2, 4], [1, 1, 2, 3, 3], [1, 1, 2, 6], [1, 1, 3, 5], [1, 1, 4, 4], [1, 1, 8], [1, 2, 2, 2, 3], [1, 2, 2, 5], [1, 2, 3, 4], [1, 2, 7], [1, 3, 3, 3], [1, 3, 6], [1, 4, 5], [1, 9], [2, 2, 2, 2, 2], [2, 2, 2, 4], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5], [2, 4, 4], [2, 8], [3, 3, 4], [3, 7], [4, 6], [5, 5], [10]]
Caso de teste super grande: 15 deve gerar este
[[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, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4], [1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3], [1, 1, 1, 1, 1, 1, 1, 1, 1, 6], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3], [1, 1, 1, 1, 1, 1, 1, 1, 2, 5], [1, 1, 1, 1, 1, 1, 1, 1, 3, 4], [1, 1, 1, 1, 1, 1, 1, 1, 7], [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2], [1, 1, 1, 1, 1, 1, 1, 2, 2, 4], [1, 1, 1, 1, 1, 1, 1, 2, 3, 3], [1, 1, 1, 1, 1, 1, 1, 2, 6], [1, 1, 1, 1, 1, 1, 1, 3, 5], [1, 1, 1, 1, 1, 1, 1, 4, 4], [1, 1, 1, 1, 1, 1, 1, 8], [1, 1, 1, 1, 1, 1, 2, 2, 2, 3], [1, 1, 1, 1, 1, 1, 2, 2, 5], [1, 1, 1, 1, 1, 1, 2, 3, 4], [1, 1, 1, 1, 1, 1, 2, 7], [1, 1, 1, 1, 1, 1, 3, 3, 3], [1, 1, 1, 1, 1, 1, 3, 6], [1, 1, 1, 1, 1, 1, 4, 5], [1, 1, 1, 1, 1, 1, 9], [1, 1, 1, 1, 1, 2, 2, 2, 2, 2], [1, 1, 1, 1, 1, 2, 2, 2, 4], [1, 1, 1, 1, 1, 2, 2, 3, 3], [1, 1, 1, 1, 1, 2, 2, 6], [1, 1, 1, 1, 1, 2, 3, 5], [1, 1, 1, 1, 1, 2, 4, 4], [1, 1, 1, 1, 1, 2, 8], [1, 1, 1, 1, 1, 3, 3, 4], [1, 1, 1, 1, 1, 3, 7], [1, 1, 1, 1, 1, 4, 6], [1, 1, 1, 1, 1, 5, 5], [1, 1, 1, 1, 1, 10], [1, 1, 1, 1, 2, 2, 2, 2, 3], [1, 1, 1, 1, 2, 2, 2, 5], [1, 1, 1, 1, 2, 2, 3, 4], [1, 1, 1, 1, 2, 2, 7], [1, 1, 1, 1, 2, 3, 3, 3], [1, 1, 1, 1, 2, 3, 6], [1, 1, 1, 1, 2, 4, 5], [1, 1, 1, 1, 2, 9], [1, 1, 1, 1, 3, 3, 5], [1, 1, 1, 1, 3, 4, 4], [1, 1, 1, 1, 3, 8], [1, 1, 1, 1, 4, 7], [1, 1, 1, 1, 5, 6], [1, 1, 1, 1, 11], [1, 1, 1, 2, 2, 2, 2, 2, 2], [1, 1, 1, 2, 2, 2, 2, 4], [1, 1, 1, 2, 2, 2, 3, 3], [1, 1, 1, 2, 2, 2, 6], [1, 1, 1, 2, 2, 3, 5], [1, 1, 1, 2, 2, 4, 4], [1, 1, 1, 2, 2, 8], [1, 1, 1, 2, 3, 3, 4], [1, 1, 1, 2, 3, 7], [1, 1, 1, 2, 4, 6], [1, 1, 1, 2, 5, 5], [1, 1, 1, 2, 10], [1, 1, 1, 3, 3, 3, 3], [1, 1, 1, 3, 3, 6], [1, 1, 1, 3, 4, 5], [1, 1, 1, 3, 9], [1, 1, 1, 4, 4, 4], [1, 1, 1, 4, 8], [1, 1, 1, 5, 7], [1, 1, 1, 6, 6], [1, 1, 1, 12], [1, 1, 2, 2, 2, 2, 2, 3], [1, 1, 2, 2, 2, 2, 5], [1, 1, 2, 2, 2, 3, 4], [1, 1, 2, 2, 2, 7], [1, 1, 2, 2, 3, 3, 3], [1, 1, 2, 2, 3, 6], [1, 1, 2, 2, 4, 5], [1, 1, 2, 2, 9], [1, 1, 2, 3, 3, 5], [1, 1, 2, 3, 4, 4], [1, 1, 2, 3, 8], [1, 1, 2, 4, 7], [1, 1, 2, 5, 6], [1, 1, 2, 11], [1, 1, 3, 3, 3, 4], [1, 1, 3, 3, 7], [1, 1, 3, 4, 6], [1, 1, 3, 5, 5], [1, 1, 3, 10], [1, 1, 4, 4, 5], [1, 1, 4, 9], [1, 1, 5, 8], [1, 1, 6, 7], [1, 1, 13], [1, 2, 2, 2, 2, 2, 2, 2], [1, 2, 2, 2, 2, 2, 4], [1, 2, 2, 2, 2, 3, 3], [1, 2, 2, 2, 2, 6], [1, 2, 2, 2, 3, 5], [1, 2, 2, 2, 4, 4], [1, 2, 2, 2, 8], [1, 2, 2, 3, 3, 4], [1, 2, 2, 3, 7], [1, 2, 2, 4, 6], [1, 2, 2, 5, 5], [1, 2, 2, 10], [1, 2, 3, 3, 3, 3], [1, 2, 3, 3, 6], [1, 2, 3, 4, 5], [1, 2, 3, 9], [1, 2, 4, 4, 4], [1, 2, 4, 8], [1, 2, 5, 7], [1, 2, 6, 6], [1, 2, 12], [1, 3, 3, 3, 5], [1, 3, 3, 4, 4], [1, 3, 3, 8], [1, 3, 4, 7], [1, 3, 5, 6], [1, 3, 11], [1, 4, 4, 6], [1, 4, 5, 5], [1, 4, 10], [1, 5, 9], [1, 6, 8], [1, 7, 7], [1, 14], [2, 2, 2, 2, 2, 2, 3], [2, 2, 2, 2, 2, 5], [2, 2, 2, 2, 3, 4], [2, 2, 2, 2, 7], [2, 2, 2, 3, 3, 3], [2, 2, 2, 3, 6], [2, 2, 2, 4, 5], [2, 2, 2, 9], [2, 2, 3, 3, 5], [2, 2, 3, 4, 4], [2, 2, 3, 8], [2, 2, 4, 7], [2, 2, 5, 6], [2, 2, 11], [2, 3, 3, 3, 4], [2, 3, 3, 7], [2, 3, 4, 6], [2, 3, 5, 5], [2, 3, 10], [2, 4, 4, 5], [2, 4, 9], [2, 5, 8], [2, 6, 7], [2, 13], [3, 3, 3, 3, 3], [3, 3, 3, 6], [3, 3, 4, 5], [3, 3, 9], [3, 4, 4, 4], [3, 4, 8], [3, 5, 7], [3, 6, 6], [3, 12], [4, 4, 7], [4, 5, 6], [4, 11], [5, 5, 5], [5, 10], [6, 9], [7, 8], [15]]
Catálogo
O snippet de pilha na parte inferior desta postagem gera o catálogo a partir das respostas a) como uma lista da solução mais curta por idioma eb) como uma tabela geral de líderes.
Para garantir que sua resposta seja exibida, inicie-a com um título, usando o seguinte modelo de remarcação:
## Language Name, N bytes
onde N
está o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:
## Ruby, <s>104</s> <s>101</s> 96 bytes
fonte
Respostas:
Pitão,
109 bytesNão tenho muita certeza se isso não é trapaça, mas as regras apenas diziam que não se pode usar partição inteira (isso não é indicado claramente na pergunta em si, mas um comentário do OP na pergunta diz partição inteira). Estou usando a partição de lista de
strings, que faz fatias da lista que concatenam até a lista "mãe". Acredito que tenho que agradecer ao @ Maltysen pela idéia de usar listas em vez de strings.n = 15 leva menos de um segundo na minha máquina.
No pseudocódigo do fluxo de dados:
Experimente online aqui.
fonte
{mSlMd./*N
salva um byte #Pitão, 18 bytes
Experimente online! (O
y
no final é usado para chamar a função)Isso é bastante rápido.
Isso usa recursão. Se a entrada for
b
, meu método irá gerar as partições de0
parab-1
e, em seguida, as partições corretas de cada uma.Por exemplo, quando
b=4
:b=0
dá[[]]
b=1
dá[[1]]
b=2
dá[[2], [1, 1]]
b=3
dá[[3], [1, 2], [1, 1, 1]]
Em seguida, em cada partição
b=0
, anexe4
(para fazer a soma 4); para cada partiçãob=1
, acrescente3
(para fazer a soma4
); etc.É principalmente assim que funciona.
fonte
MATL , 20 bytes
Experimente online!
Para entrada
15
, leva cerca de 2 segundos no compilador online.Explicação
Isso funciona gerando pontos de partição e depois convertendo em comprimentos de partição . O que quero dizer com isso é o seguinte. Dada a entrada N = 5, uma partição possível é [2 2 1]. Isso é representado pelos pontos de partição [0 2 4 5], de modo que diferenças consecutivas (ou comprimentos) dos pontos de partição forneçam a partição resultante do número de entrada.
Todas as matrizes de pontos de partição começar com 0 e terminam com N . O número k de pontos intermediários varia de 0 a N -1. Para N e k dados, os pontos intermediários podem ser gerados como uma combinação dos números [1, 2, ..., N -1] obtidos k de cada vez.
Várias matrizes de pontos de partição podem gerar o mesmo resultado em uma ordem diferente. Por exemplo, os pontos de partição [0 1 3 5] dariam o comprimento da partição [1 2 2], ou seja, o mesmo que o anterior [2 2 1] somente em uma ordem diferente. Isso deve ser levado em consideração, classificando cada matriz de comprimentos de partição e removendo duplicatas .
fonte
Haskell, 53 bytes
fonte
J,
4942363532 bytesEstá tácito agora!
Cria a partição inteira de n construindo as partições inteiras de 1 a n . Calcula o resultado para n = 15 em um milissegundo.
Começando com a partição inteira inicial
[[1]]
que corresponde a n = 1, construa a próxima partição inteira juntando os resultados de duas operações: anexando um 1 a cada partição; incrementando o menor valor em 1 em cada partição. Obviamente, partições duplicadas serão removidas. Para obter a partição inteira n = 2 em diante,Uso
Explicação
Como J não suporta matrizes irregulares, cada partição deve ser encaixotada para que não sejam preenchidas com zero quando anexadas a outras partições.
fonte
Python, 65 bytes
Python 3
Essa função acumula uma partição e imprime as saídas, ramificando as opções. Ele decide quantos 1s serão colocados na partição, quantos 2s e assim por diante. Para cada valor
i
, éi
e diminuin
paran-i
oui+1
Se
i>n
não for possível fabricar mais peças, ele pára. E sen
cair0
, a partição é bem-sucedida e, portanto, é impressa.Python 2
Um método recursivo que gera uma lista de partições. Como no código Python 3, ele conta o tamanho da peça
i
e decide em cada etapa se deve adicionar outra parte do tamanhoi
ou parar.Ambos fazem
n=15
quase que instantaneamente.fonte
Javascript, 194 bytes
Não minificado
Encontrar peças únicas classificando e comparando com uma string é um truque, mas provavelmente economiza espaço.
fonte
Quite a hack but saves space
É exatamente disso que trata este site. : DPython 3.5,
8272 bytesRetorna um conjunto de tuplas. n = 15 termina instantaneamente.
Testá-lo em repl.it .
fonte
Haskell, 44 bytes
A função auxiliar
n%m
fornece as partições den
em partes≥m
, usando a função principalm=1
. Ela ramifica cada primeira entradaj
comm≤j≤n
, recorrendo na partição restante den-j
em partes que são pelo menosj
. O caso basen==0
fornece apenas a partição vazia.fonte
Pitão, 17 bytes
Define uma função chamada
y
. Experimente online .fonte
Geléia , 9 bytes
Experimente online!
Como funciona
fonte
J, 39 bytes
Este é um verbo monádico que recebe um número inteiro e retorna uma matriz de matrizes em caixa. Experimente aqui. Uso:
Na entrada 15, ele é executado por cerca de um segundo na minha máquina.
Explicação
Esse desafio imediatamente pareceu um trabalho para Catalog (
{
) e Cut (;.
). O esboço do algoritmo é:n
.n
matriz de ao longo dos 1s e liste os comprimentos de cada parte.Aparentemente, Luis Mendo teve o mesma idéia .
Explicação do código:
fonte
;.
novamente.Braquilog , 33 bytes (Não concorrente)
Isso não é competitivo devido a uma correção de bug.
Isso leva cerca de 1 segundo
15
na minha máquina. Por20
mais e mais isso trava com umaOut of global stack
exceção.Explicação
Isso não usa particionamento interno de nenhum tipo e, em vez disso, usa o fato de que
+
funciona nos dois sentidos através da propagação de restrições.Predicado principal:
Predicado 1:
fonte
Mathematica,
6254 bytesAs partições de um número inteiro n podem ser encontradas resolvendo n- pares de números inteiros não negativos ( c 1 , c 2 , ..., c n ) de forma que c 1 + 2 c 2 + ... + n c n = n .
FrobeniusSolve
é capaz de encontrar todas as soluções para essa equação que são usadas para criar tantas cópias de seus respectivos valores, a fim de encontrar todas as partições inteiras de n .fonte
FrobeniusSolve
não encontra partições inteiras, encontra todas as soluções de números inteiros não negativosx1 ... xN
para as equações da formaa1 x1 + a2 x2 + ... aN xN = b
dadaa1 ... aN
eb
.JavaScript
(Firefox 30-57) 79ES6, 65 bytesPorta da solução Python do @ xnor. (Se ao menos eu percebesse que você poderia recorrer
m
e tambémn
...)fonte