Как перетасовать массив, не перемещая ЛОЖНЫЕ элементы? - PullRequest
Новая
       81

Как перетасовать массив, не перемещая ЛОЖНЫЕ элементы?

0 голосов
/ 02 августа 2020

Вот моя попытка; слегка модифицированный алгоритм Фишера-Йейтса. Я не знаю, как сделать так, чтобы он был случайным. 

const shuffleWithoutMovingFalsies = array => {
  const newArray = [...array];
  const getRandomValue = (i, N) => ~~(Math.random() * (N - i) + i);
  newArray.forEach((elem, i, arr, j = getRandomValue(i, arr.length)) => arr[i] && arr[j] && ([arr[i], arr[j]] = [arr[j], arr[i]]));
  return newArray;
}

const array = [1, 2, null, 3, null, null, 4, 5, 6, null];

const shuffledArray = shuffleWithoutMovingFalsies(array);

console.log(shuffledArray);

Все, что я сделал, это добавил arr[i] && arr[j] && в качестве проверки, чтобы убедиться, что оба элемента, которые собираются поменять местами, НЕ falsy.

1 Ответ

3 голосов
/ 02 августа 2020

Это мешает тасовать честно. Например, с массивом [1, null, 2], 1 должен иметь 50% шанс остаться на месте и 50% шанс поменяться местами с 2, но вместо этого разделение будет ⅔ – ⅓.

Пока вспомогательная память не является проблемой, я бы рекомендовал извлечь элементы, перемешать их и вернуть обратно для простоты: 

const shuffle = arr => {
    for (let i = 0; i < arr.length - 1; i++) {
        const j = i + Math.floor(Math.random() * (arr.length - i));
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
};

const shuffleTruthy = arr => {
    const truthy = arr.filter(Boolean);
    shuffle(truthy);

    let j = 0;

    for (let i = 0; i < arr.length; i++) {
        if (arr[i]) {
            arr[i] = truthy[j++];
        }
    }
};
...