Randomly generating unique number in pairs multiple times

Question

I am trying to set up pairs of unique numbers over a course of x times

For example if x = 8 I want to generate something like:

(5,3) (1,4) (7,2) (8,6)

Currently I have:

var playerArray = [0,1,2,3,4,5,6,7];
var loopLength = playerArray.length;
var player1 = 0;
var player2 = 0;
for(var i = 1; i <= loopLength;i++){
    var num = Math.floor(Math.random() * playerArray.length);
    if(player1 == 0){
        player1 = num+1;
        playerArray.splice(num, 1);
    }else if(player2 == 0){
        player2 = num+1;
        playerArray.splice(num, 1);
    }

    if((player1 != 0) && player2 != 0){
        alert(player1 + ' vs ' + player2);
        player1 = 0;
        player2 = 0;
    }

}

The problem, I think, is that I am using index to assign the numbers and when I splice them it resets the index, so I can end up with 1 vs 2, 1 vs 3, 2 vs 3 and so on.

Any help would be appreciated. Thanks!

Answer 1

I like @JeroenVannevel's idea of using a shuffle, or here is a method that comes to mind off the top of my head:

// Given an array of player IDs, return an array of random pairs
function randomPairs( players ) {
    var pairs = [];
    while( players.length ) {
        pairs.push([
            pluckRandomElement( players ),
            pluckRandomElement( players )
        ]);
    }
    return pairs;
}

// Return a random element and remove it from the array
function pluckRandomElement( array ) {
    var i = randomInt( array.length );
    return array.splice( i, 1 )[0];
}

// Return a random integer 0 <= n < limit
function randomInt( limit ) {
    return Math.floor( Math.random() * limit );
}

@LeeMeador shared an interesting insight about this bit of code:

        output.push([
            pluckRandomElement( array ),
            pluckRandomElement( array )
        ]);

It isn't necessary to use random elements for both of the values here. Since the array is already randomized, you could pluck the first array element and a random one. Or use array.pop() to pluck the last element—for a very long array that could be slightly more efficient:

        output.push([
            array.pop(),
            pluckRandomElement( array )
        ]);

And here's another version, using a shuffle as Jeroen suggested:

// Given an array of player IDs, return an array of random pairs
function randomPairs( players ) {
    shuffle( players );
    var output = [];
    for( var i = 0, n = players.length;  i < n;  i += 2 ) {
        output.push([ players[i], players[i+1] ]);
    }
    return output;
}

// Shuffle an array in place using the Fisher-Yates algorithm,
// adapted from http://bost.ocks.org/mike/shuffle/
function shuffle( array ) {
    for( var m = array.length;  m; ) {
        var i = Math.floor( Math.random() * m-- );
        var t = array[m];
        array[m] = array[i];
        array[i] = t;
    }
    return array;
}

Either version can be tested with this code:

// Create an array of length n and values 1 through n
function createPlayerArray( nPlayers ) {
    var array = [];
    for( var i = 0;  i < nPlayers;  ++i ) {
        array.push( i + 1 );
    }
    return array;
}

var players = createPlayerArray( 8 );
console.log( randomPairs(players) );

I separated out the creation of the player array from the rest of the code, to allow for the possibility of non-sequential player IDs (e.g. ID fields from a database or such).

Answer 2

var playerArray = [0,1,2,3,4,5,6,7];  //your array
var loopLength = playerArray.length/2; //divid by 2 since you only want pairs
var player1 = 0; //intialize varibles
var player2 = 0;
for(var i = 1; i <= loopLength;i++){
  var num = Math.floor(Math.random() * playerArray.length); //generate a random number
  player1 = playerArray.splice(num, 1); //player1 = number from array
  num = Math.floor(Math.random() * playerArray.length); //generate a new random number
  player2 = playerArray.splice(num, 1); //player2 = number from array
  alert(player1 + ' vs ' + player2); //result

}

Answer 3

I'm not familiar with javascript, so excuse any syntax mistakes: feel free to correct them.

What I had in mind was this:

var playerArray = [0,1,2,3,4,5,6,7];
// Shuffle the array here. I just googled 
// and I noticed there is no shuffle function in JS, is this correct?
var player1 = 0;
var player2 = 0;
for(var i = 0, len = Math.floor(playerArray.length / 2); i < len; i++) {
   player1 = playerArray[i * 2];
   player2 = playerArray[(i * 2) + 1];
   alert(player1 + " vs " + player2);
}

All you would have to do is add a shuffle function.

Additional clarification:

By shuffling a set of items you can extract them and retrieve a random result. What's key here is to store the pointer of the last item you extracted so you know where to continue. Since we want multiple random elements we should work in a lineair fashion, starting from the boundaries (in this case the first index and working towards the end).

We let the loop run untill half the size of the array. Since we're using integers as index, an odd integer split in half (7 => 3.5) will be floored and the loop will run 3 times. Because we have a loop we also already have our pointer (i). The only tricky part is to make sure you're pointing at the correct index: each traversal of the loop actually uses 2 indices, so we have to multiply it by 2. By doing this we get the first item of the loop and the second one uses the same approach, but adds 1 to the index to get the next item.

Answer 4

var playerArray = [0,1,2,3,4,5,6,7];
var opponentArray = [];

// mark everyone unassigned
for (var i = 0; i < playerArray.length; ++i) {
    opponentArray[i] = -1;
}

for (var i = 0; i < playerArray.length; ++i) {
    if (opponenentArray[i] == -1) {
        for (;;) {  // Keep trying until you get one that isn't assigned yet
            var num = Math.floor(Math.random() * playerArray.length);
            if (num != i && opponentArray[num] == -1) { // this one is unassigned and not me
                opponentArray[i] = num; // assign them to each other
                opponentArray[num] = i;
                break;
            }
        }
    }
}

Note

It was pointed out that their are inefficiencies involved in getting random numbers and then throwing them away.

It would have to be tested but I suspect that is offset by lacking the cost associated with moving of the array elements around in memory. Most every splice is rearranging the array elements and creating more objects in memory with added memory management and garbage collection costs.

Thank you @JimmiTh for finding the error where someone could end up playing themself. I guess even this code needs tests :)

Answer 5

I think what you are looking for is something more along the lines of this, unless I am mistaken:

var playerArray = [0,1,2,3,4,5,6,7];
var player1 = 0;
var player2 = 0;

// While there are still numbers in the array, keep pairing up the players
while (playerArray.length > 0) {
    // Get the first players number from the array and then and remove it from the array
    var arrayNum1 = Math.floor(Math.random() * playerArray.length);
    player1 = playerArray[arrayNum1] + 1;
    playerArray.splice(arrayNum1, 1);

    // Get the second players number from the array and then and remove it from the array
    var arrayNum2 = Math.floor(Math.random() * playerArray.length);
    player2 = playerArray[arrayNum2]  + 1;
    playerArray.splice(arrayNum2, 1);

    // Display the pairing
    alert(player1 + ' vs ' + player2);
}

Some sample results from testing:

1st run - (7, 3), (8, 1), (6, 5), (4, 2)
2nd run - (4, 6), (5, 7), (2, 3), (8, 1)
3rd run - (1, 8), (2, 6), (3, 5), (7, 4)
4th run - (6, 3), (5, 8), (7, 1), (4, 2)
5th run - (2, 4), (7, 5), (8, 6), (3, 1)

Answer 6

I had to do this recently. I like the idea of the shuffle algorithm. I created a copy array (the pairs) of the shuffled array and then rotated that array by 1. Then I matched the indexes of each array to create the pairs. I think that'll create unique pairs for all but arrays of size 1 and 2.