2

我有一个列表，我想从 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) 等等

获得这些组合非常容易。我按照算法从 n 返回 k 元素的所有组合， 它给了我准确的输出。

但是我不能使用此代码，因为我有另一个要求，我将继续从列表中删除元素，以防它们满足某些条件，因此组合的数量将继续减少。所以我不想使用 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 人之后，依此类推

我希望您现在了解用例。

任何人都可以帮助我实施上述用例吗？

4

3 回答 3

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 次迭代的结果（远少于迭代所有可能的组合而不删除），如下所示：

ABC DEF GHI JKO PQU VWY

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

于 2013-01-31T15:19:26.247 回答
0

这是我用 C++ 编写的用于解决类似问题的算法。如果您稍微修改它以在 c# 中工作，您应该能够将其用于您的目的。

void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const unsigned int &testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
    unsigned int n = (startNum - bitVal) << 1;
    n += bitVal ? 1 : 0;

    for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
        cout << (n >> (i - 1) & 1);
    cout << endl;

    if (!(n & testNum) && n != startNum)
        r_nCr(n, bitVal, testNum);

    if (bitVal && bitVal < testNum)
        r_nCr(startNum, bitVal >> 1, testNum);
}

您可以在此处查看其工作原理的说明。

于 2015-02-03T19:58:53.290 回答
0

不确定这是否正是您所需要的，但它可能被视为一种方法。

namespace ConsoleApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Tuple<Expression, Expression>>  conditions = new List<Tuple<Expression, Expression>>();

            // a complex condition, that the current item contains both "B" and "H"
            Expression<Func<IEnumerable<string>, bool>> expression1 = item => item.Contains("B") && item.Contains("H");

            // an expression which is used to exclude the elements from the list
            Expression<Func<string, bool>> expression2 = j => j != "B" && j != "H";

            // associate the condition with the exclusion filter
            var condition = new Tuple<Expression, Expression>(expression1, expression2);

            conditions.Add(condition);

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

            IEnumerable<IEnumerable<string>> result = Process(strArr, conditions);
        }

        private static IEnumerable<IEnumerable<string>> Process(IEnumerable<string> strArr, List<Tuple<Expression, Expression>> conditions)
        {
            List<IEnumerable<string>> response = new List<IEnumerable<string>>();
            int k = 0;
            for (int i = 1; i <= strArr.Count(); i++)
            {
                k++;
                var r = strArr.Combinations(Math.Min(strArr.Count(), k));
                bool stop=false;
                foreach (IEnumerable<string> item in r)
                {
                    if (stop)
                    {
                        break;
                    }
                    foreach (Tuple<Expression, Expression> condition in conditions)
                    {
                        if (Enumerable.Repeat<IEnumerable<string>>(item, 1).Any(Evaluate(condition.Item1) as Func<IEnumerable<string>, bool>))
                        {
                            var initialCount = strArr.Count();
                            strArr = strArr.Where(Evaluate(condition.Item2) as Func<string, bool>);
                            i -= initialCount - strArr.Count();
                            stop = true;
                            break;
                        }
                        else
                        {
                            foreach (var item1 in r)
                            {
                                response.Add(item1);
                            }
                        }
                    }

                }
            }
            return response;
        }

        public static object Evaluate(Expression e)
        {
            if (e.NodeType == ExpressionType.Constant)
                return ((ConstantExpression)e).Value;
            return Expression.Lambda(e).Compile().DynamicInvoke();
        }
    }

    public static class Helper
    {
        public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
        {
            return k == 0 ? new[] { new T[0] } :
              elements.SelectMany((e, i) =>
                elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] { e }).Concat(c))
                );
        }
    }
}

我已将此答案用作帮助者。您还可以看到该Process方法与一组条件（本例中只有一个）松散耦合。

于 2013-01-31T14:37:06.197 回答