如何将列表中的项目与其他项目进行比较而不重复？

Question

我有一个对象集合（让我们称它们为MyItem），并且每个MyItem都有一个名为IsCompatibleWith的方法，它返回一个布尔值，表示它是否与另一个MyItem兼容。

public class MyItem 
{ 
    ... 
    public bool IsCompatibleWith(MyItem other) { ... } 
    ... 
} 

A.IsCompatibleWith(B)永远是一样B.IsCompatibleWith(A)。例如，如果我有一个包含其中4个的集合，我试图找到一个LINQ查询，它将在同一个集合中的每个不同的项目对上运行该方法。所以，如果我的集合包含A，B，C和DI希望这样做相当于：

A.IsCompatibleWith(B); // A & B 
A.IsCompatibleWith(C); // A & C 
A.IsCompatibleWith(D); // A & D 
B.IsCompatibleWith(C); // B & C 
B.IsCompatibleWith(D); // B & D 
C.IsCompatibleWith(D); // C & D 

代码最初使用是：

var result = from item in myItems 
      from other in myItems 
      where item != other && 
        item.IsCompatibleWith(other) 
      select item; 

当然的，但是这仍然会做两A & B和B & A （这不是必需的和不高效的）。也可能值得注意的是，实际上这些列表将比4个项目大得多，因此希望得到最佳解决方案。

希望这是有道理的...任何想法？

编辑： 一个可能的查询 -

MyItem[] items = myItems.ToArray(); 
bool compatible = (from item in items 
        from other in items 
        where 
         Array.IndexOf(items, item) < Array.IndexOf(items, other) && 
         !item.IsCompatibleWith(other) 
        select item).FirstOrDefault() == null; 

EDIT2：到底从LukeH切换到使用自定义的解决方案，因为它是更大的列表更有效。

public bool AreAllCompatible() 
{ 
    using (var e = myItems.GetEnumerator()) 
    { 
     var buffer = new List<MyItem>(); 
     while (e.MoveNext()) 
     { 
      if (buffer.Any(item => !item.IsCompatibleWith(e.Current))) 
       return false; 
      buffer.Add(e.Current); 
     } 
    } 
    return true; 
} 

Answer 1

编辑...

由“最终查询”来看添加到你的问题，你需要一种方法以确定集合中的所有项目是否相互兼容。以下是如何合理有效地做到这一点：

bool compatible = myItems.AreAllItemsCompatible(); 

// ... 

public static bool AreAllItemsCompatible(this IEnumerable<MyItem> source) 
{ 
    using (var e = source.GetEnumerator()) 
    { 
     var buffer = new List<MyItem>(); 

     while (e.MoveNext()) 
     { 
      foreach (MyItem item in buffer) 
      { 
       if (!item.IsCompatibleWith(e.Current)) 
        return false; 
      } 
      buffer.Add(e.Current); 
     } 
    } 
    return true; 
} 

原来的答案...

我不认为有一个有效的方式来做到这一点只能使用内置的LINQ的方法。

虽然很容易建立自己的。这是你需要的那种代码的例子。我不确定究竟是你试图返回什么结果，所以我只是给每个兼容对写一条消息给控制台。应该很容易将其更改为产生您需要的结果。

using (var e = myItems.GetEnumerator()) 
{ 
    var buffer = new List<MyItem>(); 

    while (e.MoveNext()) 
    { 
     foreach (MyItem item in buffer) 
     { 
      if (item.IsCompatibleWith(e.Current)) 
      { 
       Console.WriteLine(item + " is compatible with " + e.Current); 
      } 
     } 
     buffer.Add(e.Current); 
    } 
} 

（请注意，虽然这是相当有效的，它不保存收集的原始排序。那是在你的情况的问题？）

Answer 2

这里有一个想法：

实现IComparable让您MyItem变得排序，然后运行这个LINQ查询：

var result = from item in myItems 
      from other in myItems 
      where item.CompareTo(other) < 0 && 
        item.IsCompatibleWith(other) 
      select item; 

Answer 3

这应该这样做：

var result = from item in myItems 
     from other in myItems 
     where item != other && 
       myItems.indexOf(item) < myItems.indexOf(other) && 
       item.IsCompatibleWith(other) 
     select item; 

但我不知道它是否使它更快，因为在查询中必须检查indi每行的行数。

编辑： 如果您在myItem有一个索引，你应该使用一个替代的indexOf。你可以从多余的where子句，点点去掉“项目！=其他”现在

Answer 4

如果您MyItem收集足够小，你可以存储item.IsCompatibleWith(otherItem)在布尔数组结果：

var itemCount = myItems.Count(); 
var compatibilityTable = new bool[itemCount, itemCount]; 

var itemsToCompare = new List<MyItem>(); 
var i = 0; 
var j = 0; 
foreach (var item in myItems) 
{ 
    j = 0; 
    foreach (var other in itemsToCompare) 
    { 
     compatibilityTable[i,j] = item.IsCompatibleWith(other); 
     compatibilityTable[j,i] = compatibilityTable[i,j]; 
     j++; 
    } 
    itemsToCompare.Add(item); 
    i++; 
} 

var result = myItems.Where((item, i) => 
        { 
         var compatible = true; 
         var j = 0; 
         while (compatible && j < itemCount) 
         { 
          compatible = compatibilityTable[i,j]; 
         } 
         j++; 
         return compatible; 
        } 

Answer 5

因此，我们有

IEnumerable<MyItem> MyItems; 

要获得所有组合，我们可以使用这样的功能。

//returns all the k sized combinations from a list 
public static IEnumerable<IEnumerable<T>> Combinations<T>(IEnumerable<T> list, 
                  int k) 
{ 
    if (k == 0) return new[] {new T[0]}; 

    return list.SelectMany((l, i) => 
     Combinations(list.Skip(i + 1), k - 1).Select(c => (new[] {l}).Concat(c)) 
    ); 
} 

然后我们可以将这个函数应用到我们这样的问题中。

var combinations = Combinations(MyItems, 2).Select(c => c.ToList<MyItem>()); 
var result = combinations.Where(c => c[0].IsCompatibleWith(c[1])) 

这将对所有组合执行IsCompatableWith而不重复。

您当然可以执行Combinations函数中的检查。对于进一步的工作，你可以将Combinations函数扩展为带有可变数量参数的代理，用于k的多个长度。

编辑：正如我上面所说，如果你在你的代码写这些扩展方法

public static class Extenesions 
{ 
    IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> list, int k) 
    { 
     if (k == 0) return new[] { new T[0] }; 

     return list.SelectMany((l, i) => 
      list.Skip(i + 1).Combinations<T>(k - 1) 
       .Select(c => (new[] { l }).Concat(c))); 
    } 

    IEnumerable<Tuple<T, T>> Combinations<T> (this IEnumerable<T> list, 
               Func<T, T, bool> filter) 
    { 
     return list.Combinations(2).Where(c => 
      filter(c.First(), c.Last())).Select(c => 
       Tuple.Create<T, T>(c.First(), c.Last())); 

    } 
} 

那么你可以做的，而更优雅（IMO）

var compatibleTuples = myItems.Combinations(a, b) => a.IsCompatibleWith(b))) 

然后得到的兼容项目与

foreach(var t in compatibleTuples) 
{ 
    t.Item1 // or T.item2 
}