生成由个别数字之和排序的n位数字(无递归)

Question

我希望按以下顺序生成所有可能的n位数值,其中序列由各个数字的总和决定.

例如,用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

总和组中的顺序并不重要.

任何帮助,想法将不胜感激

Answer 1

您可以随时关闭递归问题变成一个迭代,如果您维护自己的重要数据栈-这就是,如果为了避免递归的原因是语言不支持它.

但是,如果语言确实支持它,那么递归解决方案就更优雅了.

我能想到避免递归的另一个原因是有限的堆栈深度.在这种情况下,递归解决方案的迭代转换将通过不需要尽可能多的堆栈空间来缓解该问题.

但是您需要了解处理n个数字的堆栈深度仅相对于log ₁₀ n 增长.换句话说,每个数字只能获得一个额外的堆栈帧(只有10个堆栈帧来处理全部32位整数).

旁白:当你到达那一点时,你的算法将花费这么长的时间来运行,堆栈帧将是你的问题中最少的:-)

这是一个递归的Python解决方案:

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)

哪个输出(2和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

请记住,解决方案仍然可以进行一些优化 - 我将其保留为初始形式,以显示优雅的递归.接下来是一个纯迭代的解决方案,但我仍然更喜欢递归的解决方案.

运行下面的程序,并使用sort和awkUNIX下获得所需的顺序.例如:

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

请注意,这使用外部工具进行排序,但您可以在C代码中轻松排序(内存允许).

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