如何在不重复的情况下将列表中的项目与所有其他项目进行比较?

本文关键字：项目比较其他列表情况下 | 更新日期: 2023-09-27 18:05:19

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

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

A.IsCompatibleWith(B)将始终与B.IsCompatibleWith(A)相同。例如，如果我有一个包含其中4个的集合，我试图找到一个LINQ查询，该查询将对同一集合中的每个不同的项目对运行该方法。因此，如果我的集合包含A, B, C和D，我希望做的相当于:

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

如何在不重复的情况下将列表中的项目与所有其他项目进行比较?

Edit…

根据添加到问题中的"final query"判断，您需要一个方法来确定集合中的所有项是否相互兼容。以下是如何合理有效地做到这一点的方法:

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

(注意，尽管这相当有效，但它并没有保留集合的原始顺序。

应该这样做:

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

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

编辑:如果你在myItem中有一个索引，你应该使用那个而不是indexOf。你可以从where子句中删除"item != other"现在有点多余了

我有个想法:

实现IComparable，使您的MyItem变得可排序，然后运行这个linq-query:

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

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

所以我们有

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
}

相关文章：

最新信息: