Вы хотите combinations , а не перестановок. Используя стандартную формулу, мы знаем, что есть 252 возможных комбинации из 10 игроков, взятых по 5 за раз. Есть очень простой способ генерировать комбинации, которые vib упоминается в его ответе, и я расширяюсь здесь.
Всего 10 игроков. Если вы рассматриваете игроков как 10-битное число, каждый игрок соответствует бит в этом номере. Любое 10-битное число, имеющее ровно 5 бит, является действительной командой. Таким образом, 0101010101 является действительной командой, но 0011000100 не является действительной командой.
Кроме того, любая действительная команда имеет ровно одну противоположную команду. То есть, учитывая 10 игроков и команду из 5 человек, тогда есть только 5 других людей, чтобы выбрать. Поэтому команда 0101010101 в паре с командой 1010101010.
2^10 - 1024. Таким образом, мы должны только проверить 1024 возможных комбинаций. На самом деле нам нужно проверить только 512, потому что мы знаем, что любая команда с номером выше 511 будет иметь на нем наивысший пронумерованный игрок (т. Е. Последний бит установлен), и любое число меньше 512 не будет иметь этого игрока на нем.
Таким образом, идея есть, для каждого номера меньше, чем 512:
- если не пяти бит в номере, то перейдите к следующим
- инвертировать число.Это даст вам противостоящую команду
- Вычислить оценки для команды и команды соперника
Простой C# код, чтобы сделать это:
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);
}
}
}
Вы должны будете предоставить код, который извлекает номера игроков из номера команды. Это просто вопрос вывода номера бит из заданных битов. Вы можете изменить код вычисления баллов для этого.
Обратите внимание, что код, который я использовал для определения количества бит, не является оптимальным. Но это работает. Если вы хотите более быстрый способ, ознакомьтесь с BitHacks page, который имеет много разных способов.
Wow, awesome. Спасибо. –
Джим, я реализовал его здесь: https://github.com/paralin/BalanceAlgorithm/ - у вас были некоторые критические ошибки в вашем коде (используя '-' вместо' ~ 'и целых чисел со знаком), которые вы можете исправить в ваш ответ. Еще раз спасибо! –
@ChristianStewart: Мой код имеет '~', где он принадлежит. Я понимаю, что вы подразумеваете под целыми знаками, хотя алгоритм должен работать. Противоположные номера команд будут отрицательными, что является довольно выигрышным.Это легко зафиксировать, написав 'var opposingTeam = (~ team) & 0x3FF;' В любом случае, я рад, что вы его работали. –