[js] 피셔 예이츠 셔플, 알고리즘

 

피셔-예이츠 셔플 알고리즘에 대하여

알아보겠습니다. 

 

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

 값을 랜덤 하게 섞을 때 사용하는 알고리즘입니다. 

로날드 피셔(Ronald Fisher)와 프랭크 예이츠(Frank Yates)가 만들어
피셔-예이츠 셔플이라고 합니다. 

제로초님의 자바스크립트를 이용한 게임을 구현하면서 
이 셔플을 알게 되었고, 랜덤 정렬이 필요할 경우마다 사용되므로
아주 유용한 알고리즘입니다. 

저는 자바스크립트를 이용한 게임 야구, 로또 추첨기, 카드 뒤집기 게임에서 사용하였고,
음악 앱에서 음악 랜덤 플레이를 만들때도 사용한다고 합니다. 

 

피셔 예이츠 셔플 예제

숫자 야구 

//숫자뽑기 
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 = []; 
  //[9],[5],[2],[7] 같이 array가 4개 나오기 때문에 [0]으로 앞자리만 뽑음 
  //splice()가 index를 하나씩 빼주기 때문에 뽑을 숫자가 하나씩 줄음 
  //안했을 경우, 랜덤 숫자가 undefined가 나옴 -> 9-i로 index 수 반영 
  fourNum = candidate.splice(Math.floor(Math.random() * (9 - i)), 1)[0]; 
  chosenNum.push(fourNum); 
} 
console.log(chosenNum); //콘솔로 랜덤 숫자 확인

 

로또 추첨기

while (candidates.length > 0) { 
  let num = Math.floor(Math.random() * candidates.length); //0-44까지의 정수 
  //candidates에서 num을 splice()로 하나씩 빼줌 
  let leftNum = candidates.splice(num, 1)[0]; 
  //leftNum 배열이므로 [0] 
  mixedNum.push(leftNum); 
 } 

 

카드 뒤집기

const backColor = ['#FFC312', '#FFC312', '#C4E538', '#C4E538', '#12CBC4', 
'#12CBC4', '#ED4C67', '#ED4C67', '#FDA7DF', '#FDA7DF', '#833471', '#833471'] 
let chosenColor = []; 
while (backColor.length > 0) { 
	let color = Math.floor(Math.random() * backColor.length); //0-13까지 정수 
    let mixedColor = backColor.splice(color, 1)[0]; 
    chosenColor.push(mixedColor); 
  } 
 console.log(chosenColor);