如何使用LINQ从一组数字中查找n个项目的所有组合？

Question

我正在尝试编写一种算法来从一组数字中选择n个值的所有组合.

例如,给定集合: 1, 2, 3, 7, 8, 9

该组中2个值的所有组合为:

(1,2),(1,3),(1,7),(1,8),(1,9),(2,3),(2,7),(2,8),(2) ,9),(3,7),(3,8),(3,9),(7,8),(7,9),(8,9)

3是:

(1,2,3),(1,2,7),(1,2,8),(1,2,9),(1,3,7),(1,3,8),(1) ,3,9),(1,7,8),(1,7,9),(1,8,9),(2,3,7),(2,3,8),(2,3) ,9),(2,7,8),(2,7,9),(2,8,9),(3,7,8),(3,7,9),(3,8,9) ),(7,8,9)

等等!

我目前正在使用方法来产生2,3和4值组合的返回集,但在我看来,这可以在LINQ查询中推广.

谢谢你的帮助!

Answer 1

用法:

var results = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }.DifferentCombinations(3);

码:

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

Answer 2

两个答案都很好，但可以通过消除内存分配来加快速度

对于答案 1：现在从 60 计算 5 时速度提高了 2.5 倍

编辑：EnumerableEx.Return来自 System.Interactive 包。

public static IEnumerable<IEnumerable<T>> DifferentCombinations2<T>
    (this IEnumerable<T> elements, int k)
{
    return k == 0 
        ? EnumerableEx.Return(Enumerable.Empty<T>()) 
        : elements.SelectMany((e, i) => 
            elements.Skip(i + 1)
                .DifferentCombinations(k - 1)
                .Select(c => EnumerableEx.Return(e).Concat(c)));
}

答案 2：现在从 60 计算 5 时速度提高了 3 倍

static class Combinations
{
    private static void SetIndexes(int[] indexes, int lastIndex, int count)
    {
        indexes[lastIndex]++;
        if (lastIndex > 0 && indexes[lastIndex] == count)
        {
            SetIndexes(indexes, lastIndex - 1, count - 1);
            indexes[lastIndex] = indexes[lastIndex - 1] + 1;
        }
    }

    private static bool AllPlacesChecked(int[] indexes, int places)
    {
        for (int i = indexes.Length - 1; i >= 0; i--)
        {
            if (indexes[i] != places)
                return false;
            places--;
        }
        return true;
    }

public static IEnumerable<IEnumerable<T>> GetDifferentCombinations<T>(this IEnumerable<T> c, int count)
{
    var collection = c.ToList();
    int listCount = collection.Count();

    if (count > listCount)
        throw new InvalidOperationException($"{nameof(count)} is greater than the collection elements.");

    int[] indexes = Enumerable.Range(0, count).ToArray();

    do
    {
        yield return indexes.Select(i => collection[i]).ToList();

        SetIndexes(indexes, indexes.Length - 1, listCount);
    }
    while (!AllPlacesChecked(indexes, listCount));
}
}

这导致对于 60 中的 5 个答案，答案 2 比答案 1 快 5 倍。