blocks|key|1075314|text|这种锦标赛日程安排通常被称为round-robin。在维基百科中，也有一个可能的scheduling+algorithm的例子。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1075315|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Round-robin_tournament|1|http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm^0|E|B|0|14|K|1|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]|$A|R|B|S|1|T]]|C|$]]|$1|D|3|-4|5|6|7|U|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]]]

Such tournament schedule is often called <a href="http://en.wikipedia.org/wiki/Round-robin_tournament" rel="nofollow">round-robin</a>. In wikipedia, there's also an example of possible <a href="http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm" rel="nofollow">scheduling algorithm</a>.

blocks|key|1890873|text|假设玩家不会在列表中出现两次，那么双for循环会非常快：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1890874|for+(int+i=0,+i+<=+playerList.Count+-+2,+i%2B%2B)
++++for+(int+j=i%2B1,+j+<=+playerList.Count+-+1,+j%2B%2B)
++++++++//add+a+new+pairing+of+player+i+and+j|code-block|syntax|javascript|1890875|entityMap^0|I|3|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@$9|N|A|O|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|P|8|@]|D|@]|E|$I|J]]|$1|K|3|-4|5|6|7|Q|8|@]|D|@]|E|$]]]|L|$]]

assuming that players do not appear in the list twice, a double <code>for</code> loop is very quick:

<pre><code>for (int i=0, i &lt;= playerList.Count - 2, i++)
 for (int j=i+1, j &lt;= playerList.Count - 1, j++)
 //add a new pairing of player i and j
</code></pre>

blocks|key|3142110|text|一个简单的分而治之的算法：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3142111|3142112|If只有两个人:将它们配对并返回them.|ordered-list-item|offset|length|style|BOLD|3142113|Otherwise:|3142114|：|3142115|1.+Split+the+group+in+two+groups+of+equal+size.+
2.+Find+all+pairings+in+each+group+using+this+algorithm+recursively.
3.+Join+the+two+lists.|code-block|syntax|javascript|3142116|例如，[[(a,b)]]和[[(c,d)]]变成了[[(a,b),(c,d)]]。|CODE|3142117|4.通过轮换第二组，找出两组之间的配对。|3142118|例如，[[(a,c),(b,d)],[(a,d),(b,c)]]|3142119|5.返回(3)+%2B+(4)|3142120|​|3142121|该算法在O(n%5E2)时间内运行，这是最优的，因为它生成(n-1)轮的n/2配对。|3142122|对于8个玩家，你将得到7个回合：|3142123|[(a,b),+(c,d),+(e,f),+(g,h)]
[(a,c),+(b,d),+(e,g),+(f,h)]
[(a,d),+(b,c),+(e,h),+(f,g)]
[(a,e),+(b,f),+(c,g),+(e,h)]
[(a,f),+(b,g),+(c,h),+(e,e)]
[(a,g),+(b,h),+(c,e),+(e,f)]
[(a,h),+(b,e),+(c,f),+(e,g)]|3142124|entityMap^0|0|0|0|L|0|0|A|0|0|1|0|0|3|9|D|9|P|F|0|0|3|T|0|4|3|A|3|0|0|4|6|R|5|Y|3|0|0|0^^$0|@$1|2|3|4|5|6|7|1B|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|1C|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|1D|8|@$F|1E|G|1F|H|I]]|9|@]|A|$]]|$1|J|3|K|5|E|7|1G|8|@$F|1H|G|1I|H|I]]|9|@]|A|$]]|$1|L|3|M|5|6|7|1J|8|@$F|1K|G|1L|H|I]]|9|@]|A|$]]|$1|N|3|O|5|P|7|1M|8|@]|9|@]|A|$Q|R]]|$1|S|3|T|5|6|7|1N|8|@$F|1O|G|1P|H|U]|$F|1Q|G|1R|H|U]|$F|1S|G|1T|H|U]]|9|@]|A|$]]|$1|V|3|W|5|6|7|1U|8|@]|9|@]|A|$]]|$1|X|3|Y|5|6|7|1V|8|@$F|1W|G|1X|H|U]]|9|@]|A|$]]|$1|Z|3|10|5|6|7|1Y|8|@$F|1Z|G|20|H|U]|$F|21|G|22|H|U]]|9|@]|A|$]]|$1|11|3|12|5|6|7|23|8|@]|9|@]|A|$]]|$1|13|3|14|5|6|7|24|8|@$F|25|G|26|H|U]|$F|27|G|28|H|U]|$F|29|G|2A|H|U]]|9|@]|A|$]]|$1|15|3|16|5|6|7|2B|8|@]|9|@]|A|$]]|$1|17|3|18|5|P|7|2C|8|@]|9|@]|A|$Q|R]]|$1|19|3|-4|5|6|7|2D|8|@]|9|@]|A|$]]]|1A|$]]

A simple divide and conquer algorithm:

<ol>
<li>If there are only two people: Pair them and return them.</li>
<li>Otherwise:

<ol>
<li>Split the group in two groups of equal size. </li>
<li>Find all pairings in each group using this algorithm recursively.</li>
<li>Join the two lists.

E.g. <code>[[(a,b)]]</code> and <code>[[(c,d)]]</code> becomes <code>[[(a,b),(c,d)]]</code>.</li>
<li>Find pairs across of the two groups, by rotating group two.

E.g. <code>[[(a,c),(b,d)],[(a,d),(b,c)]]</code></li>
<li>Return <code>(3)</code> + <code>(4)</code></li>
</ol></li>
</ol>

This algorithm runs in <code>O(n^2)</code> time, which is optimal, as it generates <code>(n-1)</code> rounds of <code>n/2</code> pairings.

For eight players you would get 7 rounds:

<pre><code>[(a,b), (c,d), (e,f), (g,h)]
[(a,c), (b,d), (e,g), (f,h)]
[(a,d), (b,c), (e,h), (f,g)]
[(a,e), (b,f), (c,g), (e,h)]
[(a,f), (b,g), (c,h), (e,e)]
[(a,g), (b,h), (c,e), (e,f)]
[(a,h), (b,e), (c,f), (e,g)]
</code></pre>

blocks|key|3142160|text|我将两个实现放在一起进行性能比较。非常简单的版本1比版本2慢大约50%25，这并不是说没有更快的版本存在。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3142161|class+Program
{
++++class+Player
++++{
++++++++public+string+Name+{+get;+set;+}

++++++++public+Player(string+name)
++++++++{
++++++++++++Name+=+name;
++++++++}
++++}

++++class+Match
++++{
++++++++public+readonly+Player+Player1;
++++++++public+readonly+Player+Player2;

++++++++public+Match(Player+player1,+Player+player2)
++++++++{
++++++++++++Player1+=+player1;
++++++++++++Player2+=+player2;
++++++++}

++++++++public+override+string+ToString()
++++++++{
++++++++++++return+string.Format("{0}+vs.+{1}",+Player1.Name,+Player2.Name);
++++++++}
++++}

++++static+readonly+List<Player>+_players+=+new+List<Player>()
++++{
++++++++new+Player("John"),
++++++++new+Player("Lisa"),
++++++++new+Player("Matt"),
++++++++new+Player("Dan"),
++++++++new+Player("Steve"),
++++++++new+Player("Sarah"),
++++++++new+Player("Tim")
++++};

++++static+void+Main(string[]+args)
++++{
++++++++const+int+count+=+1000000;

++++++++{
++++++++++++var+v1+=+V1();
++++++++++++var+sw+=+Stopwatch.StartNew();
++++++++++++for+(int+i+=+0;+i+<+count;+i%2B%2B)
++++++++++++{
++++++++++++++++v1+=+V1();
++++++++++++}
++++++++++++Console.WriteLine(v1);
++++++++++++Console.WriteLine(sw.Elapsed);
++++++++}

++++++++{
++++++++++++var+v2+=+V2();
++++++++++++var+sw+=+Stopwatch.StartNew();
++++++++++++for+(int+i+=+0;+i+<+count;+i%2B%2B)
++++++++++++{
++++++++++++++++v2+=+V2();
++++++++++++}
++++++++++++Console.WriteLine(v2);
++++++++++++Console.WriteLine(sw.Elapsed);
++++++++}


++++++++Console.ReadLine();
++++}

++++static+List<Match>+V1()
++++{
++++++++var+challengers+=+new+List<Player>(_players);
++++++++var+matches+=+new+List<Match>();
++++++++foreach+(var+player+in+_players)
++++++++{
++++++++++++challengers.Remove(player);
++++++++++++foreach+(var+challenger+in+challengers)
++++++++++++{
++++++++++++++++matches.Add(new+Match(player,+challenger));
++++++++++++}
++++++++}
++++++++return+matches;
++++}

++++static+List<Match>+V2()
++++{
++++++++var+matches+=+new+List<Match>();
++++++++for+(int+i+=+0;+i+<+_players.Count;+i%2B%2B)
++++++++{
++++++++++++for+(int+j+=+i+%2B+1;+j+<+_players.Count;+j%2B%2B)
++++++++++++{
++++++++++++++++matches.Add(new+Match(_players[i],+_players[j]));
++++++++++++}
++++++++}
++++++++return+matches;
++++}
}|code-block|syntax|javascript|3142162|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

I put together 2 implementations to compare performance with. The very naive version 1 is about 50% slower than the version 2. That's not to say that nothing faster exists.

<pre><code>class Program
{
 class Player
 {
 public string Name { get; set; }

 public Player(string name)
 {
 Name = name;
 }
 }

 class Match
 {
 public readonly Player Player1;
 public readonly Player Player2;

 public Match(Player player1, Player player2)
 {
 Player1 = player1;
 Player2 = player2;
 }

 public override string ToString()
 {
 return string.Format("{0} vs. {1}", Player1.Name, Player2.Name);
 }
 }

 static readonly List&lt;Player&gt; _players = new List&lt;Player&gt;()
 {
 new Player("John"),
 new Player("Lisa"),
 new Player("Matt"),
 new Player("Dan"),
 new Player("Steve"),
 new Player("Sarah"),
 new Player("Tim")
 };

 static void Main(string[] args)
 {
 const int count = 1000000;

 {
 var v1 = V1();
 var sw = Stopwatch.StartNew();
 for (int i = 0; i &lt; count; i++)
 {
 v1 = V1();
 }
 Console.WriteLine(v1);
 Console.WriteLine(sw.Elapsed);
 }

 {
 var v2 = V2();
 var sw = Stopwatch.StartNew();
 for (int i = 0; i &lt; count; i++)
 {
 v2 = V2();
 }
 Console.WriteLine(v2);
 Console.WriteLine(sw.Elapsed);
 }


 Console.ReadLine();
 }

 static List&lt;Match&gt; V1()
 {
 var challengers = new List&lt;Player&gt;(_players);
 var matches = new List&lt;Match&gt;();
 foreach (var player in _players)
 {
 challengers.Remove(player);
 foreach (var challenger in challengers)
 {
 matches.Add(new Match(player, challenger));
 }
 }
 return matches;
 }

 static List&lt;Match&gt; V2()
 {
 var matches = new List&lt;Match&gt;();
 for (int i = 0; i &lt; _players.Count; i++)
 {
 for (int j = i + 1; j &lt; _players.Count; j++)
 {
 matches.Add(new Match(_players[i], _players[j]));
 }
 }
 return matches;
 }
}
</code></pre>

Basically I have list of players, and I want to pair them up so that each player will play everyone once. What's the quickest way to find this data?

What's the quickest way to find all possible pairs in list?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

基本上我有一个玩家列表，我想把它们配对，这样每个玩家就可以和每个人玩一次。查找此数据的最快方法是什么？

问在列表中查找所有可能的配对的最快方法是什么？
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在列表中查找所有可能的配对的最快方法是什么？EN