姬長信(Redy)

c# – 查找集合中的循环项(非传递项)


问题:

我有一个简单的List而我正在尝试对它进行排序.但是,列表中的项目在可比性方面并不是全部可传递的,例如,对于例如我的清单好像:

A
B
C
D
E

其中A> B和B> C但C> A.也可以像A>那样具有圆形的伟大. B,B> C,C> D但是D> A,即它不必总是一组3.我想要的是在给定列表中找到所有圆形大小组.例如,假设A> B> C> A和A> B> C> D> A是上面两个圆形组,我的输出应该看起来像:

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

要么

List> 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 Player : IComparable
{
    // logic
}

这是我试过的:

>首先生成所有可能的集合项排列,最小组大小为3.如[ABC],[A,C,B] ….,[A,B,C,D],[A,B,D ,C] ….等(这很慢)
>然后浏览整个子组并检查模式.就像是否存在A>的情况一样B> C> D(这个速度相当慢,但我很好)
>最后遍历整个子组以删除重复的组,如[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() ())
               .ToList();

public static IEnumerable> Permutations(this IEnumerable 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 : IEqualityComparer>
{
    public bool Equals(ICollection x, ICollection 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 obj)
    {
        return 0;
    }
}

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