1

JavaScript を使用して、指定されたプレーヤーのリストからバドミントン ダブルスの試合のすべての組み合わせを計算しています。各プレイヤーは他のプレイヤーとチームを組みます。

例えば。次のプレーヤー a、b、c、d がいるとします。それらの組み合わせは次のとおりです。

a & b V c & d

a & c V b & d

a & d V b & c

私は仕事をするために書いた以下のコードを使用していますが、少し非効率的です。PLAYERS 配列を 4 回ループして、すべての組み合わせ (不可能なものを含む) を見つけます。次に、ゲームをアルファベット順に並べ替え、まだ存在しない場合は GAMES 配列に格納します。次に、GAMES 配列の前半を使用して、すべてのゲームの組み合わせを一覧表示します。

問題は、8 人以上のプレイヤーがいる場合、コンビネーションの成長が指数関数的であるため、実行が非常に遅くなることです。

誰かが私が使用できるより良い方法またはアルゴリズムを知っていますか? 考えれば考えるほど頭が痛くなる！

var PLAYERS = ["a", "b", "c", "d", "e", "f", "g"];
var GAMES = [];

var p1, p2, p3, p4, i1, i2, i3, i4, entry, found, i;
var pos = 0;
var TEAM1 = [];
var TEAM2 = [];

// loop through players 4 times to get all combinations
for (i1 = 0; i1 < PLAYERS.length; i1++)
{
    p1 = PLAYERS[i1];
    for (i2 = 0; i2 < PLAYERS.length; i2++)
    {
        p2 = PLAYERS[i2];
        for (i3 = 0; i3 < PLAYERS.length; i3++)
        {
            p3 = PLAYERS[i3];
            for (i4 = 0; i4 < PLAYERS.length; i4++)
            {
                p4 = PLAYERS[i4];

                if ((p1 != p2 && p1 != p3 && p1 != p4) &&
                   (p2 != p1 && p2 != p3 && p2 != p4) &&
                   (p3 != p1 && p3 != p2 && p3 != p4) &&
                   (p4 != p1 && p4 != p2 && p4 != p3))
                {
                    // sort teams into alphabetical order (so we can compare them easily later)
                    TEAM1[0] = p1;
                    TEAM1[1] = p2;
                    TEAM2[0] = p3;
                    TEAM2[1] = p4;
                    TEAM1.sort();
                    TEAM2.sort();

                    // work out the game and search the array to see if it already exists
                    entry = TEAM1[0] + " & " + TEAM1[1] + " v " + TEAM2[0] + " & " + TEAM2[1];
                    found = false;
                    for (i=0; i < GAMES.length; i++)
                    {
                        if (entry == GAMES[i]) found = true;
                    }

                    // if the game is unique then store it
                    if (!found)
                    {
                        GAMES[pos] = entry;
                        document.write((pos+1) + ": " + GAMES[pos] + "<br>");
                        pos++;
                    }
                }
            }
        }
    }
}

前もって感謝します。

ジェイソン。

4

1 に答える 1

0

よく考えた後、私はこれを思いつきました（以下を参照）。それはまだ華麗ではありませんが、はるかに高速です。

最初に、最初の FOR ループで Players 配列の最後に移動する必要がないことがわかりました。これらの順列は既に解決されているからです。次に、2 番目の FOR ループの開始値を増やしました。これらの順列は既に解決されているためです。次に、3 番目と 4 番目の FOR ループで同様のことを行いました。

長い IF 比較を回避できれば、処理をさらに高速化できます。また、達成しようとしていることを示すために、文字の代わりに名前を追加しました。

その他のアイデアは大歓迎です。

var PLAYERS = ["eric", "bob", "jim", "john", "dave", "steve", "fred"];
var GAMES = [];

var p1, p2, p3, p4, i1, i2, i3, i4, entry, found, i;
var pos = 0;
var TEAM1 = [];
var TEAM2 = [];

// loop through players 4 times to get all combinations
for (i1 = 0; i1 < (PLAYERS.length - 1); i1++)
{
    p1 = PLAYERS[i1];
    for (i2 = 1; i2 < PLAYERS.length; i2++)
    {
        p2 = PLAYERS[i2];
        for (i3 = 1; i3 < (PLAYERS.length - 1); i3++)
        {
            p3 = PLAYERS[i3];
            for (i4 = 2; i4 < PLAYERS.length; i4++)
            {
                p4 = PLAYERS[i4];

                if ((p1 != p2 && p1 != p3 && p1 != p4) &&
                   (p2 != p1 && p2 != p3 && p2 != p4) &&
                   (p3 != p1 && p3 != p2 && p3 != p4) &&
                   (p4 != p1 && p4 != p2 && p4 != p3))
                {
                    // sort teams into alphabetical order (so we can compare them easily later)
                    TEAM1[0] = p1;
                    TEAM1[1] = p2;
                    TEAM2[0] = p3;
                    TEAM2[1] = p4;
                    TEAM1.sort();
                    TEAM2.sort();

                    // work out the game and search the array to see if it already exists
                    entry = TEAM1[0] + " & " + TEAM1[1] + " v " + TEAM2[0] + " & " + TEAM2[1];
                    found = false;
                    for (i=0; i < GAMES.length; i++)
                    {
                        if (entry == GAMES[i]) found = true;
                    }

                    // if the game is unique then store it
                    if (!found)
                    {
                        GAMES[pos] = entry;
                        document.write((pos+1) + ": " + GAMES[pos] + "<br>");
                        pos++;
                    }
                }
            }
        }
    }
}

乾杯、ジェイソン。

于 2013-10-18T09:52:30.940 に答える