我有一个简单的List< T>而我正在尝试对它进行排序.但是,列表中的项目在可比性方面并不是全部可传递的,例如,对于例如我的清单< T>好像:
A
B
C
D
E
其中A> B和B> C但C> A.也可以像A>那样具有圆形的伟大. B,B> C,C> D但是D> A,即它不必总是一组3.我想要的是在给定列表中找到所有圆形大小组< T>.例如,假设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() < l.Last())
// then remove the duplicate lists using special comparer
.Distinct(new CircularComparer())
.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万个项目).有没有更合理有效的方法?我不是追求最快的代码.这里有更好的递归方法吗?闻起来像.
本文由 投稿者 创作,文章地址:https://blog.isoyu.com/archives/c-chazhaojihezhongdexunhuanxiangfeichuandixiang.html
采用知识共享署名4.0 国际许可协议进行许可。除注明转载/出处外,均为本站原创或翻译,转载前请务必署名。最后编辑时间为:11 月 11, 2019 at 11:31 上午