生成数字的所有不同分区
我正在尝试编写一个C代码来生成具有给定数字的不同元素的所有可能的分区（分成2个或更多部分）。 给定分区的所有数字的总和应该等于给定的数字。 例如，对于输入n = 6 ，具有2个或更多具有不同元素的元素的所有可能分区是：
- 1,5
- 1,2,3
- 2,4
我认为递归方法应该有效，但我无法处理不同元素的附加约束。 非常感谢C / C ++ / Java中的伪代码或示例代码。
谢谢！
编辑：如果它使事情变得更容易，我可以忽略具有至少2个元素的分区的限制。 这将允许将数字本身添加到列表中（例如，6本身将是一个微不足道但有效的分区）。
我勾画了这个不应该生成重复项的解决方案（它可以被美化和优化）：
void partitions(int target, int curr, int* array, int idx) { if (curr + array[idx] == target) { for (int i=0; i <= idx; i++) cout << array[i] << " "; cout << endl; return; } else if (curr + array[idx] > target) { return; } else { for(int i = array[idx]+1; i < target; i++) { array[idx+1] = i; partitions(target, curr + array[idx], array, idx+1); } } } int main(){ int array[100]; int N = 6; for(int i = 1; i < N; i++) { array[0] = i; partitions(N, 0, array, 0); } }
你想要做的事情对我来说没有多大意义，但这就是我如何接近它。
首先，我创建一个循环，迭代i从1到n – 1.在第一个循环中，你可以添加分区1，i。 然后我将使用i的值递归，以获得也可以添加到1的所有子分区。
然后继续2，依此类推。
首先，编写一个返回所有分区的递归算法，包括那些包含重复的分区。
其次，编写一个算法来消除包含重复元素的分区。
编辑：
通过避免对已经看到过的数字进行递归调用，可以避免重复结果。 伪代码：
Partitions(n, alreadySeen) 1. if n = 0 then return {[]} 2. else then 3. results = {} 4. for i = 1 to n do 5. if i in alreadySeen then continue 6. else then 7. subresults = Partitions(n - i, alreadySeen UNION {i}) 8. for subresult in subresults do 9. results = results UNION {[i] APPEND subresult} 10. return results
编辑：
您还可以避免多次生成相同的结果。 通过修改循环的范围来执行此操作，以便您只以单调递增的方式添加新元素：
Partitions(n, mustBeGreaterThan) 1. if n = 0 then return {[]} 2. else then 3. results = {} 4. for i = (mustBeGreaterThan + 1) to n do 5. subresults = Partitions(n - i, i) 6. for subresult in subresults do 7. results = results UNION {[i] APPEND subresult} 8. return results
你根本不需要递归。 数字列表本质上是一个堆栈，并通过迭代按顺序确保没有重复。
这是一个显示我的意思的版本（你标记了这个C，所以我用C语言编写。在C ++中你可以使用带有push和pop的动态容器，并且大大整理它）。
#include #include void partition(int part) { int *parts; int *ptr; int i; int idx = 0; int tot = 0; int cur = 1; int max = 1; while((max * (max + 1)) / 2 <= part) max++; ptr = parts = malloc(sizeof(int) * max); for(;;) { if((tot += *ptr++ = cur++) < part) continue; if(tot == part) { for(i = 0 ; i < ptr-parts ; i++) {printf("%d ",parts[i]);} printf("\n"); } do { if(ptr == parts) {free(parts); return;} tot -= cur = *--ptr; } while(++cur + tot > part); } } int main(int argc, char* argv[]) { partition(6); return 0; }