algorithm - リスト内のすべての可能なペアを見つける最も簡単な方法は何ですか？

Question

基本的にはプレイヤーのリストを持っているので、ペアにして各プレイヤーが全員を一度プレイできるようにしたいと思います。このデータを見つける最も簡単な方法は何ですか？

Answer 1

プレーヤーがリストに2回表示されないと仮定すると、ダブルforループは非常に高速です。

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

Answer 2

このようなトーナメントスケジュールは、ラウンドロビンと呼ばれることがよくあります。ウィキペディアには、可能なスケジューリングアルゴリズムの例もあります。

Answer 3

パフォーマンスを比較するために、2つの実装をまとめました。非常に単純なバージョン1は、バージョン2よりも約50％低速です。それは、高速なものが存在しないということではありません。

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++)
            {
                v1 = V1();
            }
            Console.WriteLine(v1);
            Console.WriteLine(sw.Elapsed);
        }

        {
            var v2 = V2();
            var sw = Stopwatch.StartNew();
            for (int i = 0; i < count; i++)
            {
                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++)
        {
            for (int j = i + 1; j < _players.Count; j++)
            {
                matches.Add(new Match(_players[i], _players[j]));
            }
        }
        return matches;
    }
}

Answer 4

単純な分割統治アルゴリズム：

1. 2人しかいない場合：ペアにして返却します。

2. さもないと：

   1. グループを同じサイズの2つのグループに分割します。
   2. このアルゴリズムを再帰的に使用して、各グループのすべてのペアリングを検索します。

   3. 2つのリストに参加してください。

      たとえば[[(a,b)]]、に[[(c,d)]]なり[[(a,b),(c,d)]]ます。

   4. グループ2を回転させて、2つのグループのペアを見つけます。

      例えば[[(a,c),(b,d)],[(a,d),(b,c)]]

   5. リターン(3)+(4)

このアルゴリズムは時間内に実行されます。これは、ペアリングのラウンドをO(n^2)生成するため、最適です。(n-1)n/2

8人のプレーヤーの場合、7ラウンドを取得します。

[(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)]