개요

매번 index를 Random.Range를 통해 랜덤으로 뽑는 것 대신
미리 List를 랜덤으로 정렬해놓고 앞에서부터 뽑아오는 방식을 택하려고 찾아봤다.
그 랜덤 정렬 알고리즘 중 하나인 Fisher-Yates Shuffle 를 사용해서 적용해봤다.

Fisher-Yates Shuffle Algorithm

방식은 간단하다.
인덱스 i가 섞이는 방법은
1. 0부터 i 인덱스까지 랜덤으로 선택한다.
2. 선택된 인덱스의 숫자와 i번째 인덱스 숫자를 바꾼다.

이 방식으로 마지막 인덱스부터 0번 인덱스까지 순회하면서 반복한다.

for (int i = values.Count - 1; i > 0; i--)
{
    int k = random.Next(i + 1);
    T value = values[k];
    values[k] = values[i];
    values[i] = value;
}

찾아보니 이 방식으로 섞게되면 섞인 결과로 나올 수 있는 모든 수열의 확률이 동일하다고 한다.

이 알고리즘은 편향되지 않은 순열을 생성한다(모든 순열은 생성될 가능성이 동일하다).

C# List Extension 구현

    private static Random random = new Random();

    public static void Shuffle<T>(this IList<T> values)
    {
        for (int i = values.Count - 1; i > 0; i--)
        {
            int k = random.Next(i + 1);
            T value = values[k];
            values[k] = values[i];
            values[i] = value;
        }
    }

이런식으로 코드를 짜게 되면 List클래스에서 extension느낌으로 shuffle을 사용할 수 있게된다!

List<int> a = new();
//a에 이런저런 원소 넣어준 후
a.shuffle();

이런식으로 shuffle 함수 호출하면 Fisher-Yates Shuffle알고리즘이 적용된다.

레퍼런스

https://data-pandora.tistory.com/entry/C-랜덤-배열리스트-셔플하기-Fisher-Yates-알고리즘 [데이터 판도라:티스토리]