生成通用列表的组合

Question

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

即考虑以下数组

1,2,3,4,5

我需要看起来类似的结果(在这个例子中阈值是3)

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

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

Answer 1

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

• 当我们遍历序列时,我们可以立即返回仅保存当前值的序列.我编写了一个简单的扩展方法来为单个项创建IEnumerable.

• 接下来,我们递归地生成剩余元素的所有组合,阈值减1并将它们中的每一个与当前值组合.

我假设不应该重复元素(即不允许{1,1}或{1,2,1}).如果要允许重复元素,可以删除remaining变量并values在递归调用中替换它GetCombinations.

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

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},输出为:

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