[알고리즘] 피셔-예이츠 셔플(Fisher-Yates Shuffle) 알고리즘

피셔 - 예이츠 셔플은 무작위 순열을 생성하기 위한 알고리즘입니다. 

 

예시 :

섞으려고 하는 숫자를 모두 모자에 넣은 뒤,

배열안에 숫자가 남아있지 않을 때까지 무작위로 숫자를 모자에서 뽑습니다.

 

 

코드 

이 알고리즘은 C#으로 구현하였습니다.

using System;
using System.Collections.Generic;

class Shuffle
{
    public static Random rng = new Random();

    static void Main(string[] args)
    {

        List<int> list = new List<int>() { 1, 2, 3, 4, 5, 6, 7, 8 };

        Shuffle_List(list);

        foreach (var item in list)
        {
            Console.WriteLine(item);
        }
    }

    public static void Shuffle_List<T>(List<T> list)
    { 
        int n = list.Count;
        while (n > 1)
        {
            n--;
            int k = rng.Next(n + 1);
            T value = list[k];
            list[k] = list[n];
            list[n] = value;
        }
    }
}

 

 

결과 :