Generating n-digit numbers sequenced by sum of individual digits (without recursion)

I'm looking to generate all possible values of n-digit number, in the following order, where the 开发者_Python百科sequence is dictated by the sum of the individual digits.

For example, with 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

The order within the sum group is not important.

Any help, ideas would be appreciated

You can always turn a recursive problem into an iterative one if you maintain your own stack of important data - that's if the reason for avoiding recursion is that the language doesn't support it.

But, if the language does support it, then recursive solutions are far more elegant.

The only other reason I can think of for avoiding recursion is limited stack depth. In that case an iterative conversion of a recursive solution will mitigate the problem by not requiring as much stack space.

But you need to understand that the stack depth for processing n numbers only grows relative to log₁₀n. In other words, you only get an extra stack frame per digit (only 10 stack frames to handle the full range of 32-bit integers).

Aside: by the time you get to that point, you're algorithm will be taking so long to run, stack frames will be the least of your problems :-)

Here's a recursive Python solution:

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)

which outputs (for 2 and 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

Keep in mind that solution could still be optimized somewhat - I left it in its initial form to show how elegant recursion can be. A pure-iterative solution follows, but I still prefer the recursive one.

Run the following program and use sort and awk under UNIX to get the desired order. For example:

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

Note that this uses external tools to do the sorting but you could just as easily sort within the C code (memory permitting).

#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;
}

Can you use std::next_permutation?

The next_permutation() function attempts to transform the given range of elements [start,end) into the next lexicographically greater permutation of elements. If it succeeds, it returns true, otherwise, it returns false.

If a strict weak ordering function object cmp is provided, it is used in lieu of the < operator when comparing elements.

See this: previous SO answer

If it doesn't matter what pattern you use so long as there is a pattern (it's not entirely clear from your post whether you have a specific pattern in mind) then for n=3, start with 111 and increment until you reach 999.

By the way, the term for what you're asking for isn't exactly "permutations".

You can try to reduce your problem to two buckets:

Two bucket splits are simple: Start with all minus one in bucket A and one in bucket B, then put one from A into B until A contains only one.

Three bucket splits are then just: Start with all minus two in bucket A and one each in B and C. Reduce A by one and collect all two bucket splits of three in B and C, repeat until A contains only one.