c# - 在集合中查找循环项(非传递项)

Question

问题:

我有一个简单的 List<T>我正在尝试对其进行排序。但是列表中的项目在可比性方面并不都是可传递的，例如，我的List<T>看起来像:

A
B
C
D
E

其中 A > B 和 B > C 但 C > A。也可能有像 A > B、B > C、C > D 但 D > A ，即不必总是一组 3。我想要的是 在给定的 List<T> 中找到所有的循环伟大组 。例如，假设 A > B > C > A 和 A > B > C > D > A 是上述情况下的两个循环组，我的输出应该看起来像:

List<List<T>> circulars = [[A, B, C, A], [A, B, C, D, A]]

或

List<List<T>> circulars = [[A, B, C], [A, B, C, D]]
// but in this case I do not want duplicates in the output. 
// For e.g., the output shouldn't have both [B, C, A] and [A, B, C]
// since both the groups refer to the same set of circular items A, B & C
// as B > C > A > B is also true. 
// But [B, A, C] is a different group (though nothing circular about it)

任何一个都适合我。我更喜欢小型(linquish)解决方案，但这看起来并不像最初看起来那么容易。可能是我遗漏了一些非常简单的东西。

---

场景:

这是体育分析的一部分，其中一名球员/球队将比另一名球员/球队强，而另一名球员/球队又将比另一名球员/球队强，但最后一名将比第一名强。我不能透露更多信息，但让我举一个体育运动中的正面交锋的例子，尤其是在网球和国际象棋中，个人对决导致了这种情况。例如，就正面交锋而言，克拉姆尼克领先卡斯帕罗夫，卡斯帕罗夫领先卡尔波夫，但卡尔波夫领先克拉姆尼克。或者另一个例子，费德勒领先达维登科，达维登科领先纳达尔，但纳达尔领先费德勒。

我的类(class)是这样的:

class Player : IComparable<Player>
{
    // logic
}

这是我尝试过的:

1. 首先生成最小组大小为 3 的集合项的所有可能排列。如 [A B C]、[A、C、B]....、[A、B、C、D]、[ A, B, D, C]...等(这很慢)

2. 然后遍历整个子组并检查模式。就像在任何情况下 A > B > C > D(这相当慢，但我可以接受)

3. 最后遍历整个子组以删除重复的组，如 [A, B, C] 和 [B, C, A] 等。

代码:

var players = [.....]; //all the players in the collection

// first generate all the permutations possible in the list from size 3 
// to players.Count
var circulars = Enumerable.Range(3, players.Count - 3 + 1)
               .Select(x => players.Permutations(x))
               .SelectMany(x => x)
               .Select(x => x.ToList())

// then check in the each sublists if a pattern like A > B > C > A is 
// generated                                                                          vv    this is the player comparison
               .Where(l => l.Zip(l.Skip(1), (p1, p2) => new { p1, p2 }).All(x => x.p1 > x.p2) && l.First() < l.Last())

// then remove the duplicate lists using special comparer
               .Distinct(new CircularComparer<Player>())
               .ToList();
  
public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> list, int length)
{
    if (length == 1) 
        return list.Select(t => new[] { t });

    return Permutations(list, length - 1)  
          .SelectMany(t => list.Where(e => !t.Contains(e)), (t1, t2) => t1.Concat(new[] { t2 }));
}

class CircularComparer<T> : IEqualityComparer<ICollection<T>>
{
    public bool Equals(ICollection<T> x, ICollection<T> y)
    {
        if (x.Count != y.Count)
            return false;

        return Enumerable.Range(1, x.Count)
              .Any(i => x.SequenceEqual(y.Skip(i).Concat(y.Take(i))));
    }

    public int GetHashCode(ICollection<T> obj)
    {
        return 0;
    }
}

这种方法的问题是它非常慢。对于只有大约 10 个项目的集合，必须自行生成的排列是巨大的(接近 100 万个项目)。有没有更好的合理有效的方法？我不追求最快的代码。这里有更好的递归方法吗？闻起来像。

Answer 1

场景...

[A, B, C, D, E]

where A > B, B > C, C > D, C > A, D > A

...可以使用 A -> B 表示 A > B 的约定表示为有向图:

所以问题本质上是“如何在有向图中找到循环？”

要解决这个问题，您可以使用 Tarjan's strongly connected components algorithm .我建议查找此算法的良好实现并将其应用于您的场景。