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

Question

I'm looking to generate all possible values of n-digit number, in the following order, where the 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

Answer 1

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

Answer 2

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

Answer 3

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".

Answer 4

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.