Conteggio composizioni intere

Una composizione ordinata di un intero positivo n è una tupla di interi positivi che sommano a n, in cui l'ordine delle parti fa parte dell'identità: 1+3 e 3+1 sono due composizioni distinte di quattro. La combinatoria classica dimostra che il numero di tali somme ordinate è sempre due elevato a n meno uno. Questa capacità accetta un solo intero positivo n e restituisce quel conteggio esatto, insieme alla formula chiusa 2^(n-1), così Lei non deve enumerare ogni tupla, percorrere un albero binario di separatori né rischiare un errore di un'unità nel controllare compiti, casi di gara o identità di funzioni generatrici.

Perché il numero di composizioni ordinate è due alla n meno uno

Scriva n uni in fila. Tra quegli uni si trovano esattamente n meno uno interstizi. Per ciascun interstizio Lei può inserire una barra che spezza la sequenza in una nuova parte, oppure lasciare l'interstizio vuoto così che gli uni adiacenti restino uniti in una parte più grande.

Poiché ciascuno degli n meno uno interstizi ha due scelte indipendenti, il numero totale di schemi è due elevato alla potenza n meno uno. Quell'identità è l'intero algoritmo che questa capacità valuta: non percorre rami di prima parte, non alloca un array di tuple e non campiona. Un controllo di una riga per n uguale a quattro dà otto, in accordo con le otto composizioni (4), (1,3), (3,1), (2,2), (1,1,2), (1,2,1), (2,1,1) e (1,1,1,1).

La forma chiusa è esatta per ogni intero positivo, quindi un compito che afferma nove composizioni di quattro è semplicemente sbagliato, e un generatore che necessita della dimensione della famiglia delle composizioni può dimensionare i buffer da questo conteggio senza mai elencarle. L'ordine è essenziale: se identifica 1+3 con 3+1 ha lasciato le composizioni ed è entrato nel mondo delle partizioni, il cui conteggio p(n) non ha tale formula a potenza di due ed è un intento di ricerca diverso.

Che cosa si invia, che cosa si ottiene e quando la richiesta fallisce

La regola di prodotto è rigorosa: n inferiore a uno è invalido, compreso lo zero e ogni negativo, perché la definizione usuale di composizione richiede un intero positivo da comporre. In caso di successo la risposta ripete l'n normalizzato, restituisce count come stringa decimale del valore esatto 2^(n-1) e include formula come la stringa identità 2^(n-1) affinché i client mostrino il teorema senza codificarlo a mano.

Il conteggio è una stringa di proposito: due alla cinquantatré abbandona già l'intervallo degli interi sicuri di JavaScript, e questa pagina è utile proprio quando n è abbastanza grande da rendere disperato elencare ogni composizione. La convalida fallita non viene addebitata.

Dove ha senso un conteggio di composizioni e come viene tariffato

Usi questo conteggio quando la domanda è quante somme ordinate esistono, non quali siano le tuple. I programmatori di gare confrontano le soluzioni candidate di problemi di conteggio di composizioni con un oracolo deterministico invece di reimplementare una potenza BigInt in ogni harness di linguaggio. I docenti assegnano la dimostrazione degli interstizi e delle barre e hanno bisogno di un controllo automatico che 2^(n-1) sia davvero la dimensione della famiglia prima che gli studenti tentino di elencarla.

I sandbox per colloqui e le dimostrazioni di funzioni generatrici necessitano dello stesso numero ogni volta che chiedono. Il lavoro su dati e compilatori a volte dimensiona uno spazio di ricerca di suddivisioni per fasi ordinate di un budget n e deve conoscere la cardinalità prima di allocare.

Se Le servono davvero tutte le tuple, si fermi qui e usi uno strumento di elenco su un n piccolo; se Le servono composizioni in esattamente k parti, quello è il binomiale C(n-1, k-1) e un'altra pagina; se l'ordine non conta, Lei vuole la funzione di partizione p(n). Mantenga n entro i limiti documentati, tratti la stringa count come l'intero esatto e otterrà un conteggio di composizioni riproducibile senza installare un sistema di algebra computazionale.