피셔 예이츠 셔플 Fisher Yates Shuffle 알고리즘(배열 섞기)

✔ 피셔 예이츠 셔플 Fisher Yates Shuffle

피셔 예이츠 셔플은 유한 수열을 무작위 순열로 섞기 위한 알고리즘이다.

이 알고리즘은 모든 항목이 들어 있는 통에서 항목이 남아 있지 않을 때까지 항목을 무작위로 꺼내어 다음 항목을 선택한다. 이 알고리즘은 편향되지 않은 순열을 생성한다. - 출처: 위키백과

 

✔ 피셔 예이츠 알고리즘의 이해

5개의 요소 [0, 1, 2, 3, 4]를 가지는 배열을 생각해보기

- for문 i에 4, 3, 2, 1, 0 대입

- Math.random()은 0 이상 1 미만의 값이 반환되므로 randomIndex는 0 이상 i 이하

i	임의의 인덱스(예)	변경 후 배열(예)
4	3	[0, 1, 2, 4, 3]
3	1	[0, 4, 2, 1, 3]
2	0	[1, 4, 0, 2, 3]
1	0	[4, 1, 0, 2, 3]
0	0	[4, 1, 0, 2, 3]

 

✔ 적용

게임에서 요소의 값을 섞을 때 사용하기 좋다.

 

✔ 예시

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

const arrayLength = array.length;

for (let i = arrayLength - 1; i >= 0; i-- ) {

  const randomIndex = Math.floor(Math.random() * (i + 1));

  [array[i], array[randomIndex]] = [array[randomIndex], array[i]];

}

console.log(array) // 결과: [4, 5, 1, 2, 3]

 

* 재사용할 수 있도록 처리 작업을 함수로 만들면 편하다.

function shuffleArray(sourceArr) {

  // 기존 배열의 복제 생성

  const array = sourceArr.concat();

  // 피셔 예이츠 알고리즘

  const arrayLength = array.length;

  for (let i = arrayLength - 1; i >= 0; i-- ) {

    const randomIndex = Math.floor(Math.random() * (i + 1));

    [array[i], array[randomIndex]] = [array[randomIndex], array[i]];

  }

  return array;

}