c++ - “n”对象上的子集集

Question

可以说我有 2 个元素{a,b}。现在给定一个数字“n”，我希望将所有“n”元素的子集的所有集合添加到所有“n”元素中。({a} and {b})在这里，我们可以得到和的子集({a,b})。在一组三个元素{a,b,c}中，我有所有的子集({a},{b},{c})和({a,b},{c})和({a},{b,c})和({a,c},{b})和({a,b,c})。我如何编写一个程序C++作为函数来获取数字“n”并给我这些子集的所有集合。

Answer 1

我不确定我是否非常了解您的问题，但我认为您正在查看分区。
递归地思考问题。
要对一组 n 个元素进行分区，请运行一个遍历其所有子集的循环。
现在，只需将子集（通过递归找到）补集的分区附加到您当前正在迭代的子集。

Answer 2

你可以做到这一点，使用公式来查找一次取 r 的 n 个事物的组合。

nCr = n! / r! (n-r)!

例如，要找到一组 3 个的所有组合，一次取 2 个东西 (a,b,c) (a,b)，...

C = 3! / 2! (3-2)!
C = 6 / 2(1)
C = 3 distinct combinations are possible for set (a,b,c) in a subset of 2:
(a,b), (a,c), (b,c)

finding all of them
nCr(where n and r = 3) = 1 set (a,b,c)
nCr(n=3, r=1) = 3 = 3 sets (a),(b),(c)
include empty set {}
C = 8

要查找所有可能的集合，您可以使用 for 循环将 r 减为 0。据我记得关于组合/排列的内容，空集合 {} 也被计算在内。

这是在 c++ 函数中的样子（这是相当基本的）

unsigned int factorial(unsigned int i)
{
    unsigned int sum = 0;

    if (i > 1)
    {
        sum = i;
        --i;
        for (i; i > 1; --i)
            sum *= i;
    }// 1! and 0! are 1
    else 
        return 1;


    return sum;
}

unsigned int allsubsets(unsigned int n)
{
    unsigned int C = 0;
    for (int r = n; r > 0; --r)
    {
        C += ( factorial(n) / ( factorial(r) * factorial(n-r) ) );
    }
    ++C; // include the null set
    return C;   
}

int main()
{
    std::cout << "C of 1 is: " << allsubsets(1) << std::endl;
    std::cout << "C of 2 is: " << allsubsets(2) << std::endl;
    std::cout << "C of 3 is: " << allsubsets(3) << std::endl;
    std::cout << "C of 4 is: " << allsubsets(4) << std::endl;
    std::cout << "C of 5 is: " << allsubsets(5) << std::endl;

    return 0;
}

印刷：

C of 1 is: 2
C of 2 is: 4
C of 3 is: 8
C of 4 is: 16
C of 5 is: 32