I have an Array of Objects, like so.
var usersGoing = [
{ user: 0 },
{ user: 1 },
{ user: 2 },
{ user: 3 },
{ user: 4 }
];
I need to shuffle this Array so that no Object remains in the same index as when it was instantiated, like so:
[
{ user: 3 },
{ user: 2 },
{ user: 4 },
{ user: 0 },
{ user: 1 }
]
It is IMPERATIVE that the resulting array be sorted in this manner, as each of these user Objects will be assigned to a different user Object.
I have tried a few different sorting algorithms, including Fisher-Yates, and I've tried using Underscore.js' _.shuffle(), and this variant from Kirupa Shuffling an Array in JavaScript:
function shuffleFY(input) {
for (var i = input.length-1; i >=0; i--) {
var randomIndex = Math.floor(Math.random()*(i+1));
var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}
return input;
}
Nothing I've tried is working. Help?
UPDATED: I've marked an answer as correct below, as the key points of the Sattolo Cycle were followed correctly. Also, this is NOT a duplicate of Shuffles Random Numbers with no repetition in Javascript/PHP as this question has the additional requirement of the resulting array not only not containing duplicates, but also cannot contain items in their same initial index position.
You posted a link with Sattolo's algorithm in Python:
from random import randrange
def sattoloCycle(items):
i = len(items)
while i > 1:
i = i - 1
j = randrange(i) # 0 <= j <= i-1
items[j], items[i] = items[i], items[j]
return
Here it is translated to JavaScript:
function sattoloCycle(items) {
for(var i = items.length; i-- > 1; ) {
var j = Math.floor(Math.random() * i);
var tmp = items[i];
items[i] = items[j];
items[j] = tmp;
}
}