Как перетасовать массив Javascript, чтобы каждый индекс находился в новой позиции в новом массиве?

У меня есть массив объектов, например.

var usersGoing = [
    { user: 0 },
    { user: 1 },
    { user: 2 },
    { user: 3 },
    { user: 4 }
];

Мне нужно перетасовать этот массив так, чтобы ни один объект не оставался в том же индексе, что и при его создании, например:

[
    { user: 3 },
    { user: 2 },
    { user: 4 },
    { user: 0 },
    { user: 1 }
]

ИМПЕРАТИВНО, чтобы результирующий массив был отсортирован таким образом, так как каждый из этих пользовательских объектов будет назначен другому пользовательскому объекту.

Я пробовал несколько разных алгоритмов сортировки, включая Fisher-Yates, и я попытался использовать Underscore.js '_.shuffle(), и этот вариант из Kirupa Перетасовка массива в 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;
}

Ничего, что я пробовал, работает. Помощь?

ОБНОВЛЕНО: я отметил ответ как правильно ниже, поскольку ключевые моменты цикла Sattolo соблюдались правильно. Кроме того, это не дубликат случайных чисел в случайном порядке без повторения в Javascript/PHP, поскольку этот вопрос имеет дополнительное требование к результирующему массиву, не только не содержащему дубликатов, но также не может содержать элементы в их исходной позиции индекса.

Ответ 1

Вы отправили ссылку на алгоритм Sattolo в 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

Здесь он переводится на 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;
  }
}

Ответ 2

Для каждой позиции произвольно выбирайте индекс в более высоком положении и заменяйте два.

Каждый объект будет либо в своем собственном положении, либо заменен, и его исходное положение будет заблокировано, либо оно будет заменено на более низкое положение и заперто на место к тому времени, когда его позиция будет заменена.

Когда вы переходите на вторую и последнюю позицию, вы гарантируете своп для последней позиции (которая может быть или не быть той же стоимостью, что и была первоначально там), и все готово. Ничего не оставалось делать для окончательной позиции.

1 2 3 4 5 - оригинальные значения

3 2 1 4 5

3 1 2 4 5

3 1 4 2 5

3 1 4 5 2

Ответ 3

попробуйте Fisher-Yates-Durstenfeld shuffle:

var usersGoing = [
    { user: 0 },
    { user: 1 },
    { user: 2 },
    { user: 3 },
    { user: 4 }
];


shuffle(usersGoing);
function shuffle(sourceArray) {
    for (var n = 0; n < sourceArray.length - 1; n++) {
        var k = n + Math.floor(Math.random() * (sourceArray.length - n));

        var temp = sourceArray[k];
        sourceArray[k] = sourceArray[n];
        sourceArray[n] = temp;
    }
}

console.log(usersGoing);

Ответ 4

Бит устаревших ответов, возможно, ваше программное обеспечение закончено, упаковано и продано к настоящему времени, но есть лучший способ добиться этого...

const arr = [1,2,3,4,5,6,7,8,9];
const sfl = arr.sort( () => { Math.random() - .5 } );
// sfl == [2,9,5,1,3,6,...]