The Fisher-Yates Shuffle [ 셔플 알고리즘 ]

피셔-예이츠 셔플은 유한 수열을 무작위 순열로 섞기 위한 알고리즘 입니다.

출저 : https://ko.wikipedia.org/wiki/%ED%94%BC%EC%85%94-%EC%98%88%EC%9D%B4%EC%B8%A0_%EC%85%94%ED%94%8C

그림을 보면 뒤 섞을 문자 하나를 선택 할때 마다, 배열의 우측으로 밀어버려 선택이 안되게 하고 있습니다.

 

 

 

가장 간단하게 크기 5의 배열이 있다고 해보자

 

0 : 빨간색

1 : 초록색

2 : 파란색

3 : 주황색

4 : 보라색

 

1. 크기 만큼 랜덤 값 추출

처음으론 배열 크기가 5개이니 0 ~ 5 까지 랜덤으로 돌려주고, 가정으로 나온 값이 3(주황색)이라고 해보자

 

그러면 가장 처음으로 시작하는 것은 빨간색이니 둘을 바꾸어 준다

0 : 주황색 

1 : 초록색

2 : 파란색

3 : 빨간색

4 : 보라색

이렇게 위와 같은 배열이 됩니다. 

 

여기서 중요한 점은 이제 1번부터 시작하며, 랜덤 시작도 1 ~ 5 사이로 하기 때문에 주황색은 뽑히지 않게 됩니다.

 

2. 1 만큼 증가하며 반복을 해준다. 

배열의 크기는 똑같이 5칸 이지만 랜덤의 범위를 1 ~ 5로 해줍니다. 가정으로 나온 값이 4(보라색)라고 하였다면

 

 

0 : 주황색 

1 : 보라색 

2 : 파란색

3 : 빨간색

4 : 초록색

이렇게 위와 같은 배열이 됩니다. 

 

또한 1번은 다시 못뽑게 됩니다.

 

랜덤을 한번 더 돌려줍니다 (범위 2 ~ 5) 가정 : 3

 

0 : 주황색 

1 : 보라색 

2 : 빨간색

3 : 파란색 

4 : 초록색

이렇게 위와 같은 배열이 됩니다. 

 

랜덤을 한번 더 돌려줍니다 (범위 3 ~ 5) 가정 : 4

 

0 : 주황색 

1 : 보라색 

2 : 빨간색

3 : 초록색

4 : 파란색  

이렇게 위와 같은 배열이 됩니다. 

 

여기서 중요한 점은 마지막은 돌리지 않습니다.

 

왜냐하면 마지막은 랜덤으로 범위 4 ~ 5를 하여도 4가 나오게 되니 할 이유가 없습니다.

 

이렇게 해서 중복되지 않게 뽑을 수 있게 되는 알고리즘입니다.

 

 

 

    public T[] Shuffle<T>(T[] array)
    {
        for(int i = 0; i < array.Length - 1; i++) // array의 크기 -1만큼 이유는 마지막은 할 필요가 없어서
        {
            int rnd = Random.Range(i, array.Length); // 현재 순서에서 최대 어레이 크기만큼 랜덤으로 해줍니다.
            // Swap
            T temp = array[rnd]; // Swap 과정을 거치기 위해 임시 저장소 선언
            array[rnd] = array[i];
            array[i] = temp;
        }
        return array;
    }

 

간단하게 코드로 구현을 하였습니다.

 

가장 먼저 배열의 -1 값 만큼 for문을 돌려줍니다.

랜덤은 현재 진행중인(i)값에서 배열 크기만큼 돌려주고 나온 랜덤값이랑 현재 위치랑 Swap을 해주어 간단하게 구현을 하였습니다.