Fisher-Yates shuffle은 배열의 모든 순열이 같은 확률로 나오도록 뒤에서부터 하나씩 임의 위치와 교환하는 섞기 알고리즘입니다.
매번 전체 범위에서 아무 원소나 고르는 naive shuffle은 경우의 수가 순열 개수와 맞지 않아 편향이 생길 수 있고, Fisher-Yates는 선택 범위를 줄여가며 이 문제를 피합니다.
핵심 정리
naive shuffle은 각 위치마다 전체 배열에서 임의 인덱스를 고르기 때문에 선택 과정의 경우의 수가 순열 개수와 딱 맞지 않습니다. 그래서 어떤 순열은 더 자주 나오고 어떤 순열은 덜 나올 수 있습니다. Fisher-Yates는 마지막 위치부터 시작해 현재 위치 이하의 원소 중 하나를 골라 교환합니다. 이렇게 하면 첫 단계는 n가지, 다음은 n-1가지, 그 다음은 n-2가지로 줄어 전체 경우의 수가 순열 개수와 맞아 균등한 섞기를 만들 수 있습니다.
- naive shuffle은 구현이 쉬워 보이지만 순열 확률이 균등하지 않을 수 있습니다.
- Fisher-Yates는 뒤쪽 원소부터 확정해 나갑니다.
- 현재 위치 i에서는 0부터 i까지의 인덱스 중 하나를 고릅니다.
- 선택한 원소와 현재 위치의 원소를 swap합니다.
- 선택 범위가 한 칸씩 줄어들어 전체 경우의 수가 n factorial과 맞습니다.
- 본문 뒤쪽의 sort 메모는 배열 섞기와 별도로 정렬 comparator 예시로 볼 수 있습니다.
원문은 shuffle 설명 뒤에 Java sort 메모가 이어져 글의 중심이 흐려졌습니다. 이번 보강은 Fisher-Yates가 왜 unbiased인지 먼저 설명하고, sort 부분은 별도 메모로 읽으면 된다는 위치를 잡아줬습니다.
이어서 볼 글
- C++ sort 사용법: 배열 정렬, compare 함수, lambda 정렬 - 본문 뒤쪽의 sort 메모를 C++ 배열 정렬과 커스텀 compare 예제로 확장한다.
일반적으로 셔플 알고리즘을 떠올리면 다음과 같은 naive solution을 생각하기 쉽다.
void LnNumber::ShuffleArray(long* arr, long count)
{
for (int i=0;i<count;i++)
{
long toInx = rand() % count;
{//swap
long temp = arr[i];
arr[toInx] = arr[i];
arr[i] = temp;
}
}
}하지만 위 코드는 순진해보이는 겉모습과 다르게 엄청난 바이어스를 포함하고 있는데,
카드 3장의 모든 순열은 3!(=3 x 2 x 1) = 6이지만 위의 toInx를 보면 3 x 3 x 3 = 27로 6으로 나눠떨어지지 않는 경우의 수를 가지고 있다!
따라서 아래처럼 덜 직관적이지만 n!에 맞춘 경우의 수를 가진 코드로 수정해줘야 한다.
이 코드를 Fisher-Yates shuffle이라고 한다.
void LnNumber::ShuffleArray(long* arr, long count) {
for (int i = count - 1; i > 0; i--) {
long toInx = rand() % (i + 1); // 0부터 i까지의 랜덤한 인덱스(i포함)
// swap
long temp = arr[i];
arr[i] = arr[toInx];
arr[toInx] = temp;
}
}이코드의 toInx를 보면 카드3장의 예시에서 3 x 2 x 1 = 6 = 3!의 경우의 수를 가진다.
sort
가장 기본적인 sort는 Array.sort()또는 Collections.sort()를 쓰면 된다. (char[] 같은건 전자만 가능한듯?)
struct node 같은걸 쓰면서 특정 필드에 대해 소팅하고 싶으면 다음 기법을 쓰자.
class Tweet {
Long time;
int tweetId;
}
List<Tweet> feed;
...
//time에 대해서 sort하고 싶을때
feed.sort((t1, t2) -> t1.time.compareTo(t2.time));
//역순을 원하면 t1, t2를 바꿔준다.
feed.sort((t1, t2) -> t2.time.compareTo(t1.time));
//약간 올드하게 아래처럼도 가능
Collections.sort(feed, new Comparator<Tweet>() {
@Override
public int compare(Tweet t1, Tweet t2) {
return t1.time.compareTo(t2.time);
}
});여러 필드에 대해서 복잡하게 정렬해야하면 아래 방법 사용
feed.sort(Comparator.comparing((Tweet t) -> t.time)
.thenComparing(Comparator.comparing((Tweet t) -> t.tweetId).reversed()));'Programming > Algorithm' 카테고리의 다른 글
| LIS(Longest Increasing Subsequence) - 가장 긴 증가하는 부분 수열 (0) | 2023.08.13 |
|---|---|
| 두 선분 교차점 구하기: CCW 판정과 C++ 구현 (0) | 2023.07.25 |
| meet in the middle 알고리즘 (0) | 2022.03.02 |
| 투 포인터 알고리즘 개념: 부분합과 두 수 합 패턴 (0) | 2022.03.01 |
| 이분 그래프 판정: BFS DFS 색칠 알고리즘 (0) | 2022.02.22 |
