带剪枝的笛卡尔积的 LINQ 实现

Question

我希望有人能够帮助我解决至少对我来说相当棘手的算法。

问题

我有一个列表（1 <= size <= 5，但大小在运行时之前未知）（1 <= size <= 2） >）我需要合并。这是我正在查看的示例：-

ListOfLists = { {1}, {2,3}, {2,3}, {4}, {2,3} }

因此，我需要执行两个阶段：-

(1)。我需要以这样的方式组合内部列表，即任何组合都只有每个列表中的一个项目，也就是说，此处结果集中可能的组合为：-

• 1,2,2,4,2
• 1,2, 2,4,3
• 1,2,3,4,2
• 1,2,3,4,3
• 1,3,2,4,2
• 1,3,2,4,3
• 1,3,3,4,2
• 1,3,3,4,3

笛卡尔积解决了这个问题，因此第 1 阶段完成了......现在，出现了我无法弄清楚的转折 - 至少我无法弄清楚LINQ 的实现方式（我仍然是 LINQ 菜鸟）。

（2）。我现在需要过滤掉此笛卡尔积中的任何重复结果。在这种情况下，重复项构成结果集中的任何行，其每个不同列表元素的数量与另一行相同，即

1,2,2,4,3 与 1,3,2,4 “相同” ,2

因为第一个列表中的每个不同项目在两个列表中出现的次数相同（1 在每个列表中出现一次，2 在每个列表中出现两次，...

因此最终结果集应如下所示...

• 1,2,2,4,2
• 1,2,2,4,3
• --
• 1,2,3,4,3
• --
• --
• --
• 1,3,3,4,3

再比如最坏的情况（从组合的角度来看) 其中 ListOfLists 是 {{2,3}, {2,3}, {2,3}, {2,3}, {2,3}}，即包含最大大小的内部列表的列表 - 在此笛卡尔积显然会有 32 个结果结果集，但我试图获得的修剪结果集只是：-

• 2,2,2,2,2
• 2,2,2,2,3 <-- 所有其他带有四个 2 的结果和一个 3（以任何顺序）被抑制
• 2,2,2,3,3 <-- 所有其他具有三个 2 和两个 3 的结果被抑制，等等
• 2,2,3,3,3
• 2,3,3,3,3
• 3,3,3,3,3

对于任何有数学头脑的人 - 我希望你能有所帮助。我实际上已经为第 2 部分找到了一个可行的解决方案，但它完全是一个 hack，并且计算量很大，我正在寻求指导，以找到一个更优雅、更高效的 LINQ 解决方案来解决修剪问题。

感谢您的阅读。

pip

到目前为止使用的一些资源（用于获取笛卡尔积）

• 使用 linq 计算笛卡尔积
• c-permutation-of-an-array-of-arraylists
• msdn

更新 - 解决方案

抱歉尽快发布此内容...请参阅下面的下面

Answer 1

您应该实现自己的 IEqualityComparer> 然后在 Distinct()。

IEqualityComparer 中哈希代码的选择取决于您的实际数据，但我认为如果您的实际数据与示例中的数据类似，这样的内容应该足够了：

class UnorderedQeuenceComparer : IEqualityComparer<IEnumerable<int>>
{
    public bool Equals(IEnumerable<int> x, IEnumerable<int> y)
    {
        return x.OrderBy(i => i).SequenceEqual(y.OrderBy(i => i));
    }

    public int GetHashCode(IEnumerable<int> obj)
    {
        return obj.Sum(i => i * i);
    }
}

重要的部分是 GetHashCode( ) 应该是 O(N)，排序会太慢。

Answer 2

void Main()
{
    var query =     from a in new int[] { 1 }
                    from b in new int[] { 2, 3 }
                    from c in new int[] { 2, 3 }
                    from d in new int[] { 4 }                   
                    from e in new int[] { 2, 3 }
                    select new int[] { a, b, c, d, e }; 
    query.Distinct(new ArrayComparer());
        //.Dump();
}
 public class ArrayComparer : IEqualityComparer<int[]>
    {
        public bool Equals(int[] x, int[] y)
        {            
            if (x == null || y == null)
                return false;

            return x.OrderBy(i => i).SequenceEqual<int>(y.OrderBy(i => i));

        }

        public int GetHashCode(int[] obj)
        {
            if ( obj == null || obj.Length == 0)
                return 0;
            var hashcode = obj[0];
            for (int i = 1; i < obj.Length; i++)
            {
                hashcode ^= obj[i];
            }
            return hashcode;
        }
    }

Answer 3

整个组合多重集，然后修剪结果集以删除重复问题的最终解决方案最终以静态方法的形式出现在辅助类中。它采用了 svick 非常赞赏的答案，并将 IEqualityComparer 依赖项注入到我在 Eric Lipperts 的博客 这里（我建议阅读他的帖子它解释了他的思维迭代以及为什么 linq 实现是最好的）。

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(IEnumerable<IEnumerable<T>> sequences,
                                                       IEqualityComparer<IEnumerable<T>> sequenceComparer)
{
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
    var resultsSet = sequences.Aggregate(emptyProduct, (accumulator, sequence) => from accseq in accumulator
                                                                                  from item in sequence
                                                                                  select accseq.Concat(new[] { item }));

    if (sequenceComparer != null)
        return resultsSet.Distinct(sequenceComparer);
    else
        return resultsSet;
}