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 数组的末尾，因为这些排列已经解决了。其次，我在第二个 FOR 循环中增加了起始值，同样因为这些排列已经计算出来了。然后我在第三个和第四个 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 回答