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.

Simplest solution: Just shuffle the whole array (which definitely avoids repetition), then pair it up. — Bergi
– Bergi, Commented Jan 22, 2014 at 22:22
What might be easier is to randomize your names array, then loop through and pair that way. — brouxhaha
– brouxhaha, Commented Jan 22, 2014 at 22:23
When I attempted to do this the problem I had was trying to re-run the shuffle if someone was matched with themselves. I wouldn't want to re-shuffle the entire array so I'd have to just shuffle out that one name for someone else and hope to avoid the same problem. — Sean Patterson
– Sean Patterson, Commented Jan 22, 2014 at 22:26

adeneo · Accepted Answer · 2014-01-22 23:10:46Z

4

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

edited Jan 22, 2014 at 23:10

answered Jan 22, 2014 at 22:29

adeneo

319k29 gold badges410 silver badges392 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Tibos Over a year ago

You don't need an even number of names. You just need at least 2.

Tibos Over a year ago

You can get the same name drawn in a very edge case: arr1:[a,b,c] arr2:[b,a,c] (after sort). See my answer for a solution that is aplicable here.

adeneo Over a year ago

added some comments to make it easier to "decipher"

elclanrs · Accepted Answer · 2014-01-22 22:32:26Z

4

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' ]
// ]

answered Jan 22, 2014 at 22:32

elclanrs

94.2k21 gold badges137 silver badges171 bronze badges

Comments

Tibos · Accepted Answer · 2014-01-22 22:44:21Z

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

Samsquanch · Accepted Answer · 2014-01-22 22:44:52Z

1

I'm a tad late, but thought I'd throw my answer in here. It essentially does the same thing @adeneo's does, but it uses the same basic code as OP:

var names = ["Sean","Kyle","Emily","Nick","Cotter","Brian","Jeremy","Kimmy","Pat","Johnny"];
    pickpool = names.slice(0); // Slice the array at the first element to copy it by value

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()*pickpool.length)

    if(names[random] == names[i]) {
        // names[random] = names[random++];
        picks.push(names[i] + " gets " + pickpool[random++]);
        pickpool.splice(random++,1);
    } else {
        picks.push(names[i] + " gets " + pickpool[random]);
        pickpool.splice(random,1);
    }
}
console.log("picked array: ");
for(var k=0; k<picks.length; k++) {
    console.log(picks[k]);
}

http://jsfiddle.net/SNJpC/

answered Jan 22, 2014 at 22:44

Samsquanch

9,17612 gold badges55 silver badges90 bronze badges

1 Comment

Sean Patterson Over a year ago

Also works great - it is actually very helpful since I've just spent the past few minutes trying to decipher how @adeneo's solution works.

Dan Iveson · Accepted Answer · 2014-01-22 22:23:15Z

0

If you don't need to keep the original array you can remove the names as they get selected and each time you pick a name check that it isn't an empty string before pushing it to the next array.

answered Jan 22, 2014 at 22:23

Dan Iveson

9366 silver badges10 bronze badges

3 Comments

brouxhaha Over a year ago

If you remove the names, you wouldn't have any empty strings.

Sean Patterson Over a year ago

I initially thought of removing the name from the array if it was randomly chosen, but that also eliminates that person from the drawing. Each person needs to draw someone as well as be drawn. Removing them eliminates them from the first part.

Dan Iveson Over a year ago

@Shaun Patterson - Right enough then.

Cruz Jurado · Accepted Answer · 2022-06-24 02:46:48Z

Another consideration...

If you are trying to make a 'Secret Santa' generator, by using random method you can get the same pair next year, and next...

This is another solution where you get all the possible pairs (without repeating a name itself or a pair) for multiple years.

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 {

  const arr1 = names.slice()
  let arr2 = names.slice();

  let countDown = number => {

    if (number === 1) {
      return;
    }

    const last = arr2.pop([number - 1]);
    arr2.unshift(last);

    let pairs = [];

    arr1.map(item => {
      const index = arr1.indexOf(item);
      pairs.push(`${arr1[index]} gets ${arr2[index]}`)
    })

    console.log(pairs)

    return countDown(number - 1);
  }

  countDown(names.length)

}

Collectives™ on Stack Overflow

Javascript: randomly pair items from array without repeats

6 Answers 6

3 Comments

Comments

Comments

1 Comment

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

3 Comments

Comments

Comments

1 Comment

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related