c# - 从 n 中获取 k 元素的所有组合的算法

Question

我有一个列表，我想从 2 的组合开始对列表的元素进行一些操作。

下面是我的列表:

List<string> strArr = new List<string> { "A", "B", "C", "D", "E", "F", "G", "H" };

如果我们一次选择 2 个元素，它将生成以下组合:- (A,B) (A,C) (A,D) (A,E) (A,F) (A,G) (A,H) (B,C) (B,D) 等等

如果我们一次选择 3 个元素，它将生成以下组合:- (A,B,C) (A,B,D) (A,B,E) (A,B,F) (A,B,G) (A,B,H) (A,C,D) ( A,C,E) (A,C,F) (A,C,G) (A,C,H) (A,D,E) (A,D,F) (A,D,G) (A ,D,H) (A,E,F) (A,E,G) (A,E,H) (A,F,G) (A,F,H) (A,G,H) (B, C,D) (B,C,E) (B,C,F) 等等

获得这些组合非常容易。我关注了Algorithm to return all combinations of k elements from n 它给了我准确的输出。

但是我不能使用这段代码，因为我有另一个要求，我将继续从列表中删除元素，以防它们满足特定条件，因此组合的数量将继续减少。所以我不想使用 LINQ 获得所有组合，因为它会影响我的性能。

我想到了以下方式:

List<string> strArr = new List<string> { "A", "B", "C", "D", "E", "F", "G", "H" };
// Loop for selecting combination of two elements at time
for (int i = 0; i < strArr.Count; i++)
{
    for (int j = i + 1; j < strArr.Count; j++)
    {
        // Writing on Console
        // Actually do some operation to check whether these two elements in list needs to be removed or not
        Console.Write(strArr[i] + strArr[j]);
        Console.WriteLine();

        // Check whether current combination of 2 elements need to be removed or not
        if (<< condition >>)
        {
            // Remove both the current elements

            // Remove current element of outer loop
            strArr.RemoveAt(i);
            // Remove current element of inner loop
            // Subtracting one as list size is reduced by 1
            strArr.RemoveAt(j - 1);

            //
            i--;
            break;
        }
    }
}

bool isRemoved = false;
// Loop for selecting combination of three elements at time
for (int i = 0; i < strArr.Count; i++)
{
    for (int j = i + 1; j < strArr.Count; j++)
    {
        for (int k = j + 1; k < s.Count; k++)
        {
            // Writing on Console
            // Actually do some operation to check whether these three elements in list needs to be removed or not
            Console.Write(strArr[i] + strArr[j] + strArr[k]);
            Console.WriteLine();

            // Check whether current combination of 3 elements need to be removed or not
            if (<< condition >>)
            {
                // Remove all the three elements

                // Remove current element of outer loop
                strArr.RemoveAt(i);
                // Remove current element of inner loop
                // Subtracting 1 as list size is reduced by 1
                strArr.RemoveAt(j - 1);
                // Subtracting 2 as list size is reduced by 2
                strArr.RemoveAt(k - 2);
                isRemoved = true;
                i--;
                break;
            }

            // If elements are removed then exit from loop with variable j
            if (isRemoved)
            {
                break;
            }
        }
    }
}

// Now make loop for selecting combination of four elements at time
// and keep removing the elements depending upon condition

删除元素将确保我获得更快的性能，我想执行此操作直到结束。我想不出如何在递归中保持这些深层次的循环。谁能帮我在递归中添加这些无穷无尽的 for 循环？

感谢您花时间为我编写解决方案，但这不是我想要的...我将在没有代码的情况下简要说明需求。

1. 假设我有 10 个元素的列表。
2. 我想选择从 2 组到 9 组的所有组合。如果元素总数为 10，则可能的组合总数将为 1012。
3. 现在我想开始评估 2 组中的所有组合。假设第一组 (A,B)。我将根据某些条件评估这个组，如果该组合满足条件，那么我将从 10 个元素的列表中删除元素 (A,B)。所以我将在列表中留下 8 个元素。
4. 剩余 8 个元素的组合总数现在为 246。我没有尝试组合 (A,C) (A,D) 等等。
5. 但我仍在评估 2 人组中的组合。现在我将选择 2 人组中的剩余组合...下一个组合将是 (C,D) (C,E)..假设所有剩余组合不满足从列表中删除它们的条件。然后我想开始评估 3 人一组的组合。
6. 第一组 3 将是 (C,D,E)... 如果它通过特定条件，那么我将从列表中删除所有 3 个元素，我将只剩下 5 个元素。现在我想对这 5 个元素运行我的 3 组合测试。
7. 在那组 4 人之后等等

我希望您现在了解用例。

谁能帮我实现上述用例？

Answer 1

以下解决方案将迭代输入列表中元素的所有可能组合，从 2 个元素的组合开始并从那里向上移动。如果提供的过滤器函数返回 true，则选择的元素将不予考虑；因此，随着更多元素被删除，迭代总数会减少。不会自动跟踪结果；由调用者根据需要跟踪结果。我要遵循的示例用法将演示如何跟踪结果。

public static void PermutateElements<T>(
    IEnumerable<T> elements,
    Predicate<IEnumerable<T>> filterGroup)
{
    var chooseFrom = new LinkedList<T>(elements);
    var chosen = new List<T>(chooseFrom.Count);
    for (int chooseCount = 2; chooseCount < chooseFrom.Count - 1; chooseCount++)
    {
        Permutate(chooseFrom, chooseCount, filterGroup, chosen, 0);
    }
}

static bool Permutate<T>(LinkedList<T> chooseFrom, int chooseCount,
    Predicate<IEnumerable<T>> filterPermutation, IList<T> chosen, int skipLast)
{
    int loopCount = chooseFrom.Count;
    for (int i = 0; i < loopCount; i++)
    {
        var choosingNode = chooseFrom.First;
        chooseFrom.RemoveFirst();

        bool removeChosen = false;
        if (i < loopCount - skipLast)
        {
            chosen.Add(choosingNode.Value);
            if (chooseCount == 1)
                removeChosen = filterPermutation(chosen);
            else
                removeChosen = Permutate(chooseFrom, chooseCount - 1, filterPermutation, chosen, skipLast + i);
            chosen.RemoveAt(chosen.Count - 1);
        }
        if (!removeChosen)
            chooseFrom.AddLast(choosingNode);
        else if (chosen.Count > 0)
            return true;
    }
    return false;
}

下面的示例使用这些函数来对字母进行分组；我们想将字母 A 到 Z 放入任意组中，这样每组包含的辅音字母多于元音字母，并且至少包含一个元音字母:

HashSet<char> vowels = new HashSet<char>(new char[] { 'A', 'E', 'I', 'O', 'U', 'Y' });
var results = new List<IEnumerable<char>>();
Predicate<IEnumerable<char>> processGroup = delegate(IEnumerable<char> groupElements)
{
    int vowelCount = groupElements.Count(x => vowels.Contains(x));
    int consonantCount = groupElements.Count(x => !vowels.Contains(x));
    if (vowelCount < consonantCount && vowelCount > 0)
    {
        results.Add(new List<char>(groupElements));
        return true;
    }
    else
        return false;
};

var elements = new char[26];
for (int i = 0; i < elements.Length; i++)
    elements[i] = (char)('A' + i);
PermutateElements(elements, processGroup);

执行 3131 次迭代的结果(比迭代所有可能的组合而不删除要少得多)如下:

字母表 DEF GHI JKO PQU 大众汽车

此时所有的元音都用完了，所以不可能有更多的合法组合。