Calcular as partições de N

22

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 Nestá 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

DJMcMayhem
fonte
2
Você poderia esclarecer o que quer dizer com alça ?
Dennis
@ flawr Eu discordo - encontrar todas as partições é suficientemente diferente de encontrar partições estritas. No entanto, este pode ser um alvo idiota.
Mego
Eu acho que procurar partições não ordenadas e não limitar o número de partes torna isso diferente o suficiente.
Xnor
Você pode esclarecer o que você quer dizer com buitin ?
Freira vazando

Respostas:

6

Pitão, 10 9 bytes

{SMlMM./U

Nã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:

              input       // initial data
        U     range       // makes a list of length equal to input
      ./      partition   // partitions string
   lMM        length      // length of each substring in each way to partition
 SM           sort        // sort each way to partition
{             deduplicate // removes all duplicate after sorting
              print       // implicit, output final result

Experimente online aqui.

busukxuan
fonte
{mSlMd./*Nsalva um byte #
Leaky Nun
Você pode ir para 7 bytes se você usar lista de particionamento em vez de partição string: pyth.herokuapp.com/?code=sMM.%2Fm1&input=5&debug=0
Maltysen
@LeakyNun Bem, na verdade eu tentei e não salvou um byte. Quando vi seu comentário, descobri que minha resposta era na verdade de 10 bytes, então, na verdade, fiz uma contagem incorreta (esqueci os blocos gedit a partir de 1).
Busukxuan
@ Maltysen Você precisa classificar cada sub-lista e depois desduplicar.
Busukxuan
@ Maltysen Você estava certo, o uso de listas diminui. Tentei adicionar classificação e desduplicação ao código ao qual você vinculou e não ajudou, mas é tudo graças a você que tive a idéia de substituir * N por U. Obrigado!
Busukxuan
6

Pitão, 18 bytes

L?b{SM+R-bsdsyMb]Y

Experimente online! (O yno 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 de 0para b-1e, em seguida, as partições corretas de cada uma.

Por exemplo, quando b=4:

  • b=0[[]]
  • b=1[[1]]
  • b=2[[2], [1, 1]]
  • b=3[[3], [1, 2], [1, 1, 1]]

Em seguida, em cada partição b=0, anexe 4(para fazer a soma 4); para cada partição b=1, acrescente 3(para fazer a soma 4); etc.

É principalmente assim que funciona.

L?b{SM+R-bsdsyMb]Y

L                    define a function called "y" which takes an argument: "b"
 ?b                  test for truthiness of b (in this case, test if b>0).


   {SM+R-bsdsyMb     if truthy:

             yMb         call this function from 0 to b-1.
            s            unpack each list of partitions, generating only partitions.
      +R                 to each partition (d), append:
        -                    the difference of
         b                   b (the argument) and
          sd                 the sum of d (the partition).
    SM                   sort each partition.
   {                     remove duplicates.


                ]Y   if falsey:

                 Y       yield [].
                ]        yield [[]].
Freira Furada
fonte
5

MATL , 20 bytes

:"0Gq:@XNG3$Yc!dS!Xu

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 .

:        % Implicitly input N. Push [1 2 ... N]. These are the possible values of k,
         % except with N instead of 0
"        % For each
  0      %   Push 0
  Gq:    %   Push [1 ... N-1]. These the possible intermediate points
  @XN    %   Push k and produce the combinations. Each k produces a 2D array with
         %   each combination on a row. The value k=N produces an empty array
  G      %   Push N
  3$Yc   %   Prepend a column of zeros and append a column of N to the array
  !d     %   Transpose. Consecutive differences of each column
  S!     %   Sort each column. Transpose
  Xu     %   Keep only unique rows
         % Implicitly end for and display all arrays in the stack
Luis Mendo
fonte
1
Bom, o conceito de pontos de partição é uma maneira muito inteligente de resolver isso.
Nick
@ Nick Obrigado! E seja bem-vindo (ativo) a este site! :-)
Luis Mendo
5

Haskell, 53 bytes

p=[[]]:[map(1:)q++[a+1:b|a:b<-q,all(a<)b]|q<-p]
(p!!)
Anders Kaseorg
fonte
5

J, 49 42 36 35 32 bytes

a:1&([:~.@,(,;}./:~@,(+{.))&>)~]

Está 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,

Partition for n = 1
[[1]]

Partition for n = 2
[[1, 1]] join [[2]]
= [[1, 1], [2]]

Partition for n = 3
[[1, 2], [1, 1, 1]] join [[3], [1, 2]]
= [[3], [1, 2], [1, 1, 1]]

... and so on

Uso

   f =: a:1&([:~.@,(,;}./:~@,(+{.))&>)~]
   f 1
┌─┐
│1│
└─┘
   f 2
┌───┬─┐
│1 1│2│
└───┴─┘
   f 3
┌─────┬───┬─┐
│1 1 1│1 2│3│
└─────┴───┴─┘
   f 5
┌─────────┬───────┬─────┬───┬─────┬───┬─┐
│1 1 1 1 1│1 1 1 2│1 2 2│2 3│1 1 3│1 4│5│
└─────────┴───────┴─────┴───┴─────┴───┴─┘
   # f 15
176

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.

a:1&([:~.@,(,;}./:~@,(+{.))&>)~]  Input: n
a:                                The empty box
                               ]  Get the input n
  1&(                        )~   Repeat n times with an initial array of one empty box
           (              )&>       Operate on each partition
                     (   )            Hook a partition
                       {.               Get its head (the smallest value)
  1                   +                 Add 1 to it
  1           }.                      Drop the first value in each partition
                    ,                 Join the previous two results
                /:~@                  Sort it
  1         ,                         Prepend a 1 to the initial partition
             ;                        Box the last two results and join them
     [:   ,                         Flatten the pairs of boxes
       ~.@                          Remove duplicates and return
                                  Return the final result where each box
                                  is a partition of n
milhas
fonte
4

Python, 65 bytes

Python 3

def f(n,i=1,l=[]):n or print(l);i>n or[f(n-i,i,[i]+l),f(n,i+1,l)]

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

  • Adiciona uma parte do tamanho i e diminui npara n-iou
  • Passa para i+1

Se i>nnão for possível fabricar mais peças, ele pára. E sen cair 0, a partição é bem-sucedida e, portanto, é impressa.

Python 2

f=lambda n,i=1:n/i and[l+[i]for l in f(n-i,i)]+f(n,i+1)or[[]][n:]

Um método recursivo que gera uma lista de partições. Como no código Python 3, ele conta o tamanho da peçai e decide em cada etapa se deve adicionar outra parte do tamanho iou parar.

Ambos fazem n=15quase que instantaneamente.

xnor
fonte
3

Javascript, 194 bytes

p=n=>{var a=[];for(var i=1;i<=n-i;i+=1){for(v of p(n-i)){v.push(i);a.push(v.sort())}}a.push([n]);return a};n=5;s=p(n).map(v=>JSON.stringify(v));s=s.filter((v,i)=>s.indexOf(v)==i);console.log(s);

Não minificado

Encontrar peças únicas classificando e comparando com uma string é um truque, mas provavelmente economiza espaço.

p = n => {
    var a = [];

    for (var i = 1; i <= n-i; i++)
    {
        for (v of p(n-i)) {
            v.push(i);
            a.push(v.sort());
        }
    }

    a.push([n]);

    return a;
}

n = 5;
s = p(n).map(v =>  JSON.stringify(v));
s = s.filter((v,i) => s.indexOf(v) == i);
console.log(s);
usuario
fonte
4
Quite a hack but saves spaceÉ exatamente disso que trata este site. : D
DJMcMayhem
2

Python 3.5, 82 72 bytes

f=lambda n:{(*sorted([*p,i]),)for i in range(1,n)for p in f(n-i)}|{(n,)}

Retorna um conjunto de tuplas. n = 15 termina instantaneamente.

Testá-lo em repl.it .

Dennis
fonte
2

Haskell, 44 bytes

0%m=[[]]
n%m=[j:r|j<-[m..n],r<-(n-j)%j]
(%1)

A função auxiliar n%mfornece as partições de nem partes ≥m, usando a função principal m=1. Ela ramifica cada primeira entrada jcom m≤j≤n, recorrendo na partição restante de n-jem partes que são pelo menos j. O caso base n==0fornece apenas a partição vazia.

xnor
fonte
1

Pitão, 17 bytes

L|{SMs+LVrb0yMb]Y

Define uma função chamada y. Experimente online .

Anders Kaseorg
fonte
1

Geléia , 9 bytes

b1ŒṖḅ1Ṣ€Q

Experimente online!

Como funciona

b1ŒṖḅ1Ṣ€Q  Main link. Argument: n (integer)

b1         Convert n to unary, i.e., a list A of n 1's.
  ŒṖ       Generate all partitions of the list A.
    ḅ1     Convert each flat list from unary to integer.
      Ṣ€   Sort each resulting list.
        Q  Unique; deduplicate the lists.
Dennis
fonte
1

J, 39 bytes

[:~.i.<@\:~@(#;.1~"1 0)1,@{@;(<1 0)#~<:

Este é um verbo monádico que recebe um número inteiro e retorna uma matriz de matrizes em caixa. Experimente aqui. Uso:

   p =: [:~.i.<@\:~@(#;.1~"1 0)1,@{@;(<1 0)#~<:
   p 3
+-----+---+-+
|1 1 1|2 1|3|
+-----+---+-+

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

  • Produzir todas as matrizes de 0-1 n .
  • Para cada um deles, corte um manequimn matriz de ao longo dos 1s e liste os comprimentos de cada parte.
  • Classifique os comprimentos e remova matrizes duplicadas do resultado.

Aparentemente, Luis Mendo teve o mesma idéia .

Explicação do código:

[:~.i.<@\:~@(#;.1~"1 0)1,@{@;(<1 0)#~<:   Input is n.
                                     <:   n-1
                                   #~     copies of
                             (<1 0)       the boxed array [1 0].
                       1    ;             Prepend the boxed array [1].
                          {@              Catalog: produces all combinations of taking one
                                          item from each box, in a high-dimensional matrix.
                        ,@                Flatten the matrix. This results in a list of all
                                          boxed 0-1 arrays of length n that begin with a 1.
    i.                                    The array A =: 0, 1, ..., n-1.
            (     "1 0)                   For each of the boxed arrays B:
              ;.1~                          cut A along the occurrences of 1s in B,
             #                              take the length of each part,
        \:~@                                sort the lengths,
      <@                                    and put the result in a box.
[:~.                                      Remove duplicate boxes.
Zgarb
fonte
Muito bom uso de corte ;.novamente.
milhas
1

Braquilog , 33 bytes (Não concorrente)

:1f:oad.
:1eI,.##lI,.:{.>0}a+?,.=

Isso não é competitivo devido a uma correção de bug.

Isso leva cerca de 1 segundo 15na minha máquina. Por 20mais e mais isso trava com uma Out of global stackexceçã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:

    :1f                       Find the list of all valid outputs of predicate 1
       :oa                    Sort each element of that list
          d.                  Output is that list of sorted lists minus all duplicates
    
  • Predicado 1:

    :1eI                      I is an integer between Input and 1
        .##lI,                Output is a list of length I
              .:{.>0}a        Elements of Output are integers greater than 0
                      +?,     The sum of the elements of Output is Input
                         .=   Assign values to the elements of Output
    
Fatalizar
fonte
1

Mathematica, 62 54 bytes

Inner[#2~Table~#&,FrobeniusSolve[r=Range@#,#],r,Join]&

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

milhas
fonte
... e como isso não é incorporado?
Freira vazando
O @LeakyNun FrobeniusSolvenão encontra partições inteiras, encontra todas as soluções de números inteiros não negativos x1 ... xN para as equações da forma a1 x1 + a2 x2 + ... aN xN = bdada a1 ... aNe b.
milhas
0

JavaScript (Firefox 30-57) 79 ES6, 65 bytes

f=(n,m=1,a=[])=>n?m>n?[]:[...f(n-m,m,[...a,m]),...f(n,m+1,a)]:[a]

Porta da solução Python do @ xnor. (Se ao menos eu percebesse que você poderia recorrer me também n...)

Neil
fonte