生成通用列表的组合 [英] Generate Combinations of generic list

问题描述

我需要从另一个包含所有可能组合的列表中创建一个列表.在研究可能的解决方案时，我发现了许多有趣的方法，但是所有方法似乎都基于提供的记录数来产生结果.我需要组合才能增加到最大阈值.

I need to create a list from another list that contains every combination possible. In researching possible solutions I have found many interesting approaches but all seem to generate results based on the count of records provided. I need the combinations to increase to a max threshold.

即考虑以下数组

1,2,3,4,5

1,2,3,4,5

我需要结果看起来类似于(在此示例中，阈值为3)

I need the results to look similar to (threshold is 3 in this example)

1
1,2
1,2,3
1,2,4
1,2,5
1,3,4
2,3,5... etc

实际上，数据将是IEnumerable.我用一个简单的int []来说明所需的结果.

In actuality, the data will be IEnumerable. I used a simple int[] to illustrate the desired results.

推荐答案

我的解决方案使用简单的递归算法来创建组合:

My solution uses a simple recursive algorithm to create the combinations:

• 当我们遍历序列时，我们可以立即返回仅包含当前值的序列.我已经编写了一种简单的扩展方法来为单个项目创建IEnumerable.

• When we walk through the sequence we can immediately return a sequence that only holds the current value. I have written a simple extension method to create an IEnumerable for a single item.

接下来，我们递归地为阈值减小1的其余元素生成所有组合，并将每个组合与当前值组合.

Next we recursively generate all combinations for the remaining elements with the threshold reduced by 1 and combine each of them with the current value.

我假定不应重复元素(即，不允许使用{1，1}或{1，2，1}).如果要允许重复的元素，则可以删除remaining变量，并在对GetCombinations的递归调用中将其替换为values.

I assume that elements should not be repeated (i.e. { 1, 1 } or { 1, 2, 1 } are not allowed). If you want to allow repeated elements you can remove the remaining variable and replace it with values in the recursive call to GetCombinations.

请注意使用 yield 关键字.这意味着代码使用延迟执行.在实际枚举结果之前，无需存储任何中间结果.

Please note the use of the yield keyword. This means that the code uses deferred execution. There is no need to store any intermediate results before you actually enumerate the result.

public static IEnumerable<IEnumerable<T>> GetCombinations<T>(IEnumerable<T> values, int threshold)
{
    var remaining = values;

    foreach (T value in values)
    {
        yield return value.Yield();

        if (threshold < 2)
        {
            continue;
        }

        remaining = remaining.Skip(1);

        foreach (var combination in GetCombinations(remaining, threshold - 1))
        {
            yield return value.Yield().Concat(combination);
        }
    }
}

public static IEnumerable<T> Yield<T>(this T item)
{
    yield return item;
}

对于整数数组{1，2，3，4，5}，输出为:

For the integer array { 1, 2, 3, 4, 5 } the output is:

1
1, 2
1, 2, 3
1, 2, 4
1, 2, 5
1, 3
1, 3, 4
1, 3, 5
1, 4
1, 4, 5
1, 5
2
2, 3
2, 3, 4
2, 3, 5
2, 4
2, 4, 5
2, 5
3
3, 4
3, 4, 5
3, 5
4
4, 5
5

这篇关于生成通用列表的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！