[Js] 피셔 예이츠 셔플 알고리즘 (Fisher-Yates Shuffle)

셔플 알고리즘 (shuffle)

자바스크립트에는 랜덤 정렬을 위한 2가지 방법
1.sort()메소드
2.Fisher-Yates shuffle 알고리즘

1. Sort() 메소드

일반적을 sort() 메소드는 오름차순 / 내림차순으로 정렬할 때 자주 사용됨.

• 오름차순 : 양수 값을 리턴

const arr = [1, 2, 3, 4, 5];
arr.sort((a, b) => a - b);

• 내림차순 : 음수 값을 리턴

const arr = [1, 2, 3, 4, 5];
arr.sort((a, b) => b - a);

그리고 random정렬(셔플)할 때도 사용할 수 있음.

아래의 예제에서 0<= Math.random < 1 에서의 0.xxxxx값을 발생시키며, 이 과정은 arr배열 인자만큼 실행됨. 발생 된 값이 매순간 랜덤하기 때문에 양수/음수 리턴되는 것이 매회마다 달라져, 랜덤정렬이 가능하다고 볼 수 있음,

const arr = [1, 2, 3, 4, 5];
arr.sort(() => Math.random() - 0.5);

2. 피셔 예이츠 셔플 알고리즘 Fisher-Yates Shuffle

sort()메소드는 모든 순열의 빈도 수가 균일하게 나오지 않기 때문에 권장되지 않음.
그 대신에 피셔 예이츠 셔플 알고리즘을 사용할 수 있으며, 더 널리 사용되고 있음.

이는 로날드 피셔와 프랭크 예이츠가 만들어낸 알고리즘으로 게임야구/로또추첨기/카드뒤집기/음악랜덤 게임에서 사용됨.

예제

숫자야구

// 숫자뽑기
let candidate = [1,2,3,4,5,6,7,8,9];
let chosenNum = [];
// 숫자 4개
for (let i = 0; i < 4; i++) {
// 1 - 9까지 랜덤한 숫자 빼주기, splice() 0-8번째 index
	let fourNum = [];
    fourNum = candidate.splice(Math.floor(Math.random() * (9 - i)), 1)[0];
    chosenNum.push(fourNum);
  }
 console.log(chosenNum);

공뽑기

// while문
  const candidate = Array(45).fill().map((v, i) => i + 1);
  const shuffle = [];
  while (candidate.length > 0) {
    const random = Math.floor(Math.random() * candidate.length); // 무작위 인덱스 뽑기
    const spliceArray = candidate.splice(random, 1); // 뽑은 값은 배열에 들어 있음
    const value = spliceArray[0]; // 배열에 들어 있는 값을 꺼내어
    shuffle.push(value); // shuffle 배열에 넣기
  }
  console.log(shuffle);

// for문
  const candidate = Array(45).fill().map((v,i) => i+1);
  const shuffle = [];
  for (let i = candidate.length ; i > 0 ; i--){
    const random = Math.floor(Math.random() * i);
    const spliceArray = candidate.splice(random, 1);
    const value = spliceArray[0];
    shuffle.push(value);
 }
 console.log(shuffle);