LINQ執行笛卡爾乘積與修剪

Question

我希望有人能夠幫助我什麼，至少對我來說，相當棘手的算法。

的問題

我有列表（1 <= size <= 2），我需要組合的列表（1 <= size <= 5，但大小未知的，直到運行時）。這裏是什麼，我期待一個例子： -

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

因此，有2個階段什麼，我需要做的： -

（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

笛卡爾積照顧這一點，所以第一階段完成後.....現在，這裏來，我想不通的扭曲 - 至少我無法弄清楚LINQ的做法（我仍然是LINQ noob）。

（2）。我現在需要從這個Cartesian產品中濾除任何重複的結果。在這種情況下的重複的構成的結果與每個不同的列表元素作爲另一行，即相同數量的設置的任何行，

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部分的工作解決方案，但它是一個徹底的破解，並且是計算密集型的，我正在尋找指導，爲修剪問題找到更優雅，更高效的LINQ解決方案。

感謝您的閱讀。

PIP

至今使用的一些資源（以獲得乘積）

• computing-a-cartesian-product-with-linq
• c-permutation-of-an-array-of-arraylists
• msdn

更新 - 解決方案

不張貼這遲早

道歉......看到below

Answer 1

你應該實現自己的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），排序會太慢。

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的博客here中找到的現有CartesianProduct答案中（我推薦閱讀他的文章，因爲它解釋了他思考中的迭代以及爲什麼linq implimentation是最好的）。

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