셔플링 알고리즘은 게임이나 무작위 정렬을 할 때 자주 접하는 일반적인 무작위 문제입니다. 이는 다음과 같이 추상화될 수 있습니다. M 내의 모든 자연수의 무작위 시퀀스 배열을 얻습니다.
Baidu에서 "Shuffling Algorithm"을 검색하면 첫 번째 결과는 "Baidu Library-Shuffling Algorithm"입니다. 내용을 스캔한 후 결국 배열 대신 연결된 목록을 사용하는 것을 포함하여 많은 내용이 쉽게 다른 사람을 잘못된 길로 인도할 수 있습니다. 또한 제한된 최적화일 뿐입니다(연결된 목록도 읽기 효율성을 떨어뜨립니다).
이 글의 첫 번째 방법은 간단하게 설명할 수 있습니다. 카드를 무작위로 뽑아 다른 그룹에 넣습니다. 빈 카드를 뽑으면 다시 뽑습니다.
"빈 카드를 뽑았다면 다시 뽑으세요." 이렇게 하면 나중에 빈 카드를 뽑을 확률이 높아지는 것은 분명 불합리한 일입니다.
한 단계로 최적화할 수 있습니다. 카드를 제거한 후 원래 카드가 줄어듭니다. (빈 카드를 놔두는 대신)
코드는 다음과 같습니다.
//매번 카드 한 장을 뽑아 다른 더미에 넣습니다. 배열에서 요소를 추출하고 모든 후속 요소를 하나씩 앞으로 당겨야 하기 때문에 시간이 많이 걸립니다.
var arr2 = new Array();
for (var i=m; i>0; i--) {
var rnd = Math.floor(Math.random()*i);
arr2.push(arr[rnd]);
arr.splice(rnd,1);
}
return arr2;
}
또한 배열이 매우 큰 경우 중간에 요소를 삭제하면 후속 대기열이 앞으로 이동하게 되어 매우 시간이 많이 걸리는 작업이기 때문에 분명히 문제가 있습니다.
"왜 그 요소를 삭제하는가?"를 기억하세요. 목적은 빈 카드를 생성하는 것이 아닙니다.
해당 요소를 삭제하는 것 외에 빈 카드를 제거할 수 있는 다른 방법이 있나요?
---네, 뽑지 않은 마지막 카드를 뽑은 위치에 놓기만 하면 됩니다.
이 아이디어를 다음과 같이 최적화할 수 있습니다.
//매번 카드 한 장을 뽑아 다른 더미에 넣습니다. 뽑지 않은 마지막 카드를 빈 자리에 놓습니다.
var arr2 = new Array();
for (var i=m; i>0;) {
var rnd = Math.floor(Math.random()*i);
arr2 .push(arr[rnd]);
arr[rnd] = arr[--i];
}
return arr2;
}
//한 라운드 후에 i번째 카드를 다른 카드로 교체
for (var i=0; i
temp = arr[rnd];
arr[rnd] = arr[i];
arr[i]=temp;
}
return arr;
}
카드를 뽑고 교환하는 아이디어 외에도 카드를 삽입하는 아이디어도 활용할 수 있습니다. 먼저 카드가 하나 있고, 두 번째 카드에는 무작위로 삽입할 수 있는 위치가 두 군데 있습니다(전후 첫 번째 카드), 세 번째 카드를 무작위로 삽입할 수 있는 위치는 세 군데(뒤, 첫 번째, 두 번째) 등
코드는 다음과 같습니다.
위 코드에도 몇 가지 문제가 있습니다. 카드 수가 늘어날수록 카드를 삽입하면 이후에 많은 카드가 뒤로 밀려나게 되기 때문에 카드 삽입이 점점 더 어려워집니다.
물론 적절하게 최적화할 수도 있습니다. 먼저 n-1개의 카드가 있고 n번째 카드가 끝에 배치된 다음 임의의 카드와 위치를 바꿉니다.
코드는 다음과 같습니다.
전체 코드는 다음과 같습니다. 관심 있는 학생들은 자신의 컴퓨터에서 실행해 보고 각자의 실행 효율성과 최종 결과가 이론적으로 무작위인지 확인할 수 있습니다.