c# - 使用 LINQ 获取不同的数字组合

Question

以下代码根据 1,2,3 = 3,2,1 = 2,3,1 的逻辑返回所有不同的组合，因此它仅返回该组数字的 1 个实例。

但是，我想更改该逻辑，以便它返回所有数字集的所有实例。

我需要对“GetPowerSet”下面的 LINQ 查询做些什么才能实现这一点？

    public void GetPowersets()
    {
        List<int> ints = new List<int>()
        {
            1,2,2,3,3
        };

        var results = GetPowerSet(ints);


        List<String> combinations = new List<String>();
        foreach (var result in results)
        {
            StringBuilder sb = new StringBuilder();
            foreach (var intValue in result.OrderBy(x => x))
            {
                sb.Append(intValue + ",");
            }
            combinations.Add(sb.ToString());
        }

        string c1 = string.Join("|", combinations.ToArray()).Replace(",|", "|");
        //c1 = "|1|2|1,2|2|1,2|2,2|1,2,2|3|1,3|2,3|1,2,3|2,3|1,2,3|2,2,3|1,2,2,3|3|1,3|2,3|1,2,3|2,3|1,2,3|2,2,3|1,2,2,3|3,3|1,3,3|2,3,3|1,2,3,3|2,3,3|1,2,3,3|2,2,3,3|1,2,2,3,3,"

    }

    public IEnumerable<IEnumerable<int>> GetPowerSet(List<int> list)
    {
        return from m in Enumerable.Range(0, 1 << list.Count)
                     select
                         from i in Enumerable.Range(0, list.Count)
                         where (m & (1 << i)) != 0
                         select list[i];
    }

这是我试图实现的最终结果:(没有重复的组合行:duplicate = 3,2,1 和 3,2,1 是同一件事。但是 1,2,3 和 3,2， 1 不是一回事，两者都应该在最终结果中)

1
2
3
1,2
1,3
2,1
2,3
2,2
3,1
3,2
3,3
1,2,3
1,2,2
1,3,2
1,3,3
2,1,3
2,1,2
2,3,1
2,3,2
2,3,3
2,2,1
2,2,3
3,1,2
3,1,3
3,2,1
3,2,2
3,2,3
3,3,1
3,3,2
1,2,3,2
1,2,3,3
1,2,2,3
1,3,2,2
1,3,2,3
1,3,3,2
2,1,3,2
2,1,3,3
2,1,2,3
2,3,1,2
2,3,1,3
2,3,2,1
2,3,2,3
2,3,3,1
2,3,3,2
2,2,1,3
2,2,3,1
2,2,3,3
3,1,2,2
3,1,2,3
3,1,3,2
3,2,1,2
3,2,1,3
3,2,2,1
3,2,2,3
3,2,3,1
3,2,3,2
3,3,1,2
3,3,2,1
3,3,2,2
1,2,3,2,3
1,2,3,3,2
1,2,2,3,3
1,3,2,2,3
1,3,2,3,2
1,3,3,2,2
2,1,3,2,3
2,1,3,3,2
2,1,2,3,3
2,3,1,2,3
2,3,1,3,2
2,3,2,1,3
2,3,2,3,1
2,3,3,1,2
2,3,3,2,1
2,2,1,3,3
2,2,3,1,3
2,2,3,3,1
3,1,2,2,3
3,1,2,3,2
3,1,3,2,2
3,2,1,2,3
3,2,1,3,2
3,2,2,1,3
3,2,2,3,1
3,2,3,1,2
3,2,3,2,1
3,3,1,2,2
3,3,2,1,2
3,3,2,2,1

执行此操作的“foreach”方式，一旦数字集变得太大(我预计 LINQ 不应该有这个问题)，它往往会导致“内存不足异常”，如下所示。这按我想要的方式工作，返回我想要的结果集。但它很慢并且存在性能问题。我也乐于接受有关如何让它变得更好的建议。

public List<List<int>> GetAllCombinationsOfAllSizes(List<int> ints)
{
    List<List<int>> returnResult = new List<List<int>>();

    var distinctInts = ints.Distinct().ToList();
    for (int j = 0; j < distinctInts.Count(); j++)
    {
        var number = distinctInts[j];

        var newList = new List<int>();
        newList.Add(number);
        returnResult.Add(newList);

        var listMinusOneObject = ints.Select(x => x).ToList();
        listMinusOneObject.Remove(listMinusOneObject.Where(x => x == number).First());

        if (listMinusOneObject.Count() > 0)
        {
            _GetAllCombinationsOfAllSizes(listMinusOneObject, newList, ref returnResult);
        }
    }

    return returnResult;
}
public void _GetAllCombinationsOfAllSizes(List<int> ints, List<int> growingList, ref List<List<int>> returnResult)
{
    var distinctInts = ints.Distinct().ToList();
    for (int j = 0; j < distinctInts.Count(); j++)
    {
        var number = distinctInts[j];

        var newList = growingList.ToList();
        newList.Add(number);
        returnResult.Add(newList);

        var listMinusOneObject = ints.Select(x => x).ToList();
        listMinusOneObject.Remove(listMinusOneObject.Where(x => x == number).First());

        if (listMinusOneObject.Count() > 0)
        {
            _GetAllCombinationsOfAllSizes(listMinusOneObject, newList, ref returnResult);
        }
    }

}

我正在寻找的答案是:如何实现我想要的结果集，但使用 LINQ 和 C# 来实现，其方式比我发布的当前“foreach”方式更快、更高效？

Answer 1

NEW UPDATE(删除了旧代码，性能优于 OP 的代码，产生了输出)

static IEnumerable<int[]> EnumeratePermutations2(int[] ints)
{
    Dictionary<int, int> intCounts = ints.GroupBy(n => n)
                                         .ToDictionary(g => g.Key, g => g.Count());
    int[] distincts = intCounts.Keys.ToArray();
    foreach (int[] permutation in EnumeratePermutations2(new int[0], intCounts, distincts))
        yield return permutation;
}

static IEnumerable<int[]> EnumeratePermutations2(int[] prefix, Dictionary<int, int> intCounts, int[] distincts)
{
    foreach (int n in distincts)
    {
        int[] newPrefix = new int[prefix.Length + 1];
        Array.Copy(prefix, newPrefix, prefix.Length);
        newPrefix[prefix.Length] = n;
        yield return newPrefix;
        intCounts[n]--;
        int[] newDistincts = intCounts[n] > 0
                             ? distincts
                             : distincts.Where(x => x != n).ToArray();
        foreach (int[] permutation in EnumeratePermutations2(newPrefix, intCounts, newDistincts))
            yield return permutation;
        intCounts[n]++;
    }
}