배열의 요소를 무작위로 섞기

📌 배열의 요소를 무작위로 섞기

로또 프로젝트를 진행하면서 테스트 코드를 구현하기 위해 배열의 요소를 랜덤으로 입력받는 코드를 구현하고자 했다. 

하지만 자바스크립트는 파이썬의 random 모듈과 같은 배열의 요소를 랜덤 한 방법으로 바꾸는 기능을 제공하지 않으므로 배열의 요소를 섞기 위해서는 기능을 직접 구현해서 사용해야 한다는 것을 알게 되었다. 이를 직접 구현해보도록 하자!

✏️ 자바스크립트로 배열의 요소를 무작위로 섞어보자

자바스크립트에서 배열을 무작위로 섞는 방법은 sort() 메서드와 Math.random() 메서드를 이용하여 구현할 수 있다.

function shuffle(array) {
  array.sort(() => Math.random() - 0.5);
}

let arr = [1, 2, 3];
shuffle(arr);

sort와 random을 활용한 무작위 정렬 결과

위 코드를 통해 간단하게 무작위 함수를 구현할 수 있다.

arr 배열은 아래와 같이 [1, 3, 2]로 무작위로 순서가 변경된 것을 확인할 수 있다.

이때 Math.random() - 0.5 의 계산 결과는 양수나 음 수 둘 중 하나이기 때문에 정렬 함수는 요소를 무작위로 재 정렬할 수 있게 한다.

하지만 sort는 이런 용도로 만들어진 메서드가 아니기 때문에 숫자 1, 2, 3으로 만들 수 있는 순열이 같은 빈도로 발생하지 않을 수 도 있다.

예시를 통해 실제 빈도수를 확인해보도록 하자.

function shuffle(array) {
  array.sort(() => Math.random() - 0.5);
}

// 1, 2, 3으로 만들 수 있는 모든 순열의 빈도를 측정하기 위한 객체
let count = {
  '123': 0,
  '132': 0,
  '213': 0,
  '231': 0,
  '321': 0,
  '312': 0
};

for (let i = 0; i < 1000000; i++) {
  let array = [1, 2, 3];
  shuffle(array);
  count[array.join('')]++;
}

shuffle 메서드를 백만번 실행시켜 가능한 한 모든 결과의 빈도를 측정해보자.

// 만들 수 있는 모든 순열의 생성 빈도 출력
for (let key in count) {
	console.log(`${key}: ${count[key]}`);
}

실행 결과는 위와 같다. (자바스크립트 엔진마다 다를 수 있음)

실행 결과 빈도가 한쪽으로 지나치게 편향될 수 있다는 것을 알게 되었다.

실행 결과는 자바스크립트 엔진마다 다를 수 있지만, 기존의 코드는 빈도가 다른 문제점을 가지고 있다.

해당 결과의 발생 원인은, sort를 실행했을 때 내부 로직으로 인해 발생하는 문제로, 추가적인 방식을 통해 빈도를 같게끔 유도하도록 하자.

✏️ 피셔-예이츠 셔플(Fishcer-Yates shuffle) 알고리즘 활용

피셔-예이츠 셔플 알고리즘은 배열 끝 요소부터 시작해 앞으로 하나씩 나아가면서 해당 요소 앞에 있는 임의의 요소와 해당 요소를 바꿔치기하는 알고리즘이다.

// "구조 분해 할당(destructuring assignment)" ver
function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
		// 무작위로 index 값 생성 (0 이상 i 미만)
    let j = Math.floor(Math.random() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]];
  }
}

// 구조 분해 할당을 사용하지 않은 코드
function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1)); 

		// 임시 변수에 원본 값을 저장하고, 랜덤 값 j를 사용해 배여
    let t = array[i]; 
		array[i] = array[j]; 
		array[j] = t
  }
}

새로 작성한 함수를 실행해서 빈도를 측정해보자.

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

// 1, 2, 3으로 만들 수 있는 모든 순열의 빈도 측정
let count = {
  '123': 0,
  '132': 0,
  '213': 0,
  '231': 0,
  '321': 0,
  '312': 0
};

for (let i = 0; i < 1000000; i++) {
  let array = [1, 2, 3];
  shuffle(array);
  count[array.join('')]++;
}

// 만들 수 있는 모든 순열의 생성 빈도 출력
for (let key in count) {
	console.log(`${key}: ${count[key]}`);
}

피셔-예이츠 알고리즘 방식의 정렬 결과

실행 결과 모든 순열이 거의 유사한 빈도로 만들어 진것을 확인할 수 있다.

이로써 기존의 함수보다 더욱 고른 결과값을 획득할 수 있을 뿐만 아니라 피셔-예이츠 알고리즘은 ‘정렬' 연산도 없기 때문에 성능상 이점 또한 가지고 있다.

 

---

참고

• https://ko.javascript.info/task/shuffle

배열 요소 무작위로 섞기

• https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle​

Fisher–Yates shuffle - Wikipedia