JavaScript 优化

Question

我正在使用 JavaScript 从给定的球员列表中计算出羽毛球 double 比赛的所有组合。每个玩家都与其他人组队。

EG。如果我有以下球员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++;
                    }
                }
            }
        }
    }
}

提前致谢。

杰森。

Answer 1

好吧，经过一番深思熟虑，我想出了这个(见下文)。它仍然不是很出色，但速度要快得多。

首先，我发现我不需要在第一个 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++;
                    }
                }
            }
        }
    }
}

干杯，杰森。