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

1. 셔플 알고리즘(shuffle)

 

 

 

 

 본론으로 돌아와서, 자바스크립트에서는 랜덤 정렬을 두 가지 방법을 이용해서 구현할 수 있는데, 첫 번째는 sort() 메서드를 이용하는 방법이고, 두 번째는 피셔 예이츠 셔플(Fisher-Yates Suffle) 알고리즘을 이용하는 방법이다.

 

 

2.  Sort() 를 이용하는 방법

 

 

 sort() 메서드는 음수 값을 리턴하면 내림차순으로 정렬되고, 양수 값을 리턴하면 오름차순으로 정렬된다. 그래서 이를 랜덤으로 정렬시키기 위해서는 양수 또는 음수 값이 나오는 선택지를 줘야한다. 

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

arr.sort(() => Math.random() - 0.5);

 

 위 예제를 보면 Math.random()은 곱한 값이 없으므로 0.xxxxxxxx의 난수를 발생시킨다. 이 과정은 총 다섯 번 실행된다. 각 과정마다 Math.random() 메서드가 만든 난수가 0.5보다 크면 양수가 리턴되고, 0.5보다 작으면 음수가 리턴된다. 그리고 매회마다 어떤 값이 나올지 모르기 때문에 위 코드는 랜덤정렬이라고 할 수 있다.

 

 

 하지만 코어 자바스크립트 사이트에서는 위 코드를 이용해서 랜덤정렬을 할 것을 추천하지 않는다. 왜냐하면 위 코드는 모든 순열의 빈도 수가 균일하게 나오지 않기 때문이다. 무슨 말인지 모른겠다면, 링크를 참고하면 바로 이해할 수 있을 것이다. 따라서 이 경우를 고려해서 랜덤정렬을 시키기 위해서는 피셔 예이츠 셔플 알고리즘(Fisher-Yates Shuffle)을 쓰면 된다.

 

 

3. 피셔 예이츠 셔플(Fisher-Yates Shuffle) 알고리즘

 피셔 예이츠 셔플 알고리즘은 랜덤 정렬을 위해 로날드 피셔(Ronald Fisher)와 프랭크 예이츠(Frank Yates)가 고안한 알고리즘이다. 그 밖에도 이 알고리즘을 이용한 Sattolo 알고리즘이 있는데, 이 알고리즘은 순환 순열(팩토리얼이라고 생각하면 될 것 같다.)을 발생시키기 위해서 만든 알고리즘이다.

 

 

피셔 예이츠 셔플 알고리즘은 오리지날(클래식)한 버전과 모던한 버전이 있다. 

 

 

오리지날 버전의 동작과정과 코드는 다음과 같다.

1.  임의로 입력된 배열 [1, 2, 3, 4, 5]가 있다고 가정해보자.

2.  0부터 4까지의 난수를 발생시킨다.

3.  (2)에서 난수가 3이 나왔다고 가정해보자.

4.  입력 배열[3]의 값을 뺀다. 그러면 입력배열은 [1, 2, 4, 5]가 된다.

5.  난수 3에 1을 더한다(난수: 4)

6.  난수 4와 입력 배열 길이에 1을 뺀 값를 비교연산 한다. 이 때 난수 4가 더 클 경우, 난수를 0으로 만들고, 난수 4가 더 작은 경우 값을 유지한다.

7.  (4) - (6) 과정을 입력 배열이 빈 상태가 될 때까지 반복한다.

const fysOriginal = (arr) => {
    let roll = Math.floor(Math.random()*arr.length);
    const firstRoll = roll;
    const strikeOut = [];
    while(arr.length){
        strikeOut.push(arr.splice(roll, 1)[0]);
        roll += 1;
        if(roll >= arr.length)
          roll = 0;
    }
    return strikeOut;
}

 

 모던 버전의 코드는 다음과 같다. 동작 과정을 설명하는 것 보다 코드를 보는 것이 더 이해하기 쉬울 것이라 생각하여 코드만 올리도록 하겠다.

const fysModern = (arr) => {
  const strikeOut = [];
  while(arr.length){
    const lastIdx = arr.length-1;
    let roll = Math.floor(Math.random()*arr.length);
    let temp = arr[lastIdx];
    arr[lastIdx] = arr[roll];
    arr[roll] = temp;
    strikeOut.push(arr.pop());
  }
  return strikeOut;
}

 

 부록으로 순열(permutation)을 발생시키는 Sattolo 알고리즘의 코드는 다음과 같다.

const sattoloCycle = (arr) => {
    for(let i=arr.length-1; i>=1; i--){
      let roll = Math.floor(Math.random()*i);

      const temp = arr[roll];
      arr[roll] = arr[i];
      arr[i] = temp;
    }
}

 

 위 예제는 자신을 제외한 순열 데이터 중 하나의 결과만을 반환한다. [10, 20, 30]을 예로 들면, [20, 10, 30], [10, 30, 20] 둘 중에 하나 값이 이 랜덤으로 만들어진다는 뜻이다. 자신을 제외한 모든 순열 결과를 보고 싶을 경우, 피셔 예이츠 셔플 알고리즘을 응용해서 다음과 같이 작성하면 된다.'

const sattoloCycle = (arr) => {
  const newArr = [];
  const originalArr = JSON.parse(JSON.stringify(arr));
  let count = arr.length-1;
  const isUsed = new Array(arr.length-1).fill(false);
  const firstRolls = Array.from({length: arr.length-1}, (x,idx) => idx);

  const fys = (a) => {
    const lastIdx = a.length-1;
    let roll = Math.floor(Math.random()*a.length);
    const temp = a[lastIdx];
    a[lastIdx] = a[roll];
    a[roll] = temp;
    return a.pop();
  };
  
  while(count > 0){
    for(let i=arr.length-1; i>=1; i--){
      let roll =  count === arr.length-1 ? fys(firstRolls) : Math.floor(Math.random()*i);

      const temp = arr[roll];
      arr[roll] = arr[i];
      arr[i] = temp;
    }
    newArr.push(arr);
    arr = originalArr;
    count--;
  }
  console.log(newArr);
}