我希望有人能够帮助我，至少对我来说，这是一个非常棘手的算法。

问题

我有一个列表(1 <= size <= 2)需要组合的列表(1 <= size <= 5，但大小未知，直到 run-time)。这是我正在查看的示例：-

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 阶段是 done.....now，这是我无法弄清楚的转折点-至少我无法弄清楚 LINQ 的处理方式(我仍然是 LINQ noob)。

(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

另一个示例是 worst-case 场景(从组合的角度来看)，其中 ListOfLists 为{{2,3}，{2,3}，{2,3}，{2,3}，{2,3}}， i.e。一个包含最大大小的内部列表的列表-在这种情况下，笛卡尔乘积 result-set 显然将有 32 个结果，但是我尝试获取的修剪后的 result-set 只是：-

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

对于在那里的任何 mathematically-minded 个人-希望您能提供帮助。实际上，我已经为第 2 部分找到了一个可行的解决方案，但这是一个完全的技巧，是 computationally-intensive，并且我正在寻找有关为修剪问题找到更优雅，更有效的 LINQ 解决方案的指南。

谢谢阅读。

点子

到目前为止已使用的一些资源(获得笛卡尔积)

更新-解决方案

抱歉未发布此 sooner...see 下面

3 回答

3
您应该实现自己的IEqualityComparer<IEnumerable<int>>，然后在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)，排序速度太慢。
回复于 2024-04-30T00:00:28+08:00

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;
        }
    }

回复于 2024-04-30T00:00:28+08:00

最终确定了多集整体组合的最终解决方案，然后修剪 result-sets 以消除重复问题，最终将其作为静态方法作为帮助器类生成。它采用了 svick 广受赞赏的答案，并将 IEqualityComparer 依赖项注入到我在 Eric Lipperts 的博客这里中找到的现有 CartesianProduct 答案中(我建议阅读他的帖子，因为它解释了他的思想中的迭代以及为什么 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;
}

回复于 2024-04-30T00:00:28+08:00

修剪的直角积的 LINQ 实现

问题

更新-解决方案

3 回答

相关问题