Retrieve random element from array not contained in second array

Question

I have a function, getUnusedName that returns a random name, but first checks if it's already used by any object within a second array.

Observing how many times the function is called across multiple runs shows a pretty wide variation as I would expect when using random. Is there a more efficient way of achieving this?

As well as a general code review, I'd also like to ask:

1. If possible, I'd like to avoid removing items from names, which is why I have chosen the random solution. Is this a bad choice? What are my alternatives?

2. Is there a cleaner way to check if a name is already in use? Using Array.filter then checking the resulting length seems a little verbose.

var names = ['Steve', 'Adam', 'Phillip', 'Thomas', 'John', 'Joseph'];
var people = [];
var calls = 0;
function getUnusedName() {
 calls++;
 var randomName = names[Math.floor(Math.random() * names.length)];
 if (people.filter(function (val) { return val.name === randomName; }).length === 0) {
 return randomName
 } else {
 return getUnusedName();
 }
}
for (var i = 0; i < names.length; i++) {
 var name = getUnusedName();
 people.push({
 name: name,
 age: (i * i) + 20,
 });
}
console.log('getUnusedName calls: ' + calls);
console.log(people);

• Flambino: How about shuffling the names array, and then just taking one name at a time? Would that be a solution? Or should the names not be altered at all?

Answer 1

The choice of the algorithm will depend on how many elements you have in your array, and how many of them you want to select. If you want to pull all names in random order, then shuffling is probably the best choice.

You can easily create a copy of names using names.slice() and shuffle the copy instead of the original array:

function randint(a, b) {
 return a + Math.floor(Math.random() * (b - a));
}
function shuffle(list) {
 list.forEach(function(value, i) {
 var j = randint(i, list.length);
 list[i] = list[j];
 list[j] = value;
 });
 return list;
}
var names = ['Steve', 'Adam', 'Phillip', 'Thomas', 'John', 'Joseph'];
console.log(shuffle(names.slice()));

Alternatively, you can shuffle an array of numbers [0..N], and use them as indices to the names array:

function range(start, stop) {
 var list = [];
 for (var i = start; i < stop; i++) {
 list.push(i);
 }
 return list;
}
var indices = shuffle(range(0, names.length));
indices.forEach(function(i) {
 console.log(names[i]);
});

Shuffling has a much better time complexity than the original algorithm. For an array of 1000 names, the innermost loop of the original algorithm is executes ~6 million times, while the innermost loop of the shuffle algorithm is executed only 1000 times.