C# 中的部分 Combinations/Permutations - 例如A,B,C = {A,B}, {A,C}, {B,C}

Question

排列有很多 brilliant 实现 - 我在 link 中选择了 Sam 的答案。

我也明白排列和组合之间存在差异，但我不知道如何正确表达。

我需要有关获取所有唯一部分组合的指导，例如

A,B,C = {A,B}, {A,C}, {B,C}
A,B,C,D = {A,B,C},{A,B,D},{B,C,D},{A,C,D},{A,B}, {A,C}, {B,C}

从这里我将把它传递给排列函数，让我全部可用排列，例如{A,B}, {B,A}, {A,C}, {C,A}等

如何获得更大集合的这些（部分）子集？

Answer 1

排列与组合的区别在于排列顺序很重要。

据我了解，您想要所有组合，因此，所有未填充确切集合的组合（您想创建一个子集）

EX:

所以对于 S = {A,B,C,D}，部分组合的一个例子是 {A,C,B}，因为它不关心顺序并且不包含完整的集合（即它是一个S)

的子集

组合公式为N choose K

所以你的集合有 4 个元素 (N)，而你想要一组 3 个或更少的元素 (K)

So N!/K!(N-K)! 
3: = 4!/3!(4-3)! = (1x2x3x4)/(1x2x3)(1) = 4
2: = 4!/2!(2)! = 1x2x3x4/(1x2x1x2) = 6
1: = 4!/1!(4-1)! = 1x2x3x4/1x2x3 = 4

因此答案是14

如果你想要一些关于如何实现组合计算的代码：SOURCE

private static void GetCombination(List<int> list)
{
    double count = Math.Pow(2, list.Count);
    for (int i = 1; i <= count - 1; i++)
    {
        string str = Convert.ToString(i, 2).PadLeft(list.Count, '0');
        for (int j = 0; j < str.Length; j++)
        {
            if (str[j] == '1')
            {
                Console.Write(list[j]);
            }
        }
        Console.WriteLine();
    }
}

Answer 2

递归做起来很容易。您在 GetSubCombinations 函数中遍历虚拟树，始终首先返回没有当前元素的集合，然后返回包含当前元素的集合。在最后一级（GetSubCombinations 函数的第一部分）生成返回的列表，包括最后一个元素或为空。

代码如下：

using System.Collections.Generic;


class Program {
    private static IEnumerable<List<char>> GetSubCombinations(char[] elements, uint startingPos)
    {
        // Leaf condition
        if (startingPos == elements.Length - 1)
        {
            yield return new List<char> {elements[startingPos]};
            yield return new List<char>();
            yield break;
        }

        // node splitting
        foreach (var list in GetSubCombinations(elements, startingPos + 1))
        {
            yield return list;
            list.Add(elements[startingPos]);
            yield return list;
            list.Remove(elements[startingPos]);
        }
    }

    private static IEnumerable<List<char>> GetPartialCombinations(char[] elements)
    {
        foreach (var c in GetSubCombinations(elements, 0))
        {
            // Here you can filter out trivial combinations,
            // e.g. all elements, individual elements and the empty set
            if (c.Count > 1 && c.Count < elements.Length)
                yield return c;
        }
    }


    static void Main(string[] args) {
        char[] elements = new char[] {'A', 'B', 'C'};
        foreach (var combination in GetPartialCombinations(elements))
        {
            foreach (char elem in combination)
                System.Console.Write(elem + ", ");
            System.Console.Write("\n");
        }
        return;
    }

}

C# 中的部分 Combinations/Permutations - 例如A,B,C = {A,B}, {A,C}, {B,C}

Partial Combinations/Permutations in C# - e.g. A,B,C = {A,B}, {A,C}, {B,C}

c#

combinations

permutation