1つのプロジェクトでは、複数のチーム間の試合計画を計算する必要があります。
要件：
たとえば、4teams（A、B、C、D）を使用して、これを計算できるようにしたいと思います。
ラウンド1
ラウンド2
ラウンド3
問題は、ラウンドXにはいくつかの選択肢があり、ラウンドX + 1での試合を不可能にすることです（チームはすでに他のチームと対戦しています）。
いくつかのバックトラッキング手法を使用できると思いますが、このためのアルゴリズムがあるかどうかを探していますか？
これはc＃で実装されます。
これを行う方法について何か考えがありますか？
実際、答えはコメントで提供されているリンク Olivierにあります。より具体的には、この答え。
そして、それはあまり明白ではないことを除いて、ラウンドの概念を処理します。そのコードでTuple<string, string>は、aは試合（2つのチーム名を含むアイテム）をList<Tuple<string, string>>表し、aはラウンド（試合のコレクション）を表します。
このコードは、ラウンドのコレクションを。の形式で返しますList<List<Tuple<string, string>>>。
との概念がコード内でより明確になるようにMatch、コードを少しリファクタリングしました。Round
MatchおよびRoundクラスは次のとおりです。
public class Match
{
public string Team1 { get; set; }
public string Team2 { get; set; }
public Match(string team1, string team2)
{
Team1 = team1;
Team2 = team2;
}
public override string ToString()
{
return string.Format("{0} vs {1}", Team1, Team2);
}
}
public class Round
{
public List<Match> Matches { get; private set; }
public Round()
{
Matches = new List<Match>();
}
public override string ToString()
{
return String.Join(Environment.NewLine, Matches) + Environment.NewLine;
}
}
そして、これが魔法を実行するコードです（クレジットはNaggに送られます）：
public static List<Round> ComputeFixtures(List<string> listTeam)
{
var result = new List<Round>();
var numberOfRounds = (listTeam.Count - 1);
var numberOfMatchesInARound = listTeam.Count / 2;
var teams = new List<string>();
teams.AddRange(listTeam.Skip(numberOfMatchesInARound).Take(numberOfMatchesInARound));
teams.AddRange(listTeam.Skip(1).Take(numberOfMatchesInARound - 1).ToArray().Reverse());
var numberOfTeams = teams.Count;
for (var roundNumber = 0; roundNumber < numberOfRounds; roundNumber++)
{
var round = new Round();
var teamIdx = roundNumber % numberOfTeams;
round.Matches.Add(new Match(teams[teamIdx], listTeam[0]));
for (var idx = 1; idx < numberOfMatchesInARound; idx++)
{
var firstTeamIndex = (roundNumber + idx) % numberOfTeams;
var secondTeamIndex = (roundNumber + numberOfTeams - idx) % numberOfTeams;
round.Matches.Add(new Match(teams[firstTeamIndex], teams[secondTeamIndex]));
}
result.Add(round);
}
return result;
}
このコードのオンライン実行サンプルは次のとおりです。
私はあなたがこれを間違った方法で取っていると思います。前のラウンドに基づいてペアリングを各ラウンドで計算するのではなく、単純なdouble forループを使用して可能なすべてのペアリングを作成することから始め、次にラウンドごとにゲームをランダムに分散します。
すべてのプレーヤーがまったく同じ数のゲームをプレイするため、そのような配布が存在する必要があります。
ラウンドロビンを試してください。これは、プロセス間でタイムスロットを共有するための単純なスケジューリングアルゴリズムですが、この問題はどういうわけか私にそれを思い出させます。
編集
これがラウンドロビントーナメントの実装です。ODDのチーム数がある場合は、ダミーチームを挿入する必要があります。そうしないと、対戦相手のいないチームが存在します。ラウンド数は偶数なので、合計ラウンド数は（NumberOfTeams-1）です。最初に、最初のラウンドを設定しました。
ABCDEFGH
HGFEDCBA
つまり、チームA-H、チームB-Gなどです。
これからは、たとえばAなどの1つのチームを固定します。次に、A_Sideチームを2番目の位置から右にシフトします。最後のチームはポジション2になります（ABCDEFGHはAHBCDEFGになります）。（楽しみのために）rotate_A_side（）再帰メソッドを参照してください。
B_Sidesの半分が左にシフトされます。これにより、HGFED-GFEDになります。
チームの選択は対称的であるため（AはHでプレイし、次にHはAでプレイします）、B_Sideの上半分はA_Sideの下位チームの逆コピーです。したがって、DCBAはCBHAになります）。rotate_B_side（）を参照してください。
したがって、ラウンド2は次のとおりです。
HBCDEFG _
GFED CBHA
すべてのラウンドを行うには、前述のシフト手順を繰り返すだけです。NextRound（）を参照してください
アルゴリズムを実装するac＃クラスは次のとおりです。
class Teams
{
private int[] A_Side;
private int[] B_Side;
public int[,] PlayingCounter;
public int RoundCounter = 1;
public bool DummyTeam = false; // ODD number of teams -> one team will no be able to play.
public bool NextRoundExists
{
get
{
return (RoundCounter < B_Side.Length-1);
}
}
public Teams(int NumberOfTeams)
{
if (NumberOfTeams % 2 != 0)
{
NumberOfTeams++; DummyTeam = true;
}
A_Side = new int[NumberOfTeams];
B_Side = new int[NumberOfTeams];
PlayingCounter = new int[NumberOfTeams,NumberOfTeams]; // Counting to see if alg is correct
int x,y;
for (x=0; x<NumberOfTeams; x++)
{
A_Side[x] = x + 1;
B_Side[NumberOfTeams-x-1]=x+1;
for (y=0;y<NumberOfTeams;y++)
{
PlayingCounter[x,y] = 0;
}
}
}
private void rotate_A_Side(int AtPos)
{
if (AtPos == 1)
{
int iO = A_Side[A_Side.Length - 1];
rotate_A_Side(AtPos+1);
A_Side[1] = iO;
}
else
{
if (AtPos < A_Side.Length - 1) { rotate_A_Side(AtPos + 1); }
A_Side[AtPos] = A_Side[AtPos - 1];
}
}
public void rotate_B_Side()
{
int i;
for (i = 0; i<B_Side.Length/2 ; i++)
{
B_Side[i] = B_Side[i + 1];
}
for (i = B_Side.Length / 2; i < B_Side.Length; i++)
{
B_Side[i] = A_Side[B_Side.Length/2 - (i -B_Side.Length/2 + 1) ];
}
}
public bool NextRound()
{
if (NextRoundExists)
{
RoundCounter++; // Next round
rotate_A_Side(1); // A side rotation
rotate_B_Side(); // B side rotation
LogRound(); // Update counters
return true;
}
else return false;
}
public void LogRound()
{
for (int x = 0; x < A_Side.Length; x++)
{
PlayingCounter[A_Side[x]-1, B_Side[x]-1]++;
PlayingCounter[B_Side[x]-1, A_Side[x]-1]++;
}
}
public string GetCounters()
{
string return_value = "";
for (int y = 0; y < A_Side.Length; y++)
{
for (int x = 0; x < A_Side.Length; x++)
{
return_value += String.Format(" {0:D3}", PlayingCounter[y, x]);
}
return_value += System.Environment.NewLine;
}
return return_value;
}
public string GetCurrentRound()
{
string Round = "Round #" + RoundCounter.ToString() + " ";
for (int x = 0; x < B_Side.Length; x++)
{
Round += String.Format("Team {0} - Team {1};", A_Side[x], B_Side[x]);
}
return Round;
}
}
コードから、次のように使用できます。
Teams Rounds = new Teams(22);
if (Rounds.DummyTeam) {
// Anything to do if nober of teams is odd?
}
Rounds.LogRound(); // DEBUG - you can check number of matches ;-)
while (Rounds.NextRoundExists) // While we have next round...
{
Rounds.NextRound(); // ... generate the next
// round (team assignment)
// Your can tack using: Rounds.GetCurrentRound()
}
// If you want to see the number of matches, call Rounds.GetCounters();
6チームから次の出力が得られました。
ラウンド＃1 AF; なれ ; CD ; DC; EB; FA;
ラウンド＃2 AE; FD; 紀元前; CB; DF; EA;
ラウンド＃3 AD; EC; FB; BF; CE; DA;
ラウンド＃4 AC; DB; EF; FE; BD; CA;
ラウンド＃5 AB; CF; DE; ED; FC; BA;
チーム1をAなどに置き換えました。
rotate_B_Side（）を改良する必要があります。これは簡単なアプローチです。
簡単な方法を使用して、簡単に説明します
これにより、少し「硬い」ように見えるゲームの配布が発生します。
schedule_tournament(new List<string> { "A", "B", "C" });
schedule_tournament(new List<string> { "A", "B", "C", "D", });
schedule_tournament(new List<string> { "A", "B", "C", "D", "E" });
schedule_tournament(new List<string> { "A", "B", "C", "D", "E", "F" });
schedule_tournament(new List<string> { "A", "B", "C", "D", "E", "F", "G" });
...
private void schedule_tournament(List<string> teams)
{
List<string> games = new List<string>();
List<string> rounds = new List<string>();
// get all possible games
for (int i = 0; i < teams.Count; i++)
{
for (int j = i + 1; j < teams.Count; j++)
{
string game_name = string.Format("{0}{1}", teams[i], teams[j]);
if (!games.Contains(game_name)) games.Add(game_name);
}
}
// allocate games to rounds
for (int i = 0; i < games.Count; i++)
{
bool allocated = false;
for (int j = 0; j < rounds.Count; j++)
{
string team_1 = games[i].Substring(0, 1);
string team_2 = games[i].Substring(1, 1);
if (!rounds[j].Contains(team_1) && !rounds[j].Contains(team_2))
{
rounds[j] += " - " + games[i];
allocated = true;
break;
}
}
if (!allocated)
{
rounds.Add(games[i]);
}
}
Console.WriteLine("{0} teams, play {1} games in {2} rounds", teams.Count, games.Count, rounds.Count);
for (int i = 0; i < rounds.Count; i++) Console.WriteLine("Round {0}: {1}", i + 1, rounds[i]);
}
これの出力は次のとおりです。
3 teams, play 3 games in 3 rounds
Round 1: AB
Round 2: AC
Round 3: BC
4 teams, play 6 games in 3 rounds
Round 1: AB - CD
Round 2: AC - BD
Round 3: AD - BC
5 teams, play 10 games in 7 rounds
Round 1: AB - CD
Round 2: AC - BD
Round 3: AD - BC
Round 4: AE
Round 5: BE
Round 6: CE
Round 7: DE
6 teams, play 15 games in 7 rounds
Round 1: AB - CD - EF
Round 2: AC - BD
Round 3: AD - BC
Round 4: AE - BF
Round 5: AF - BE
Round 6: CE - DF
Round 7: CF - DE
7 teams, play 21 games in 7 rounds
Round 1: AB - CD - EF
Round 2: AC - BD - EG
Round 3: AD - BC - FG
Round 4: AE - BF - CG
Round 5: AF - BE - DG
Round 6: AG - CE - DF
Round 7: BG - CF - DE