我希望按以下顺序生成所有可能的 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
sum 组内的顺序并不重要。
任何帮助,想法将不胜感激
我希望按以下顺序生成所有可能的 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
sum 组内的顺序并不重要。
任何帮助,想法将不胜感激
如果您维护自己的重要数据堆栈,则始终可以将递归问题转变为迭代问题——如果避免递归的原因是语言不支持它的话。
但是,如果语言确实支持它,那么递归解决方案会更加优雅。
我能想到的避免递归的唯一其他原因是堆栈深度有限。在这种情况下,递归解决方案的迭代转换将通过不需要太多堆栈空间来缓解问题。
但是您需要了解处理 n 个数字的堆栈深度仅相对于 log 10 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
请记住,解决方案仍然可以进行一些优化 - 我将其保留为初始形式以展示递归的优雅程度。接下来是纯迭代解决方案,但我仍然更喜欢递归解决方案。
运行以下程序并在 UNIX 下使用sort
andawk
来获得所需的顺序。例如:
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;
}
你可以使用std::next_permutation吗?
next_permutation() 函数尝试将给定的元素范围 [start,end) 转换为下一个字典序上更大的元素排列。如果成功,则返回 true,否则返回 false。
如果提供了严格的弱排序函数对象 cmp,则在比较元素时使用它代替 < 运算符。
看到这个:以前的SO答案
如果你使用什么模式无关紧要,只要有一个模式(从你的帖子中并不完全清楚你是否有一个特定的模式),那么对于 n=3,从开始111
并递增直到你达到999
.
顺便说一句,您所要求的术语并不完全是“排列”。
您可以尝试将问题减少到两个方面:
两个桶拆分很简单:从桶 A 中的所有减一和桶 B 中的一个开始,然后将一个从 A 放入 B 直到 A 只包含一个。
三个桶拆分然后就是:从桶 A 中的所有负二开始,B 和 C 中各一个。将 A 减一并收集 B 和 C 中的所有三个桶拆分的所有两个桶拆分,重复直到 A 只包含一个。