修剪的笛卡尔乘积的LINQ实现 [英] LINQ implementation of Cartesian Product with pruning
问题描述
我希望有人能够帮助我，至少对我来说，这是一个非常棘手的算法.
I hope someone is able to help me with what is, at least to me, quite a tricky algorithm.
我有一个列表(1 <= size <= 5，但是大小直到运行时才知道)，我需要将其合并(1 <= size <= 2).这是我正在查看的示例:-
I have a List (1 <= size <= 5, but size unknown until run-time) of Lists (1 <= size <= 2) that I need to combine. Here is an example of what I am looking at:-
ListOfLists = { {1}, {2,3}, {2,3}, {4}, {2,3} }
所以，我需要完成两个步骤:-
So, there are 2 stages to what I need to do:-
(1).我需要以这样一种方式组合内部列表，使得任何组合中的每个列表中都只有一个项目，也就是说，此处结果集中可能的组合为:-
(1). I need to combine the inner lists in such a way that any combination has exactly ONE item from each list, that is, the possible combinations in the result set here would be:-
- 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新手).
The Cartesian Product takes care of this, so stage 1 is done.....now, here comes the twist which I can't figure out - at least I can't figure out a LINQ way of doing it (I am still a LINQ noob).
(2).现在，我需要从该笛卡尔积中滤除任何重复的结果.在这种情况下，重复项构成结果集中的任何行，并且每个单独的列表元素的数量与另一行相同，即
(2). I now need to filter out any duplicate results from this Cartesian Product. A duplicate in this case constitutes any line in the result set with the same quantity of each distinct list element as another line, that is,
1,2,2,4,3与1,3,2,4,2相同"
1,2,2,4,3 is the "same" as 1,3,2,4,2
因为第一个列表中的每个不同项目在两个列表中都发生相同的次数(1个在每个列表中出现一次，2个在每个列表中出现两次，....
because each distinct item within the first list occurs the same number of times in both lists (1 occurs once in each list, 2 appears twice in each list, ....
因此，最终结果集应如下所示……
The final result set should therefore look like this...
- 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个结果，但是我要得到的修剪后的结果集只是: -
Another example is the worst-case scenario (from a combination point of view) where the ListOfLists is {{2,3}, {2,3}, {2,3}, {2,3}, {2,3}}, i.e. a list containing inner lists of the maximum size - in this case there would obviously be 32 results in the Cartesian Product result-set, but the pruned result-set that I am trying to get at would just be:-
- 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解决方案的指南.
To any mathematically-minded folks out there - I hope you can help. I have actually got a working solution to part 2, but it is a total hack and is computationally-intensive, and I am looking for guidance in finding a more elegant, and efficient LINQ solution to the issue of pruning.
感谢阅读.
点
到目前为止已使用了一些资源(以获得笛卡尔积)
Some resources used so far (to get the Cartesian Product)
- computing-a-cartesian-product-with-linq
- c-permutation-of-an-array-of-arraylists
- msdn
Apologies for not posting this sooner...see below
推荐答案
You should implement your own IEqualityComparer<IEnumerable<int>> and then use that in Distinct().
IEqualityComparer中哈希代码的选择取决于您的实际数据，但是我认为，如果您的实际数据与示例中的数据类似，则这样的操作就足够了:
The choice of hash code in the IEqualityComparer depends on your actual data, but I think something like this should be adequate if your actual data resemble those in your examples:
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)，排序速度太慢.
The important part is that GetHashCode() should be O(N), sorting would be too slow.
这篇关于修剪的笛卡尔乘积的LINQ实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
