総当たり戦の日程作成 in JavaScript DouKaku?

総当たり戦の日程作成

任意の偶数Nのチームの総当たり戦を最短日数（N-1日）で行う場合の日程表を１つ作成してください。

解はひとつではない場合もあります。
もし、余力があれば、全ての可能性も求めてください。

これは、スポーツスケジューリングと言う分野の問題で、数学的には、カークマンの問題と言うのが近いようです。

例えば、４チームであれば、

1-2 3-4
1-3 2-4
1-4 2-3

６チームであれば

1-2 3-4 5-6 
1-3 2-5 4-6 
1-4 2-6 3-5 
1-5 2-4 3-6 
1-6 2-3 4-5

が解のひとつです。

see: カークマンの組分け

post comment

Posted feedbacks - JavaScript

結果：
1-2 6-3 5-4
1-6 5-2 4-3
1-5 4-6 3-2
1-4 3-5 2-6
1-3 2-4 6-5

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>総当たり戦の日程作成</title>
<script type="text/javascript">
/**
 * 配列を回転する
 */
function rotateArray(aOld) {
    var iLast = aOld.length - 1;
    return [aOld[iLast]].concat(aOld.slice(0, iLast));
}

/**
 * 総当たり戦のスケジュール作成
 */
function getLeageSchedule(aTeam) {
    var aResult = [];
    if(aTeam.length%2 != 0) {
        aTeam.push('');
    }
    var vFirst = aTeam[0];
    var aCycle = aTeam.slice(1);
    var iHalfLen = aTeam.length/2;
    for(var i=0; i<aCycle.length; i++) {
        var aLeft = [vFirst].concat(aCycle.slice(iHalfLen).reverse());
        var aRight = aCycle.slice(0, iHalfLen);
        var aGames = [];
        for(var j=0; j<aLeft.length; j++) {
            if(aLeft[j] != '' && aRight[j] != '') {
                aGames.push(aLeft[j] + '-' + aRight[j]);
            }
        }
        aResult.push(aGames);
        aCycle = rotateArray(aCycle);
    }
    return aResult;
}

//テスト
var aTeam = [1,2,3,4,5,6];
var aSchedule = getLeageSchedule(aTeam);
for(var i=0; i<aSchedule.length; i++) {
    document.write(aSchedule[i].join('  ') + '<br/>');
}
</script>
</head>
<body>
</body>
</html>

DouKaku?

総当たり戦の日程作成

Posted feedbacks - JavaScript

Index

Feed

Other

Link

Pathtraq