Generación de números de n dígitos secuenciados por suma de dígitos individuales (sin recursión)

Question

Busco para generar todos los posibles valores de número de n dígitos, en el siguiente orden, donde la secuencia está determinada por la suma de los dígitos individuales.

Por ejemplo, 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

El orden en el grupo suma no es importante.

Cualquier ayuda, idea sería apreciada

Answer 1

Puede siempre convertir un problema recurrente en un proceso iterativo si mantiene su propia pila de datos importantes - que es si la razón para evitar la repetición es que el idioma no lo soporta

Sin embargo, si el idioma hace lo apoyan, a continuación, soluciones recursivas son mucho más elegante.

La única otra razón que se me ocurre para evitar la repetición es limitada profundidad de la pila. En ese caso una conversión iterativo de una solución recursiva mitigará el problema al no requerir tanto espacio de pila.

Sin embargo, es necesario comprender que la profundidad de la pila para el procesamiento de n números sólo crece en relación con log ₁₀ n. En otras palabras, sólo se obtiene una estructura de pila extra por dígitos (sólo 10 marcos de pila de manejar toda la gama de enteros de 32 bits).

Aparte: en el momento en que llegue a ese punto, estás algoritmo va a tomar tanto tiempo para correr, marcos de pila será el menor de sus problemas: -)

Esto es una solución 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)

que da salida (para 2 y 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

Tenga en cuenta que la solución todavía se podría optimizar un poco - lo dejé en su forma inicial para mostrar cómo puede ser elegante recursividad. Una solución pura iterativo sigue, pero yo prefiero el recursiva.

Ejecutar el programa siguiente y use sort y awk bajo UNIX para obtener el orden deseado. Por ejemplo:

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

Tenga en cuenta que este utiliza herramientas externas para realizar la ordenación, pero que podría fácilmente especie dentro del código C (permitiendo la memoria).

#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

¿Se puede utilizar std :: next_permutation ?

  

El next_permutation función ()   los intentos de transformar el rango dado   de elementos [start, end) en la siguiente   lexicográfico mayor de permutación   de elementos. Si tiene éxito,   devuelve true, en caso contrario, devuelve   falsa.

     

Si una estricta función ordenadora débil   se proporciona objeto cmp, se utiliza en   lugar de la

Vea esto: anterior para responder

Answer 3

Si no importa qué patrón se utiliza siempre que hay un patrón (no es del todo clara de su cargo si usted tiene un patrón específico en mente), entonces para n = 3, se inicia con 111 y el incremento hasta que se llegar a 999.

Por cierto, el término para lo que está pidiendo no es exactamente "permutaciones".

Answer 4

Puede intentar reducir el problema a dos cubos:

Dos divisiones de cubo son simples: Comenzar con todos menos uno en el cubo A y uno en el cubo B, a continuación, poner uno de A a B hasta A contiene una sola

.

tres divisiones de cubo están a continuación, sólo: empezar con todos dos menos en cubo de A y uno en B y C. Reducir A por uno y recoger todas las dos divisiones de cubo de tres en B y C, se repiten hasta que A contiene sólo una.