C# Fisher-Yates Shuffle 알고리즘

오리지널 Fisher-Yates Shuffle 알고리즘

1. 길이가 n인 배열을 생성한다.
2. [0, n - 1] 범위의 무작위 인덱스를 뽑아서 새로운 배열에 추가한다.
3. 기존 배열의 n - 1 위치의 원소를 무작위로 뽑혀 나간 위치에 추가한다.
   (한 칸씩 당겨서 해당 빈칸을 채우는 방법도 있지만 그때는 length - n개만큼 움직여야 해서 비효율적이다.)
4. 다음으로 [0, n - 2] 범위의 무작위 인덱스를 뽑아서 새로운 배열에 추가한다.
5. 기존 배열의 n - 2 위치의 원소를 무작위로 뽑혀 나간 위치에 추가한다.
6. 해당 과정을 반복한다.

무작위로 인덱스 하나를 선택해서 새 배열에 추가한다.

무작위로 뽑혀져 나간 자리에 맨 마지막 원소를 채워넣는다.

계속해서 무작위로 인덱스 하나를 선택해서 새 배열에 추가한다.

무작위로 뽑혀져 나간 자리에 맨 마지막 원소를 채워넣는다. 이제 이 과정을 반복한다.

예제 코드

public partial class Program
{
    private static Random random = new Random();

    static void Main(string[] args)
    {
        int[] ints = new int[] { 1, 2, 3, 4, 5 };

        Console.Write("Before:");

        foreach (var i in ints)
        {
            Console.Write($"{i} ");
        }

        Console.WriteLine();

        Console.Write("After:");

        foreach (var i in Shffle(ints))
        {
            Console.Write($"{i} ");
        }
    }

    private static T[] Shffle<T>(T[] array)
    {
        int n = array.Length;
        var sortArray = new T[n];

        for (int i = 0; i < n; i++)
        {
            int last = n - 1 - i;

            var index = random.Next(0, last + 1);
            sortArray[i] = array[index];
            array[index] = array[last];
        }

        return sortArray;
    }
}

 

모던 Fisher-Yates Shuffle 알고리즘

오리지날 Fisher-Yates Shuffle의 문제점은 새로운 배열이 필요하다는 점이다. 이를 개선한 현대적인 Fisher-Yates Shuffle 알고리즘을 알아보자.

 

1. [0, n - 1] 범위에서 무작위 인덱스를 뽑아, 해당 원소를 인덱스 0에 위치한 원소와 바꾼다.
2. [1, n - 1] 범위에서 무작위 인덱스를 뽑아, 해당 원소를 인덱스 1에 위치한 원소와 바꾼다.
3. 이를 0번에서 n - 2번까지 반복한다.
   (마지막 원소(n - 1)는 바꿀 대상이 자기 자신밖에 없으므로 포함하지 않는다.)

 

모던 Fisher-Yates Shuffle은 추가 배열을 필요로 하지 않는다.

마지막 n - 2 인덱스까지만 진행하면 셔플이 완료된다.

예제 코드

public partial class Program
{
    private static Random random = new Random();

    static void Main(string[] args)
    {
        int[] ints = new int[] { 1, 2, 3, 4, 5 };

        Console.Write("Before:");

        foreach (var i in ints)
        {
            Console.Write($"{i} ");
        }

        Console.WriteLine();

        Console.Write("After:");

        MordernShuffle(ints);

        foreach (var i in ints)
        {
            Console.Write($"{i} ");
        }
    }

    private static void MordernShuffle<T>(T[] array)
    {
        for (int i = 0; i < array.Length - 1; i++)
        {
            var randomIndex = random.Next(i, array.Length);
            Swap(array, i, randomIndex);
        }
    }

    private static void Swap<T>(T[] array, int n, int m)
    {
        var temp = array[n];
        array[n] = array[m];
        array[m] = temp;
    }
}

 

참고 사이트

Fisher-Yates Shuffle 간단 정리