Liste todas as composições ordenadas de um inteiro

Uma composição ordenada de um inteiro positivo n é uma forma de escrever n como soma de inteiros positivos na qual a ordem das parcelas importa: 1+2 e 2+1 são composições diferentes de 3, e existem sempre exatamente 2 elevado a n menos um composições no total.

O que são composições ordenadas e como diferem de partições

Em teoria dos números e combinatória, uma composição de n é uma sequência ordenada de inteiros positivos cuja soma é n. Ao contrário das partições de inteiros, nas quais só importa o multiconjunto de parcelas e 1+2 é identificado com 2+1, as composições tratam cada ordenação como um objeto distinto. Para todo n de pelo menos um existem exatamente dois elevado a n menos um composições: cada composição corresponde a colocar ou omitir um separador entre unidades consecutivas em uma fila de n uns.

Os livros usam composições quando a ordem codifica sequência, classificação ou alocação em etapas—por exemplo tamanhos sucessivos de bloco em um cronograma, comprimentos de corrida em uma cadeia binária, ou tamanhos de passo ao longo de um caminho que deve cobrir exatamente n unidades. Os estudantes costumam confundir as duas famílias porque ambas respondem “como n pode ser escrito como soma”, mas só as composições se importam com a ordem da esquerda para a direita.

Devolver a lista ordenada completa torna essa distinção concreta: você vê cada rearranjo, e não um representante canônico ordenado, e o campo de contagem deve bater com a fórmula fechada, de modo que você identifica de imediato uma enumeração manual incompleta.

Como a capacidade enumera composições e quando ela recusa

O motor constrói cada composição por expansão recursiva da primeira parcela: para a soma restante r ele tenta cada tamanho de parcela k de um até r, acrescenta k ao prefixo em crescimento e continua até que o resto seja zero, ponto em que a sequência completa é registrada. Esse percurso produz uma ordem estável e determinística—requisições idênticas sempre geram o mesmo vetor de vetores—sem depender de relógio, aleatoriedade ou estado de rede.

A resposta reporta o próprio n, o vetor de composições e a contagem igual ao comprimento desse vetor (que é sempre dois elevado a n menos um para um n válido). Campos n ausentes, não inteiros ou malformados são recusados da mesma forma e nunca são cobrados.

Onde usar a lista e quanto custa

Aplicações típicas incluem verificar respostas de estudantes que listam composições de um dado n, gerar casos de teste exaustivos para funções que aceitam sequências ordenadas de parcelas, explorar identidades combinatórias que contam composições com tamanhos de parcela restritos ao pós-filtrar a lista completa, e documentar opções de encadeamento quando um orçamento de n unidades pode ser dividido em fases ordenadas.

Mantenha n dentro dos limites documentados para que a resposta continue gerenciável; se você só precisa da contagem, ainda pode usar esta ferramenta para n pequeno ou aplicar a fórmula fechada dois elevado a n menos um fora da ferramenta para trabalhos teóricos maiores. O caminho do navegador roda localmente e não exige conta. Trate a contagem devolvida como autoritativa para os vetores listados, em vez de recalcular o comprimento em código cliente que possa divergir deste contrato.