Permutations of combinations of two groups

Question

In C#, I am attempting to write an algorithm to balance two teams given integer player ratings for each of the players.

The data set looks like this:

Player 1:  1330
Player 2:  1213
Player 3:  1391
Player 4:  1192
Player 5:  1261
Player 6:  1273
Player 7:  1178
Player 8:  1380
Player 8:  1200
Player 10: 1252

I'd like to build two sets of five players, where the total rating difference of both teams is as small as possible, for a fair match.

Now to do this I'd like to generate all team permutations (each permutation is two teams of 5 players). But all c# permutation examples are for combining things like power sets, not teams.

What's the most efficient way to do this?

Answer 1

You want combinations, not permutations. Using the standard formula we know that there are 252 possible combinations of 10 players taken 5 at a time. There's a really easy way to generate the combinations, which vib mentioned in his answer and I expand on here.

There are 10 players. If you view the players as a 10-bit number, then each player corresponds to a bit in that number. Any 10-bit number that has exactly 5 bits set is a valid team. So 0101010101 is a valid team, but 0011000100 is not a valid team.

In addition, any valid team has exactly one opposing team. That is, given 10 players and a team of 5 members, then there are only 5 other people to select. So team 0101010101 is paired with team 1010101010.

2^10 is 1024. So we only have to check 1024 possible combinations. Actually, we only have to check 512 because we know that any team with a number above 511 will have the highest numbered player on it (i.e. the last bit is set), and any number less than 512 will not have that player on it.

So the idea is, for each number less than 512:

1. if there are not five bits set in the number, go to the next one
2. invert the number. This will give you the opposing team
3. Calculate the ratings for the team and the opposing team

Simple C# code to do that:

private readonly int[] _playerRatings = new[] {1330, 1213, 1391, 1192, 1261, 1273, 1178, 1380, 1200, 1252};

private int CalculateTeamScore(int team)
{
    var score = 0;
    for (var i = 0; i < 10; ++i)
    {
        if ((team & 1) == 1)
        {
            score += _playerRatings[i];
        }
        team >>= 1;
    }
    return score;
}

private bool IsValidTeam(int team)
{
    // determine how many bits are set, and return true if the result is 5
    // This is the slow way, but it works.
    var count = 0;
    for (var i = 0; i < 10; ++i)
    {
        if ((team & 1) == 1)
        {
            ++count;
        }
        team >>= 1;
    }
    return (count == 5);
}

public void Test()
{
    // There are 10 players. You want 5-player teams.

    // Assign each player a bit position in a 10-bit number.
    // 2^10 is 1024.
    // Start counting at 0, and whenever you see a number that has 5 bits set,
    // you have a valid 5-player team.
    // If you invert the bits, you get the opposing team.

    // You only have to count up to 511 (2^9 - 1), because any team after that
    // will already have been found as the opposing team.

    for (var team = 0; team < 512; ++team)
    {
        if (IsValidTeam(team))
        {
            var opposingTeam = ~team;
            var teamScore = CalculateTeamScore(team);
            var opposingTeamScore = CalculateTeamScore(opposingTeam);
            var scoreDiff = Math.Abs(teamScore - opposingTeamScore);
            Console.WriteLine("{0}:{1} - {2}:{3} - Diff = {4}.", 
                team, teamScore, opposingTeam, opposingTeamScore, scoreDiff);
        }
    }
}

You'll have to provide the code that extracts the player numbers from the team number. It's a simple matter of outputting the bit number from the set bits. You can modify the score computation code to do that.

Note that the code I used to find how many bits are set is not at all optimum. But it works. If you want a faster way, check out the BitHacks page, which has many different ways.