I'm working on a Secret Santa app, and I'm matching up people by shuffling up an array of users, and then iterating through it using a for loop, then invoking the function if a key in the first array is identical to a key in the second array. However, this is causing some problems when being executed within the application, and results in it hanging at times. In addition, the theoretical maximum execution time for this function is infinite, and something I want to avoid.
Is there a way to shuffle an array so that no two keys are in the same location without reiterating the function if it fails?
The code I'm using (not implemented into the application itself) is as follows:
//underscore utility library
var _ = require('underscore');
//pretty console colors
var colors = require('colors');
//fs module to write to file
var fs = require('fs');
//path utilities
var path = require('path');
//arr will contain the UIDs of the participants.
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50];
//sArr will be the pairings.
var sArr = [];
//plain-text data
var writeMe = '';
//i for an i
var i = 0;
//var declaration to shut up the linter
var justDoIt;
var writeIt;
var shuffleIt;
var checkIt;
var shuffleIt = function () {
//use Underscore.js' shuffle function on the array.
sArr = _.shuffle(arr);
};
var checkIt = function () {
for (i = 0; i < arr.length; i++) {
//check to make sure that there are no duplicates.
//otherwise, politely plain
if (arr[i] === sArr[i]) {
//well fuck. both are the same. Let's do it again
console.log(arr[i] + "=>" + sArr[i]);
console.log("ERROR".red + "\n==================\n");
justDoIt();
return;
}
//otherwise, print current pairing to console
writeMe += arr[i] + '=>' + sArr[i] + "\n";
console.log(arr[i] + '=>' + sArr[i]);
}
//we're done!
console.log("All good!".green);
//let's write it out
writeIt();
return;
};
var justDoIt = function () {
//roll it
shuffleIt();
//check it
checkIt();
};
var writeIt = function () {
//write it to a file
fs.writeFileSync(path.join(__dirname, 'pairings.txt'), writeMe);
};
//init
justDoIt();
I'm working on a Secret Santa app, and I'm matching up people by shuffling up an array of users, and then iterating through it using a for loop, then invoking the function if a key in the first array is identical to a key in the second array. However, this is causing some problems when being executed within the application, and results in it hanging at times. In addition, the theoretical maximum execution time for this function is infinite, and something I want to avoid.
Is there a way to shuffle an array so that no two keys are in the same location without reiterating the function if it fails?
The code I'm using (not implemented into the application itself) is as follows:
//underscore utility library
var _ = require('underscore');
//pretty console colors
var colors = require('colors');
//fs module to write to file
var fs = require('fs');
//path utilities
var path = require('path');
//arr will contain the UIDs of the participants.
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50];
//sArr will be the pairings.
var sArr = [];
//plain-text data
var writeMe = '';
//i for an i
var i = 0;
//var declaration to shut up the linter
var justDoIt;
var writeIt;
var shuffleIt;
var checkIt;
var shuffleIt = function () {
//use Underscore.js' shuffle function on the array.
sArr = _.shuffle(arr);
};
var checkIt = function () {
for (i = 0; i < arr.length; i++) {
//check to make sure that there are no duplicates.
//otherwise, politely plain
if (arr[i] === sArr[i]) {
//well fuck. both are the same. Let's do it again
console.log(arr[i] + "=>" + sArr[i]);
console.log("ERROR".red + "\n==================\n");
justDoIt();
return;
}
//otherwise, print current pairing to console
writeMe += arr[i] + '=>' + sArr[i] + "\n";
console.log(arr[i] + '=>' + sArr[i]);
}
//we're done!
console.log("All good!".green);
//let's write it out
writeIt();
return;
};
var justDoIt = function () {
//roll it
shuffleIt();
//check it
checkIt();
};
var writeIt = function () {
//write it to a file
fs.writeFileSync(path.join(__dirname, 'pairings.txt'), writeMe);
};
//init
justDoIt();
- 3 Way too plicated. Shuffle the array once, make a copy of it, transpose the elements in that copy by one. Voila, guaranteed unique match-ups. – deceze ♦ Commented Dec 24, 2014 at 2:51
- 3 @deceze What if the shuffled array was one away from having an exact match? – Vitruvie Commented Dec 24, 2014 at 2:52
- 1 @Saposhiente After the copy, all of them will be exact matches, but in a random order. Shifting them by one will make a set of random matches that are guaranteed to have no collisions. – Brandon Anzaldi Commented Dec 24, 2014 at 2:54
- 4 Anyone else notice this is for a secret Santa app... with only 1 day left before Christmas? that's a seriously tight deadline! ;-) – scunliffe Commented Dec 24, 2014 at 2:59
- 4 @deceze I see more clearly what exactly you meant by this algorithm. It's simple because it is not truly random: It is guaranteed to produce a gifting assignment such that if you follow a chain of one gift to the next, you always go through every person in the group before returning to your start; in a truly random shuffle, there will be many separate loops of gifts. – Vitruvie Commented Dec 24, 2014 at 3:08
3 Answers
Reset to default 8The general term for a rearrangement where no element is in its original position is a derangement, and it's a fascinating problem.
You are looking for an unbiased (uniformly random), non-rejection (not "repeat until it works") algorithm for a random derangement.
It's not trivial.
This is one such algorithm (EDIT: it does not appear to be unbiased):
function derangementNumber(n) {
if(n == 0) {
return 1;
}
var factorial = 1;
while(n) {
factorial *= n--;
}
return Math.floor(factorial / Math.E);
}
function derange(array) {
array = array.slice();
var mark = array.map(function() { return false; });
for(var i = array.length - 1, u = array.length - 1; u > 0; i--) {
if(!mark[i]) {
var unmarked = mark.map(function(_, i) { return i; })
.filter(function(j) { return !mark[j] && j < i; });
var j = unmarked[Math.floor(Math.random() * unmarked.length)];
var tmp = array[j];
array[j] = array[i];
array[i] = tmp;
// this introduces the unbiased random characteristic
if(Math.random() < u * derangementNumber(u - 1) / derangementNumber(u + 1)) {
mark[j] = true;
u--;
}
u--;
}
}
return array;
}
var a = [1, 2, 3, 4, 5, 6, 7];
derange(a);
You can look at this paper, this slide deck, or this Mathematics question too.
As was pointed out in the ments, by shuffling the initial array, then shifting it by 1 (or any number less than the length of the array) will yield a random sort.
Sample code:
// Underscore Utility Library, since I was using this anyway.
var _ = require('underscore');
// Example shuffle: [4,2,1,9,5,8,3,7,6]
var arr = _.shuffle([1,2,3,4,5,6,7,8,9]);
var sArr = _.union(_.rest(arr), [_.first(arr)]);
// Log out pairs.
for (i = 0; i < arr.length; i++) {
console.log(arr[i] + ' --> ' + sArr[i]);
}
An example output for this is:
6 --> 3
3 --> 1
1 --> 2
2 --> 4
4 --> 7
7 --> 5
5 --> 8
8 --> 9
9 --> 6
The caveat of this solution is that it's not truly random. It will create certain impossible situations. For example, with this solution, it would be impossible for two users to get each other. 3 cannot have 6 if 6 already has 3. It creates a chain-effect that will ensure a random ordering, and that each recipient pairing will be unpredictable without knowledge of the previous pairings, but it will not be truly random.
The following seems reasonably random and guarantees that a member will not be returned to its original position:
// Return a new array that is a deranged version of arr
// Guarantee that no member retains its original position
function derange(arr) {
// Make a copy of arr
var c = arr.slice();
// If arr.length is < 2, return copy
if (c.length < 2) {
return c;
}
var result = [];
var idx, i, iLen;
// Keep track of whether last member has been moved
var lastMoved = false;
// Randomly remove a member of c, with conditions...
for (i=0, iLen=c.length - 1; i<iLen; i++) {
// If get down to final two and last hasn't been moved,
// swap last two and append to result
if (c.length == 2 && !lastMoved) {
result = result.concat(c.reverse().splice(0,2))
break;
}
// Otherwise, select a remaining member of c
do {
idx = Math.random() * c.length | 0;
// But make sure it's not going back in the same place
} while (arr.indexOf(c[idx]) == result.length)
// Add member to result
result.push(c.splice(idx, 1)[0]);
// Remember if last was just moved
lastMoved = lastMoved || idx == c.length;
}
// Add the last member, saves a do..while iteration about half the time
if (c.length) result.push(c[0]);
return result;
}
Some results:
console.log(derange([1,2,3,4,5,6]));
[6, 4, 2, 5, 3, 1]
[4, 1, 2, 5, 6, 3]
[5, 4, 2, 6, 1, 3]
[4, 5, 2, 3, 6, 1]
[4, 6, 1, 5, 2, 3]
[5, 6, 1, 3, 4, 2]
[2, 4, 6, 1, 3, 5]
[2, 1, 4, 5, 6, 3]
It's impossible to preclude certain values from Math.random, so if you get one you don't like, there's no choice but to get another. So a do..while loop is used to ensure that a member originally at index i isn't moved to new index i. However, such collisions should be minimal. It would also be good to optimise the lookup of the original value other than using indexOf. Perhaps that only matters for very large arrays.
If it gets to the last two members and the last member of the original array hasn't been moved, it will simply reverse then append the last two members, which is the only possible oute at that point.