Тасование Фишера-Йетса

Описание

• Википедия
• GitHub

Тасование Фишера-Йетса (Fisher-Yates shuffle) - это алгоритм создания произвольных перестановок конечного множества, проще говоря, для произвольного тасования множества. Правильно реализованный алгоритм несмещенный, так что каждая перестановка генерируется с одинаковой вероятностью. Современная версия алгоритма очень эффективна и требует время, пропорциональное числу элементов множества, а также не требует дополнительной памяти.

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

Реализация

// algorithms/sets/fisher-yates.js
export default function fisherYates(arr) {
  // Эффективно создаем глубокую копию массива
  // https://developer.mozilla.org/en-US/docs/Web/API/structuredClone
  const arrCopy = structuredClone(arr)

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

  return arrCopy
}

Тестирование

// algorithms/sets/__tests__/fisher-yates.test.js
import fisherYates from '../fisher-yates'

const sortedArr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

describe('fisherYates', () => {
  it('должен тасовать маленькие массивы', () => {
    expect(fisherYates([])).toEqual([])
    expect(fisherYates([1])).toEqual([1])
  })

  it('должен произвольно перетасовать элементы массива', () => {
    const shuffledArray = fisherYates(sortedArr)

    expect(shuffledArray.length).toBe(sortedArr.length)
    expect(shuffledArray).not.toEqual(sortedArr)
    expect(shuffledArray.sort()).toEqual(sortedArr)
  })
})

Запускаем тесты:

npm run test ./algorithms/sets/__tests__/fisher-yates