総当たり戦をして結果出力するだけのシェルスクリプト

何かしらの競技を開催する時など、総当たり戦を実施したい時がある。
本記事はシェルスクリプトで総当たりを実装した際の備忘録です。

総当たり戦とは

リーグ戦とも呼ばれる。

https://ja.wikipedia.org/wiki/リーグ戦#総当り戦
リーグ戦（リーグせん）とは、競技大会の大会形式を指す用語。参加者（チーム）同士がそれぞれに対戦を繰り返し、対戦結果を総合した成績によって順位を決定する。特殊な場合を除き、参加者の試合数は一定となる。日本語の定義では総当り戦に限ることが一般的である。

組み合わせの数はN*(N－1)/2となる。（参加者の数をNとする）
例えば、N=6の場合は15通り
例えば、N=10の場合は45通り

処理の流れ

以下の通り。
基本的にプレーヤ一覧を入力として、総当たりを実施して結果を返すのみです。
工夫ポイントとしては、重複する試合は省略しています。（例えばAvsB,BvsAは同じなので省略する）

- １．プレーヤ一覧を取得する
- ２．プレーヤ一覧から、総当たり戦を実施するための組み合わせ一覧表を作成する
- ３．組み合わせ一覧表の順番に総当たり戦をする
- ４．対戦結果の配列から結果表を出力する

プレーヤ一覧は以下のような配列で与えます。

# プレーヤ一覧を取得する                                                                                                                                       
USERS=(
    "testA@master"
    "testB@master"
    "testC@master"
    "testD@master"
    "testE@master"
    "testF@master"
    "testG@master"
    "testH@master"
    "testI@master"
    "testJ@master"
)

処理の全体像

test.sh

#!/bin/sh

# プレーヤ一覧を取得する
PLAYERS=(
    "testA@master" # 0
    "testB@master"
    "testC@master"
    "testD@master"
    "testE@master"
    "testF@master"
    "testG@master"
    "testH@master"
    "testI@master"
    "testJ@master" # N
)

# Debug
function print_debug() {
    echo "--- UserList"
    for user in ${PLAYERS[@]}; do
	echo $user
    done
}

# プレーヤ一覧から、総当たり戦を実施するための組み合わせ一覧表を作成する
COMBINATION_LIST=()
function get_combination_list() {
    echo "--- CombinationList"
    N=`echo ${#PLAYERS[*]}`
    N=`expr ${N} - 1`
    for i in `seq 0 ${N}`; do
	for j in `seq 0 ${N}`; do
	    STR="${i}_${j}"
	#echo ${STR}
	    COMBINATION_LIST+=(${STR})
	done
    done
}

# 対戦する
function do_battle(){
    local PLAYER1_=${1}
    local PLAYER2_=${2}
    #echo "${PLAYER1}, ${PLAYER2}"
    ## とりあえず勝ちを返す
    return 0 # win
    #return 1 # lose
}

# 組み合わせ一覧表の順番に総当たり戦をする
function do_battle_main() {
    #echo ${COMBINATION_LIST[@]}
    for i in ${COMBINATION_LIST[@]}; do

        # 変数を取得
	PLAYER1_NUM=`echo ${i} | cut -d'_' -f1`
	PLAYER2_NUM=`echo ${i} | cut -d'_' -f2`
	PLAYER1=${PLAYERS[${PLAYER1_NUM}]}
	PLAYER2=${PLAYERS[${PLAYER2_NUM}]}
	echo "${PLAYER1_NUM}:${PLAYER1}, ${PLAYER2_NUM}:${PLAYER2}"

        # 対戦不要の組み合わせの場合
        # 結果を取得して対戦はスキップする
	if [ ${PLAYER1_NUM} -ge ${PLAYER2_NUM} ]; then
	    RESULT="-"
	    RESULT_LIST+=(${RESULT})
	    continue
	fi

        # 対戦必要な組み合わせの場合
        # ここで対戦する(PLAYER1 vs PLAYER2) -->
	do_battle "${PLAYER1}" "${PLAYER2}"
	RET=$?
	if [ $RET -eq 0 ]; then
	    RESULT="W"
	else
	    RESULT="L"
	fi
        # <---- ここまで対戦

        # 対戦結果を格納する
	RESULT_LIST+=(${RESULT})
    done
}

# 対戦結果の配列から結果表を出力する
function get_result() {
    # show result list
    #echo ${RESULT_LIST[@]}
    echo "--- Result"
    count=0
    for i in ${COMBINATION_LIST[@]}; do

	PLAYER1_NUM=`echo ${i} | cut -d'_' -f1`
	PLAYER2_NUM=`echo ${i} | cut -d'_' -f2`
	RESULT=${RESULT_LIST[${count}]}

        # 結果を出力
	if [ ${PLAYER1_NUM} -lt ${PLAYER2_NUM} ]; then
	    echo -n "${RESULT},"
	elif [ ${PLAYER1_NUM} -gt ${PLAYER2_NUM} ]; then
            # 既存の結果を再利用(総当たり表の反対側の要素を取得)
	    AA=`expr ${count} / ${#PLAYERS[@]}`
	    BB=`expr ${count} % ${#PLAYERS[@]}`
	    CC=`expr ${BB} \* ${#PLAYERS[@]} + ${AA}`
	    RESULT=${RESULT_LIST[${CC}]}
	    if [ "${RESULT}" == "W" ]; then
		echo -n "L,"
	    else
		echo -n "W,"
	    fi
	else
	    echo -n "-,"
	fi

        # PLAYERS分だけループ処理したら改行する
	count=`expr $count + 1`
	TMP_NUM=`expr $count % ${#PLAYERS[@]}`
	if [ "${TMP_NUM}" == "0" ]; then
	    echo ""
	fi
    done
}

print_debug
get_combination_list
do_battle_main
get_result

実行結果は以下の通り

test.sh

$ bash test.sh
--- UserList
testA@master
testB@master
testC@master
testD@master
testE@master
testF@master
testG@master
testH@master
testI@master
testJ@master
--- Result
-,W,W,W,W,W,W,W,W,W,
L,-,W,W,W,W,W,W,W,W,
L,L,-,W,W,W,W,W,W,W,
L,L,L,-,W,W,W,W,W,W,
L,L,L,L,-,W,W,W,W,W,
L,L,L,L,L,-,W,W,W,W,
L,L,L,L,L,L,-,W,W,W,
L,L,L,L,L,L,L,-,W,W,
L,L,L,L,L,L,L,L,-,W,
L,L,L,L,L,L,L,L,L,-,

do_battleの部分は目的に応じて適宜書き換えればOK

参考