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

Question

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?

Poulin

Answer 1

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

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

Kelcie

exactly what I came yup with a second ago. Thanks! – Poulin

This seems like the most efficient to me. Micah wants every possible pair, and you're not doing anything extra. – Benignant

Out of curiosity, what would be more efficient? – Ingoing

I don't assume this works, since it doesn't generate any rounds. – Galaxy

@Ingoing i glanced at the round-robin article that @Nikita Rybak linked, it seemed slightly better than this, but on second thought, perhaps not? I edited the answer to remove the claim on lack of efficiency – Kelcie

@Thomas Ahle I believe you misread the question. @Poulin did not ask for rounds. I see your solution shows them, but they are not specifically requested by the OP. – Kelcie

@Kelcie From his accepting your answer, it seams like you are right :) – Galaxy

What happens if the playerList.count is say 10^9 ?? this seems very slow in tat case.. any other optimized solution? – Babel

Answer 2

Such tournament schedule is often called round-robin. In wikipedia, there's also an example of possible scheduling algorithm.

Gravitative

Would a Cartesian product be the same thing? – Ingoing

@Ingoing I might have misunderstand the question, but the point of this algorithm is to fit all those pairs into the smallest possible number of rounds. If you select which pairs play at each round randomly, you'll end up with the number of rounds well above optimal. Just compiling list of pairs (like vlad proposed) is easy, but solves different problem. – Gravitative

I guess not - since a true Cartesian product will return pairings from a simple "players" table in SQL where "John - John" is a pairing (obviously not desired) and "John - Sally" and "Sally - John" are also returned (also not desired). – Ingoing

This seams a bit tedious to implement, since it requires rotating an array. – Galaxy

@Thomas This algorithm and the one by vlad solve different problems. Please see my comment above. – Gravitative

@Nikita I agree vlad has solved a different problem, but the rotation algorithm is just a bit tedious. I guess it's a matter of taste though, and perhaps of they way your data is already stored. – Galaxy

@Thomas If you have better algorithm achieving the same result, I'd be interested to know :) And rotating array by one position is not that difficult. – Gravitative

Answer 3

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.

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;
    }
}

Flexure

Answer 4

A simple divide and conquer algorithm:

1. If there are only two people: Pair them and return them.

2. Otherwise:

   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.

      E.g. [[(a,b)]] and [[(c,d)]] becomes [[(a,b),(c,d)]].

   4. Find pairs across of the two groups, by rotating group two.

      E.g. [[(a,c),(b,d)],[(a,d),(b,c)]]

   5. Return (3) + (4)

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

For eight players you would get 7 rounds:

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

Galaxy

This works really well if the length of the group is a power of two. Three pairs are not quite so simple, for example, though easy to brute-force. – Teleutospore

@ken: How would you match games into rounds with brute force? How fast would it be? – Galaxy

brute force would be terribly slow for large groups. As an exercise, we did a group of six which only took a few minutes. A group of 30 would take considerably longer. – Teleutospore