仕事の関係でスイス式トーナメントという競技形式に触れましたので、対戦相手の組み合わせアルゴリズムを記録しておきます。
スイス式トーナメントには 2 つのルールがあります。
- スコアが近い相手を選んで対戦すること。
- 重複した対戦は行わないこと。
以下に書かれたアルゴリズムです:
type player struct {
Id int64
Score int64
Opponent map[int64]struct{} // 過去に対戦した相手
}
// pickTablePlayer はスイス式トーナメントの対戦相手を選ぶ関数です
func pickTablePlayer(players []int64, playerOpponentMap map[int64]map[int64]struct{}) ([]int64, bool) {
if len(players) < 2 {
return players, true
}
whitePlayer := players[0]
opponentMap, _ := playerOpponentMap[whitePlayer]
for i := range players {
if i != 0 {
// すでに対戦しているかどうかを判断する
if _, has := opponentMap[players[i]]; !has {
// 選択する
res := make([]int64, 2)
res[0] = whitePlayer
res[1] = players[i]
// 残りのデータを組み立てる
var nextRound []int64
nextRound = append(nextRound, players[1:i]...)
nextRound = append(nextRound, players[i+1:]...)
pick, ok := pickTablePlayer(nextRound, playerOpponentMap) // 次のラウンドの対戦相手を選ぶ
if ok {
return append(res, pick...), true // 成功した場合、結果を返す
}
}
}
}
return nil, false // 失敗した場合、上位で再計算する
}
func CreateSwissRound(players []player) (playerBattleList [][]int64, emptyPlayer int64, ok bool) {
ok = true
// 空きプレイヤーを判断する
total := len(players)
if total%2 != 0 {
emptyPlayer = players[total-1].Id
players = players[:total]
}
// データ構造を変換する
var playerIds []int64
var playerOpponentMap = make(map[int64]map[int64]struct{})
for _, v := range players {
playerIds = append(playerIds, v.Id)
if _, has := playerOpponentMap[v.Id]; !has {
playerOpponentMap[v.Id] = v.Opponent
}
}
// 対戦相手の順番を計算する
playerList, ok := pickTablePlayer(playerIds, playerOpponentMap)
if !ok {
return playerBattleList, emptyPlayer, ok
}
// 二次元配列に変換する
for i := 0; i < len(playerList)/2; i++ {
playerBattleList = append(playerBattleList, []int64{
playerList[i*2],
playerList[i*2+1],
})
}
return
}