números de geração de n dígitos sequenciados pela soma dos dígitos individuais (sem recursão)

Question

Eu estou olhando para gerar todos os valores possíveis de número n dígitos, na seguinte ordem, em que a sequência é ditada pela soma dos dígitos individuais.

Por exemplo, com 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

A ordem dentro do grupo soma não é importante.

Qualquer ajuda, idéias seria apreciada

Answer 1

Você pode sempre transformar um problema recursivo em um um iterativo se você manter a sua própria pilha de dados importantes -. Isso é se a razão para evitar recursão é que a linguagem não apoiá-lo

Mas, se o idioma faz apoiá-lo, em seguida, soluções recursivas são muito mais elegante.

A única outra razão que eu posso pensar para evitar recursão é profundidade da pilha limitado. Nesse caso, uma conversão iterativo de uma solução recursiva irá atenuar o problema por não exigir o máximo de espaço de pilha.

Mas você precisa entender que a profundidade da pilha para processamento de n números só cresce em relação ao log ₁₀ n. Em outras palavras, você só tem um quadro de pilha extra por dígitos (apenas 10 quadros de pilha para lidar com toda a gama de inteiros de 32 bits).

Aparte: pelo tempo que você chegar a esse ponto, você está algoritmo será demorando tanto para ser executado, quadros de pilha será o menor dos seus problemas: -)

Aqui está uma solução Python recursiva:

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)

o qual as saídas (para 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

Tenha em mente que a solução poderia ainda ser otimizado um pouco - Deixei-o na sua forma inicial para mostrar como elegante recursão pode ser. Uma solução pura iterativo segue, mas eu ainda prefiro a um recursiva.

Execute o seguinte programa e uso sort e awk em UNIX para obter a ordem desejada. Por exemplo:

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

Note que isto usa ferramentas externas para fazer a triagem, mas você poderia facilmente tipo dentro do código C (memória permitir).

#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

Você pode usar std :: next_permutation ?

função

O next_permutation () tentativas de transformar a gama dada de elementos [início, fim) para o próximo lexicograficamente maior permutação de elementos. Se ele for bem sucedida, retorna verdadeiro, caso contrário, ele retorna falsa.

Se uma função de ordenação fraca estrita cmp objecto é fornecida, é usado em vez do operador

Veja este:

Answer 3

Se não importa que padrão você usa, desde que há um padrão (não é totalmente clara do seu post se você tem um padrão específico em mente), então para n = 3, comece com 111 e incremento até você alcance 999.

A propósito, o termo para o que você está pedindo não é exatamente "permutações".

Answer 4

Você pode tentar reduzir o problema a dois baldes:

Dois splits balde são simples: Comece com tudo menos um no balde A e um no balde B, em seguida, colocar um de A para B, até A contém apenas um

.

Três divisões de balde são então apenas: Comece com todos menos dois em balde A e uma na B e C. Reduzir Um por um e recolher todos dois splits balde de três em B e C, repita até que A contém apenas um.