피셔 예이츠 셔플 ( Fisher Yates Shuffle )

피셔 예이츠 셔플 ( Fisher Yates Shuffle )

피셔 예이츠 셔플은 배열이나 리스트의 원소들을 무작위 ( Random )로 섞는 알고리즘이다.

모든 가능한 순열이 동일한 확률로 발생하도록 보장한다는 특징이 있다.

피셔 예이츠 셔플은 처음 기술한 로널드 피셔와 Frank Yates 의 이름을 따서 명명되었다.

도널드 커누스의 이름을 따서 커누스 셔플이라고 부르기도 한다.

배열의 끝에서부터 앞으로 이동하면서,
현재 위치 i 와 0 ~ i 사이 임의의 위치 j 를 뽑는다.
arr[ i ] 와 arr [ j ] 를 교환한다.
배열의 처음까지 진행하면, 전체 배열이 무작위로 섞인다.

 

 

동작 과정

1. 배열의 끝에서 시작한다. ( i = n - 1 )

2. 현재 인덱스 i 와 0 ~ i 사이의 무작위 인덱스 j 를 선택한다.

3. arr [ i ] 와 arr [ j ] 를 교환한다.

4. i = i - 1 로 감소시키며 배열 처음까지 이 과정을 반복한다.

5. 모든 과정이 끝나면 배열이 무작위로 섞인다.

 

 

 

의사코드 ( PseudoCode ) 표현

for (i = 배열의 마지막 인덱스 ~ 1까지 감소하면서 반복한다)
    0부터 i까지 범위에서 무작위 인덱스 r을 선택한다
    arr[i]와 arr[r]을 교환한다

 

 

C# 예제 코드

public static void FisherYatesShuffle(int[] inputArr)
{
    Random random = new Random();
        
    for (int i = inputArr.Length - 1; i > 0; i--) //인덱스 역순
    {
        int j = random.Next(0, i + 1); // 0부터 i까지 랜덤 인덱스 선택
            
        // 배열 요소 교환
        int temp = inputArr[i];
        inputArr[i] = inputArr[j];
        inputArr[j] = temp;
    }
}

 

 

▼출력

static void Main()
{
    int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        
    foreach(var a in numbers)
    {
        Console.Write(a + " ");
    }
        
    Console.WriteLine();
        
    FisherYatesShuffle(numbers);
        
    foreach(var a in numbers)
    {
        Console.Write(a + " ");
    }
}

 

 

정리

• 배열을 무작위로 섞는다 ( 정렬이 아님 )
• 끝에서 앞으로 오면서 무작위 인덱스와 교환
• 모든 순열이 균등 확률
• 카드 게임 , 랜덤 배치 등에 활용할 수 있다.