[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해줄 필요 없이, 뽑은 인덱스와 가장 끝 부분(처음 또는 마지막)의 인덱스의 값을 서로 바꿔주기만 하는거죠.

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;
    }
}

Knuth's (Fisher-Yates) 셔플을 이용한 방법이라고 합니다. 다르게 생각하면, 배열을 단순하게 피셔-예이츠 셔플을 한번 거친 후에 그걸 처음부터 순회하면, 자연스럽게 비복원 추출이 되겠네요!