Shuffle 알고리즘 (Fisher-Yates Shuffle, Knuth Shuffle)

Fisher-Yates Shuffle (피셔 예이스 셔플) 알고리즘은 랜덤 값을 이용해, 배열을 uniform하게 섞을 수 있는 알고리즘이다. 한번 순환 (1 iterator)로 셔플을 완성할 수 있다.

 

매우 간단하다.

 

랜덤하게 숫자 하나를 뽑고 그 값을 인덱스로 치환한다음 그 값과 현재 값을 swap한다.

// Fisher-Yates Shuffle Algorithm
void Shuffle(std::vector<int>& arr)
{
	int n = arr.size();
	for (int i = n - 1; i > 0; i--)
	{
		int j = rand() % (i + 1);		
		swap(arr[i], arr[j]);
	}
}

 

하나 주의할 점은 랜덤 값을 얻는 함수로 rand()를 사용했기 때문에 시드를 설정 해줘야 한다.

 

#include <iostream>
#include <ctime>
#include <random>
#include <vector>

using namespace std;

// Fisher-Yates Shuffle Algorithm
void shuffle(vector<int>& arr)
{
	int n = arr.size();
	// 배열의 마지막 요소부터 첫 요소까지 하나씩 섞음
	for (int i = n - 1; i > 0; i--)
	{
		// 0부터 i까지의 임의의 인덱스 j를 선택
		int j = rand() % (i + 1);
		// arr[i]와 arr[j]를 교환			
		swap(arr[i], arr[j]);
	}
}

int main() {
    srand(time(0)); // 시드 설정

    vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	const int size = arr.size();
    
    cout << "Original array: ";
    for (int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;

    shuffle(arr);

    cout << "Shuffled Array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}