Javascript: randomly pair items from array without repeats

Question

I am trying to make a very basic "secret santa" generator as one of my first Javascript projects. I have searched for hours for a solution to this problem but so far nothing has worked that I have found.

I have an array of names which need paired to each other. I successfully have them pairing to each other, but right now someone can be drawn twice. I am pushing the randomly chosen names to another array but I can't find a way to check the randomly chosen names against the ones already chosen.

var names = ["Sean","Kyle","Emily","Nick","Cotter","Brian","Jeremy","Kimmy","Pat","Johnny"];

var used = [];
var picks = [];

if (names.length % 2 != 0) {
    alert("You must have an even number of names. You currently have " + names.length + " names.");
}

for( var i = 0; i < names.length; i++){

var random = Math.floor(Math.random()*names.length)

if(names[random] == names[i]) {
    names[random] = names[random++];
    picks.push(names[i] + " gets " + names[random]);
    used.push(names[random]);
} else {
    picks.push(names[i] + " gets " + names[random]);
    used.push(names[random]);
}

}

console.log("picked array: ")
for(var k=0; k<picks.length; k++) {
console.log(picks[k]);
}
console.log("used array: " + used);

Thank you in advance for any help.

Answer 1

Create two arrays with the names, shuffle them, and make sure you don't pick the same name from both arrays :

var names = ["Sean","Kyle","Emily","Nick","Cotter","Brian","Jeremy","Kimmy","Pat","Johnny"];

if (names.length % 2 != 0) {
    alert("You must have an even number of names. You currently have " + names.length + " names.");
} else {
    var arr1 = names.slice(), // copy array
        arr2 = names.slice(); // copy array again

    arr1.sort(function() { return 0.5 - Math.random();}); // shuffle arrays
    arr2.sort(function() { return 0.5 - Math.random();});

    while (arr1.length) {
        var name1 = arr1.pop(), // get the last value of arr1
            name2 = arr2[0] == name1 ? arr2.pop() : arr2.shift();
            //        ^^ if the first value is the same as name1, 
            //           get the last value, otherwise get the first

        console.log(name1 + ' gets ' + name2);
    }
}

FIDDLE

Answer 2

I would suggest a different approach. Shuffle, split, and zip, no mutation:

var splitAt = function(i, xs) {
  var a = xs.slice(0, i);
  var b = xs.slice(i, xs.length);
  return [a, b];
};

var shuffle = function(xs) {
  return xs.slice(0).sort(function() {
    return .5 - Math.random();
  });
};

var zip = function(xs) {
  return xs[0].map(function(_,i) {
    return xs.map(function(x) {
      return x[i];
    });
  });
}

// Obviously assumes even array
var result = zip(splitAt(names.length/2, shuffle(names)));
//^
// [
//   [ 'Nick', 'Kimmy' ],
//   [ 'Sean', 'Johnny' ],
//   [ 'Kyle', 'Brian' ],
//   [ 'Cotter', 'Pat' ],
//   [ 'Emily', 'Jeremy' ]
// ]

Answer 3

There is a multitude of ways you can achieve this.

The fastest to code, but not necessarily the randomest is:

var names = ["Sean","Kyle","Emily","Nick","Cotter","Brian","Jeremy","Kimmy","Pat","Johnny"];
function getPicks(names) {
  return names.slice(0).sort(function(){ return Math.random()-0.5 }).map(function(name, index, arr){
    return name + " gets " + arr[(index+1)%arr.length];
  });
}
getPicks(names);

This is not very random because the shuffling isn't very good and also because you get a single cycle each time. There can be no two cycles A->B->C->A D->E->D.

If you want it to have a random number of cycles of variable length, you can split the names array in several arrays and do the above for each of them, then concatenate the results (see elclanrs).

Finally, the last solution is for each person to pick a person at random and if it's the same one, simply pick again. If the last name remaining in both arrays is the same, simply swap it with another pair.

var names = ["Sean","Kyle","Emily","Nick","Cotter","Brian","Jeremy","Kimmy","Pat","Johnny"];

var a = names.slice(0);
var b = names.slice(0);
var result = [];
while (a.length > 1) {
  var i = extractRandomElement(a);
  var j = extractRandomElement(b);

  while (i===j) {
    b.push(j);
    j = extractRandomElement(b);
  }
  result.push({ a:i, b:j });
}
if (a[0] === b[0]) {
  result.push({ a:a[0], b:result[0].b });
  result[0].b = a[0];
} else {
  result.push({ a:a[0], b:b[0] });
}
var pairs = result.map(function(item){ return item.a + ' gets ' + item.b});


function extractRandomElement(array) {
  return array.splice(Math.floor(Math.random()*array.length),1)[0];
}