[C#] 중복 없는 랜덤

중복 없이 랜덤 숫자나 객체를 뽑는 알고리즘을 생각해보면, 간단하게 이미 뽑은 숫자를 뽑은 경우에 랜덤을 다시 돌리는 방법을 생각해 볼 수 있습니다.  구글링 해보면 많이 나오는 방법이기도 하죠. 다음은 그 방법을 이용해서 0에서 (N-1)까지의 숫자를 랜덤으로 뽑는 프로그램입니다.

using System;
using System.Linq; // 배열 초기화 - Enumerable 사용

static void Main(string[] args)
{
    Random random = new Random();
    
    int N = Convert.ToInt32(Console.ReadLine());

    bool[] selected = Enumerable.Repeat<bool>(false, N).ToArray<bool>();
    int selectedCnt = 0;

    while(selectedCnt < N)
    {
        int a = random.Next(0, N); // 1에서 N-1까지
        if(selected[a] == true)
        {
            continue;
        }

        Console.Write($"{a} ");
        selected[a] = true;
        selectedCnt++;
    }
}

이 방법은 최소 N의 시간이 걸리지만 최대 무한대의 시간이 걸릴 수도 있는 방법입니다. 말 그대로 '랜덤'이기 때문입니다. 수학적으로 평균 소요 시간이 어느 정도인지는 모르겠지만, 랜덤으로 뽑아야 하는 값이 많아질수록, 더욱 오래걸릴 것이라는 것은 직관적으로 뚜렷하게 알 수 있습니다.

이 글에서는 모집단이 커져도 랜덤 값을 확실한 시간 내에 뽑아낼 수 있는 방법에 대해 적어 보려 합니다. C#을 기준으로 설명할 예정이고, 간단하게 모집단의 모든 원소는 0부터 n-1까지의 정수라고 생각합시다. (총 n개)

 

1. 이미 뽑은 것을 뽑았다면, 그 다음 것을 뽑기

제목 그대로, 이미 뽑은 것을 뽑았다면 그 다음 것을, 그것도 이미 뽑았다면 또 그 다음 것을 뽑는 방식입니다.

using System;
using System.Linq; // 배열 초기화 - Enumerable 사용

static void Main(string[] args)
{
    Random random = new Random();
    
    int N = Convert.ToInt32(Console.ReadLine());

    bool[] selected = Enumerable.Repeat<bool>(false, N).ToArray<bool>();
    int selectedCnt = 0;

    while(selectedCnt < N)
    {
        int a = random.Next(0, N); // 1에서 N-1까지
        while(selected[a] == true)
        {
            a = (a+1) % N;
        }

        Console.Write($"{a} ");
        selected[a] = true;
        selectedCnt++;
    }
}

서론에서 언급한 코드에서 if문 내부만 바꿔주어 간단하게 구현할 수 있으며 O(N²)의 시간복잡도로 예측가능한 실행시간을 가졌으나, 이 방법으로 얻는 랜덤값은 확률적으로 오류가 있습니다.

간단하게 1에서 3까지의 숫자를 뽑는 중에 이미 1을 뽑은 상태라고 해봅시다. 오류가 없다면, 이 때 2를 뽑을 확률과 3을 뽑을 확률은 같아야 하겠죠. 하지만 위 알고리즘의 경우 1을 뽑으면 그 다음 원소인 2를 뽑아야 하기 때문에 (2를 뽑을 확률 = 1을 뽑을 확률 + 2를 뽑을 확률 = 2/3) ≠ (3을 뽑을 확률 = 1/3) 이므로 확률에 오류가 있음을 알 수 있습니다.

모집단이 커질수록 이 확률의 차이는 무시해도 될 만큼 작아지며, 구현이 아주 간단하기 때문에, 모집단이 크고 확률의 정확도가 그리 중요하지 않은 경우에 쓰면 좋습니다. 다만 확률이 정확하면 훨씬 좋겠죠.

 

 

2. 모집단의 인덱스를 랜덤으로 뽑고, 모집단에서 원소 제거.

List<int> list에 1부터 n까지의 원소를 채운다.
list의 크기는 현재 n.
    0~(n-1)의 숫자 중 "인덱스"를 랜덤으로 뽑고 해당 인덱스의 원소를 삭제한다.
list의 크기는 현재 (n-1).
    0~(n-2)의 숫자 중 "인덱스"를 랜덤으로 뽑고 해당 인덱스의 원소를 삭제한다. ...

이러한 과정을 반복해서 뽑는 것입니다.

using System;
using System.Collections.Generic;

static void Main(string[] args)
{
    Random random = new Random();

    int N = Convert.ToInt32(Console.ReadLine());

    List<int> list = new List<int>();
    for(int i=0 ; i<N ; ++i)
    {
        list.Add(i);
    }

    for(int i=0 ; i<N ; ++i)
    {
        int a = random.Next(0, N-i);
        Console.Write($"{list[a]} ");
        list.RemoveAt(a);
    }
}

O(N²)의 시간복잡도로, 실행 시간을 예측가능한 상태로 랜덤을 뽑을 수 있으며, 위의 방법과는 달리 우리가 통상적으로 생각하는 비복원 추출을 그대로 구현했기 때문에 확률도 정확합니다. 다만 메모리를 더 쓴다는 단점이 있는데, 요즘 같은 시대에는 단점이라고 보기도 어렵겠지요.

(2024.10.22 추가)
이를 좀 더 최적화해서 O(N)에 수행하는 방법이 있습니다. 원소를 제거하는 작업을, Swap을 이용하는 것으로 대체하는 것입니다. 굳이 Remove해줄 필요 없이, 랜덤으로 뽑은 인덱스와 현재 인덱스의 값을 서로 바꿔주기만 하는거죠. i가 증가하면서 선택된 인덱스의 값은 더이상 고려되지 않기 때문에 위에서 Remove해준 것과 같은 효과가 나는 것입니다.

using System;
using System.Collections.Generic;

static void Main(string[] args)
{
    Random random = new Random();

    int N = Convert.ToInt32(Console.ReadLine());

    int[] array = new int[N];
    for(int i=0 ; i<N ; ++i)
    {
    	array[i] = i;
    }

    for(int i=0 ; i<N ; ++i)
    {
        int a = random.Next(i, N);
        Console.Write($"{array[a]} ");
        
        // swap
        int temp = array[a];
        array[a] = array[i];
        array[i] = temp;
    }
}

이 코드가 전부 돌아가면, array는 Knuth's (Fisher-Yates) 셔플이 된 상태가 됩니다.
배열을 피셔-예이츠 셔플하면서 그때 그때 뽑은 숫자를 출력하는 게 위 코드가 되겠고,
모두 셔플을 돌린 후에 하나씩 순회하는 것도 좋은 방법이겠네요.