머리말
자바스크립트로 프로그래밍을 하던 중 배열의 요소를 무작위로 섞어야 되는 상황이 발생했다. 자바스크립트 내부 함수에서 제공되는 sort 함수를 사용해서 랜덤 하게 섞는 방법도 존재하지만, 일부 자바스크립트 엔진에 따라 균등한 분배가 이루어지지 않는 경우가 발생한다. 그렇기 때문에 본 포스팅에서는 배열 요소를 랜덤 하게 섞되, 모든 배열의 가능성이 균등하게 섞이는 방법에 대해 소개한다.
배열의 요소를 무작위로 섞는 방법
머리말에서 소개한 내용과 같이 자바스크립트 엔진마다 다를 수 있지만, sort 내부 함수를 활용해서 배열의 요소를 무작위로 섞을 수 있다. 아래와 같은 코드를 수행하면 3개의 배열에 1, 2, 3 각각의 숫자를 할당한 뒤, 배열의 경우의 수를 출력할 수 있다.
// sort 내부함수를 활용한 배열의 요소를 무작위로 섞는 함수
function arrayShuffle(array){
array.sort(() => Math.random() - 0.5);
}
// 무작위로 섞인 배열 요소가 균등하게 섞였는지 확인하기 위해
// 배열에 할당된 1, 2, 3 배열 값으로 구성할 수 있는 모든 경우의 수 나열
var count={
'123': 0,
'132': 0,
'213': 0,
'231': 0,
'321': 0,
'312': 0
};
// 반복문을 10,000번 수행하면서 경우의 수 통계
for(var i = 0; i < 10000; i++){
var array = [1, 2, 3];
arrayShuffle(array); //무작위 재배열 함수 호출
count[array.join('')]++; //통계 정보 저장
}
// 통계 정보를 저장한 count 변수 출력
for(var key in count){
console.log(key+': '+count[key]);
}
배열의 재배열 결과가 특정한 배열에 치우쳐져 있는 모습을 확인할 수 있다. 무작위란 모든 경우의 수가 균등하게 반환되어야 그 의미에 부합하지만, sort 내부 함수에 의한 무작위 재배열은 그럴듯해 보이지만 진정한 무작위가 아니다. 이렇게 균등하지 못한 이유는 sort 내부 함수의 엔진에 해답이 있다. sort 내부함수는 값의 크고 작음을 기준으로 정렬하기 위한 목적인 자바스크립트 엔진이다. 이러한 동작 원리로 무작위 재배열을 수행했지만, 정렬의 원리로는 무작위 재배열이 완벽하지 않을 수 있다는 결론이 나온다.
이러한 문제는 다양한 방법으로 해결을 제시할 수 있는데, 본 포스팅에서는 피셔 에이츠 셔플(Fisher Yates Shuffle) 알고리즘을 통해 해결하는 방법을 소개한다. 피셔 에이츠 셔플 알고리즘은 배열의 끝 요소에서 출발하며 앞에 위치한 요소들 중 랜덤 한 인덱스의 요소와 변경한다. 이를 자바스크립트 코드로 구현하면 아래와 같다.
function arrayShuffle(array) {
for(var i = array.length - 1; i > 0; i--){ // 배열의 끝 요소에서부터 시작 요소까지 진행
var j = Math.floor(Math.random() * (i + 1)); // 현재 인덱스(i) 미만의 무작위 인덱스 추출
[array[i], array[j]] = [array[j], array[i]]; // 무작위로 추출된 인덱스와 재정렬
}
}
꼬리말
피셔 에이츠 셔플 알고리즘을 통해 재정렬한 배열을 통계해 보면 균등한 경우의 수로 재배열된 결과를 확인할 수 있다. 조금 더 무작위라는 단어에 알맞은 방법으로 배열을 재배열할 수 있게 되었다. 또한 자바스크립트 엔진에서 제공하는 sort 함수를 사용하지 않았기 때문에 조금 더 향상된 성능으로 재배열을 수행할 수 있다. 피셔 에이츠 셔플 알고리즘을 통해 배열의 요소를 재배열하는 방법에 대해서 소개한 본 포스팅은 이로써 마무리를 짓도록 한다.
소중한 댓글 (0)