javascriptarraysunderscore.jsshuffle

How do I shuffle a Javascript Array ensuring each Index is in a new position in the new Array?


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.


Solution

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