Generazione di numeri n cifre in sequenza dalla somma delle singole cifre (senza ricorsione)

Question

Sto cercando di generare tutti i possibili valori di numero n cifre, nel seguente ordine, dove la sequenza è dettata dalla somma delle singole cifre.

Per esempio, con n = 3:

111     sum = 3
112     sum = 4
121
211
122     sum = 5
212
221
113
131
311
114     sum = 6
141
411
:::
999     sum = 27

L'ordine all'interno del gruppo somma non è importante.

Qualsiasi aiuto, le idee sarebbe apprezzato

Answer 1

È possibile sempre trasformare un problema ricorsivo in un iterativo se si mantiene la propria pila di dati importanti - che, se la ragione per evitare la ricorsione è che la lingua non la supporta

Ma, se la lingua non supporta, quindi le soluzioni ricorsive sono molto più elegante.

L'unico altro motivo che posso pensare per evitare ricorsione è limitata profondità dello stack. In tal caso, una conversione iterativa di una soluzione ricorsiva attenui il problema non richiedendo tanto spazio dello stack.

Ma è necessario capire che la profondità dello stack per l'elaborazione n numeri cresce solo rispetto al log ₁₀ n. In altre parole, si ottiene solo uno stack frame in più a cifre (solo 10 stack frame per gestire l'intera gamma di interi a 32 bit).

A parte: per il momento si arriva a quel punto, sei algoritmo prenderà così tanto tempo per correre, stack frame sarà l'ultimo dei vostri problemi: -)

Ecco una soluzione Python ricorsiva:

def recur (numdigits,sum,pref="",prefsum=0):
    if numdigits == 0:
        if prefsum == sum:
            print "%s, sum=%d"%(pref,prefsum)
    else:
        for i in range (1,10):
            recur (numdigits-1,sum,"%s%d"%(pref,i),prefsum+i)

def do (n):
    for i in range (1,n*9+1):
        recur (n,i)

do (2)
do (3)

che fornisce in uscita (per 2 e 3):

11, sum=2          111, sum=3
12, sum=3          112, sum=4
21, sum=3          121, sum=4
13, sum=4          211, sum=4
22, sum=4          113, sum=5
31, sum=4          122, sum=5
14, sum=5          131, sum=5
23, sum=5          212, sum=5
32, sum=5          221, sum=5
41, sum=5          311, sum=5
15, sum=6          114, sum=6
 :    :             :     :
89, sum=17         989, sum=26
98, sum=17         998, sum=26
99, sum=18         999, sum=27

Tenete a mente che la soluzione potrebbe ancora essere ottimizzato un po '- ho lasciato nella sua forma iniziale per mostrare come elegante ricorsione può essere. Una soluzione pura-iterativa segue, ma io continuo a preferire quella ricorsiva.

Eseguire il seguente programma e utilizzare sort e awk sotto UNIX per ottenere l'ordine desiderato. Ad esempio:

go | sort | awk '{print $2}'

Si noti che questo utilizza strumenti esterni a fare la cernita ma si potrebbe altrettanto facilmente sorta all'interno del codice C (memoria permettendo).

#include <stdio.h>

int main (void) {
    int i, sum, carry, size;
    int *pDigit;

    // Choose your desired size.

    size = 2;

    // Allocate and initialise digits.

    if ((pDigit = malloc (size * sizeof (int))) == NULL) {
        fprintf (stderr, "No memory\n");
        return 1;
    )

    for (i = 0; i < size; i++)
        pDigit[i] = 1;

    // Loop until overflow.

    carry = 0;
    while (carry != 1) {
        // Work out sum, then output it with number.
        // Line is sssssssssssssssssss ddddd
        //   where sss...sss is the fixed-width sum, zero padded on left (for sort)
        //   and ddd...ddd is the actual number.

        sum = 0;
        for (i = 0; i < size; i++)
            sum += pDigit[i];

        printf ("%020d ", sum);
        for (i = 0; i < size; i++)
            printf ("%d", pDigit[i]);
        printf ("\n");

        // Advance to next number.

        carry = 1;
        for (i = 0; i < size; i++) {
            pDigit[size-i-1] = pDigit[size-i-1] + carry;
            if (pDigit[size-i-1] == 10)
                pDigit[size-i-1] = 1;
            else
                carry = 0;
        }
    }

    return 0;
}

Answer 2

Si può utilizzare std :: next_permutation ?

  

La next_permutation function ()   i tentativi di trasformare l'intervallo dato   di elementi [inizio, fine) nella prossima   lexicographically maggiore permutazione   di elementi. Se ci riesce, è   restituisce true, in caso contrario, restituisce   falso.

     

Se una rigorosa funzione di ordinamento debole   oggetto cmp è fornito, è utilizzato in   sostituzione del

Vedere questo: precedente SO rispondere

Answer 3

Se non importa quale schema si utilizza fino a quando v'è un modello (non è del tutto chiaro dal tuo post se si dispone di un modello specifico in mente), allora per n = 3, iniziare con 111 e l'incremento fino a quando non raggiungere 999.

A proposito, il termine per quello che stai chiedendo non è esattamente "permutazioni".

Answer 4

Si può cercare di ridurre il problema a due secchi:

Due spaccature benna sono semplici: Iniziare con tutti meno uno nel secchio A e uno in secchio B, poi mettere uno da A in B fino a quando A contiene un solo

.

Tre divisioni benna sono poi basta: iniziare con tutti meno due nel secchio A e uno ciascuno in B e C. ridurre una per una e raccogliere tutte le due divisioni benna di tre in B e C, ripetere fino a quando A contiene una sola.