生成数字的所有不同分区 [英] Generating all distinct partitions of a number

问题描述

我正在尝试编写一个 C 代码来生成所有可能的分区(分成 2 个或更多部分)，其中包含给定数量的 distinct 元素.给定分区的所有数字的总和应该等于给定的数字.例如，对于输入 n = 6，所有具有 2 个或更多具有不同元素的元素的可能分区是:

I am trying to write a C code to generate all possible partitions (into 2 or more parts) with distinct elements of a given number. The sum of all the numbers of a given partition should be equal to the given number. For example, for input n = 6, all possible partitions having 2 or more elements with distinct elements are:

• 1、5
• 1、2、3
• 2、4

我认为递归方法应该可行，但我无法处理不同元素的附加约束.非常感谢 C/C++/Java 中的伪代码或示例代码.

I think a recursive approach should work, but I am unable to take care of the added constraint of distinct elements. A pseudo code or a sample code in C/C++/Java would be greatly appreciated.

谢谢！

如果它使事情变得更容易，我可以忽略分区具有至少 2 个元素的限制.这将允许将数字本身添加到列表中(例如，6 本身将是一个微不足道但有效的分区).

If it makes things easier, I can ignore the restriction of the partitions having atleast 2 elements. This will allow the number itself to be added to the list (eg, 6 itself will be a trivial but valid partition).

推荐答案

我草拟了这个不应该产生重复的解决方案(可以美化和优化):

I sketched this solution (it can be beautified and optimized) that shouldn't generate duplicates:

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

这篇关于生成数字的所有不同分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！