피셔-예이츠 셔플 알고리즘 이해하기

로또 추첨기를 프로그래밍으로 만든다면?

로또를 프로그래밍으로 만든다면 어떻게 추첨할까? 1부터 45까지의 정수 중 랜덤하게 뽑혀야 하며, 중복도 없어야 한다. 이때 사용될 수 있는 알고리즘이 '피셔-예이츠 셔플'이다.

피셔-예이츠 셔플 알고리즘

피셔-예이츠 알고리즘은 편향되지 않은 순열을 생성한다. 즉, 어떤 수의 집합이 있을 때 랜덤한 정렬을 편향되지 않게 만들어주는 정렬 방법인 것이다.

이 알고리즘을 사용하면 마치 물리적인 로또 추첨기가 통 안에서 마구 돌면서 섞인 후, 차례대로 뽑히는 것 같은 효과를 낼 수 있다.

방법은 다음과 같다.

1. 1 ~ 45까지 정수가 순서대로 담긴 배열1을 만든다.
2. 무작위 순열이 담길 빈 배열2를 선언한다.
3. 자바스크립트의 random 함수를 이용해 배열1에서 랜덤한 인덱스를 뽑는다.
4. 배열1에서 핸덤한 인덱스에 해당하는 요소를 추출한다.
5. 추출한 요소를 배열2에 담는다.
6. 1~5번의 작업을 반복한다.

그런데 여기서 한 가지 문제가 있다. 랜덤한 인덱스를 뽑을 때 중복된 값이 뽑힐 수도 있다는 점이다. 이러한 문제를 해결하기 위해 1부터 45까지의 숫자가 담긴 배열에서 이미 뽑힌 값은 제거해줘야 한다. 자바스크립트에서는 splice 함수를 통해 해결할 수 있다.

이를 코드로 구현하면 다음과 같다.

// candidate에는 1~45 정수가 순서대로 들어있다.
const candidate = Array(45).fill().map((v, i) => i + 1)

// 무작위 순열이 담길 배열을 선언한다.
const shuffle = [];

// candidate 배열이 0이 되기 전까지 반복
while (candidate.length > 0) {
	// 인덱스를 랜덤하게 추출한다.
    const random = Math.floor(Math.random() * candidate.length);
    // 고른 숫자는 candidate 배열에서 빼고, 해당 숫자를 spliceArray에 할당한다.
    const spliceArray = candidate.splice(random, 1);
	// spliceArray에는 랜덤한 값 하나만 있다. 이때 첫 번째 값을 추출한다.
    const value = spliceArray[0]; 
	// shuffle 배열에 value를 넣는다.
    shuffle.push(value); 
   }

이제 shuffle 배열에는 1부터 45까지의 숫자가 랜덤하게 정렬되어 있을 것이다.
이 중에서 6개의 숫자를 뽑는다면 0~5까지의 인덱스를 추출하면 된다.
뽑은 숫자를 오름차순으로 정렬하고 싶다면 sort 함수를 이용한다.

참고자료

렛츠 기릿 자바스크립트 프로그래밍
https://ko.wikipedia.org/wiki/%ED%94%BC%EC%85%94-%EC%98%88%EC%9D%B4%EC%B8%A0_%EC%85%94%ED%94%8C