JavaScript優化

Question

我正在使用JavaScript來計算給定列表中的羽毛球雙打比賽的所有組合。每個球員與其他人合作。

EG。 如果我有以下球員a，b，c & d。它們的組合可以是：

一個& B）（VÇ& d

一個&（C V）b & d

一個& d V b &Ç

我使用下面的代碼，這我寫信去做這項工作，但效率不高。它通過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++; 
        } 
       } 
      } 
     } 
    } 
} 

在此先感謝。

Jason。

Answer 1

經過一番艱難的思考後，我想出了這個（見下文）。它仍然不是很出色，但速度更快。

首先我得出結論，我不需要去第一個FOR循環中的Players數組的末尾，因爲這些排列已經算出來了。其次，我在第二個FOR循環中增加了起始值，這是因爲這些排列已經算出來了。然後我在第三和第四個FOR循環中做了類似的事情。

如果我可以避免長中頻比較，那麼我可以加快更多的事情！我還添加了名稱而不是字符來演示我試圖實現的目標。

歡迎任何想法。

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++; 
        } 
       } 
      } 
     } 
    } 
} 

乾杯，賈森。