JavaScript Optimisation
- by Jayie
I am using JavaScript to work out all the combinations of badminton doubles matches from a given list of players. Each player teams up with everyone else.
EG.
If I have the following players a, b, c & d. Their combinations can be:
a & b V c & d
a & c V b & d
a & d V b & c
I am using the code below, which I wrote to do the job, but it's a little inefficient. It loops through the PLAYERS array 4 times finding every single combination (including impossible ones). It then sorts the game out into alphabetical order and stores it in the GAMES array if it doesn't already exist. I can then use the first half of the GAMES array to list all game combinations.
The trouble is if I have any more than 8 players it runs really slowly because the combination growth is exponential.
Does anyone know a better way or algorithm I could use? The more I think about it the more my brain hurts!
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++;
}
}
}
}
}
}
Thanks in advance.
Jason.
