1

Trying to generate n sets of unique pairs from an array without repeating items, creating a set of pairs that uses all items in the array only once.

I am working with javascript. I have an array of say 10 items I need to generate the following:

The code I am using gets tripped up like this:

arrPlayers = [1,2,3,4,5,6,7,8,9,10]

matchups-week-1 = [[1,2],[3,4],[5,6],[7,8],[9,10]]

matchups-week-2 = [[1,3],[2,4],[5,7],[6,8],[ ooops!! ] can't do [9,10] again so this set won't work.

You see how the 9,10 pair paints the code into a corner? You can only produce 4 pairs because 9,10 is not unique.

I thought this would be easy to work out but I am stuck. Any ideas on code that would not paint itself into this "set of 4" corner?

The code I am using. ...admittedly I am grasping at straws. That's why I am asking the question.

function CreateMatchups(player_ids){
    //Create array of PLAYER IDs where checkbox = checked
    arrPlayers = player_ids.split(", ");
    arrOpponents = arrPlayers;
    arrPrevUsed = GetPrevUsedPairs();
    var arrUsed = [];
    var arrTempMatchups = [];

    var intNumPlayers = arrPlayers.length;
    var blnOddNumberOfPlayers = isOdd(intNumPlayers);

    if(blnOddNumberOfPlayers){
        arrPlayers.push(9999); //bogus id for placeholder player - fix this
    }
    for (var i = 0; i < arrPlayers.length; i++) { 
        player_id = arrPlayers[i];
        if(!arrUsed.contains(player_id)){
            for (var j = 0; j < arrOpponents.length; j++) { 
                opponent_id = arrOpponents[j];
                if((!arrUsed.contains(opponent_id)) && (!arrUsed.contains(player_id)) && (player_id != opponent_id)){
                    matchup = player_id + "vs" + opponent_id;
                    if(!arrPrevUsed.contains(matchup)) {
                        arrTempMatchups.push(matchup);
                        arrUsed.push(player_id);
                        arrUsed.push(opponent_id);
                    }
                }
            }
        }
    }
    return arrTempMatchups;

    }
rgalpin
  • 137
  • 1
  • 13
  • I don't understand how they match. Is this an "odd" and "even" thing? – John Mar 27 '16 at 23:57
  • I recommend posting the code you're using to show what you have tried. – mugabits Mar 27 '16 at 23:59
  • All the pairs must be unique. [9,10] can only appear once in the entire result. – rgalpin Mar 27 '16 at 23:59
  • And how many pairs do you need at last? Or is it the goal to find out how many pairs are possible!? – John Mar 28 '16 at 00:01
  • In the final solution I will also need to check each result against previous matchups held in a database so I plan to iterate through the result set until I have a set that is unique not only to itself but also tested against pairs found in database records. – rgalpin Mar 28 '16 at 00:05
  • @John re: How many pairs? I want to return all possible SETS of pairs. Each set must contain n elements. n being array.length * .5 because if there are say 10 players I need 5 pairs. – rgalpin Mar 28 '16 at 00:59
  • [This explanation](http://www.jdawiseman.com/papers/tournaments/all-play-all/all-play-all.html) of tournament designs of All-Play-All might help you. And [here](http://www.jdawiseman.com/papers/tournaments/all-play-all/apa_10.html) is the particular arrangement for 10 competitors. – R. Schifini Mar 28 '16 at 01:23
  • Interesting. The piece that will make this application most beneficial will be when a player cancels and the schedule needs to be reworked. Doing it by hand without creating dupes is a nightmare. Creating a programmatic way to adjust on the fly for last minute cancellations. For that, I need some kind of algorithm that can be applied across various scenarios of players in the pool. – rgalpin Mar 28 '16 at 01:50

2 Answers2

3

It's called permutation.

function pairwise(list) {
  if (list.length < 2) { return []; }
  var first = list[0],
      rest  = list.slice(1),
      pairs = rest.map(function (x) { return [first, x]; });
  return pairs.concat(pairwise(rest));
}

var result = pairwise(['1','2','3','4','5','6','7','8','9','10']);

document.write(JSON.stringify(result));
John
  • 760
  • 5
  • 12
  • I am getting an error: Object doesn't support this property or method on the this line: pairs = rest.map(function (x) { return [first, x]; }); – rgalpin Mar 28 '16 at 15:31
  • One thing that is different about my setup - I am running this code on the web server - because it is an ASP page coded in javascript. So I am attempting to view my result with a Response.Write(result) replacing your document.write(JSON.stringify(result)). – rgalpin Mar 28 '16 at 15:52
  • Could be that the server side javascript is from an older version - "JScript engine generally coincides with the ECMAScript 3.0 specification " from http://stackoverflow.com/questions/28331519/what-version-of-javascript-does-asp-classic-use. Stuck with Classic ASP on this. – rgalpin Mar 28 '16 at 16:02
2

The answer to my question came when I finally discovered how to reference what I was trying to do using standard terms. The term is: Round Robin Tournament. So when I Googled "javascript round robin tournament schedule" one of the results was this: http://www.devenezia.com/javascript/article.php/RoundRobin2.html. That gave me the basis of what I needed to generate matchups programmatically.

rgalpin
  • 137
  • 1
  • 13