通过单个数字总和（没有递归）测序生成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个堆栈深度只生长相对登录<子> 10 ñ。换句话说，你只能得到每位的额外的堆栈帧（仅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)

，其输出（3 2和）

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和awk UNIX下以获得所需的顺序。例如：

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

Answer 2

您可以使用的std :: next_permutation ？

  

在next_permutation（）函数   试图变换给定的范围   元素[开始，结束）到下一个的   字典顺序排列更大   的元素。如果成功，它   返回true，否则，返回   假的。

     

如果一个严格弱排序函数   提供对象的CMP中，它在使用   <操作符的代替比较时   元件。

请参阅此：先前SO回答

Answer 3

如果你用什么方式，只要是有规律并不重要（这不是从你的文章完全清楚，你是否心里有一个特定的模式），则n = 3时，开始111和增量，直到你达到999。

顺便说一句，你在问什么，任期不完全是“置换”。

Answer 4

您可以尽量减少你的问题，以两个水桶：

两种铲斗分裂是简单的：与所有减去一个在桶A和一个在桶乙开始，然后把一个从A到乙直到甲只包含一个

。

三种豆片然后只是：开始在桶A中的每个都减去两个和一个在B和C由一个降低，并收集三个所有二斗分裂在B和C，重复，直到A含有唯一的一个。