Fisher-Yates Shuffling Algoritması

Giriş

Bu algoritma Array gibi random access veren veri yapılarında kolayca kullanılır. 

Bir diziyi shuffle yapmak için, tüm dizi üzerinde tersten dolaşıp, bir sayı üretir ve üzerinde olduğumuz elemanla yer değiştiririz. Üretilen sayı üzerinde bulunduğumuz [0,indeks] aralığındadır. Tersten dolaşmamızın sebebi RNG'lerin genelde [0,x) aralığında sayı üretmesi.

Düzden de dolaşsak, tersten de dolaşsak, önemli olan daha önce shuffle ettiğimiz kısma dokunmamak. Bu yüzden nextInt(i+1) şeklinde kodluyoruz.

Bir çok programlama dilinde shuffle işlemi için çözüm bulunuyor. Böylece Fisher-Yates gibi algoritmalar bilmek zorunda kalmıyoruz.

Örnek - Java

Şöyle yaparız. nextInt() exclusive olduğu için uzunluğun bir fazlası verilir.

// Implementing Fisher–Yates shuffle
static void shuffleArray(int[] ar)
{
  Random rnd = new Random();
  for (int i = ar.length - 1; i > 0; i--)
  {
    int index = rnd.nextInt(i + 1);
    // Simple swap
    int a = ar[index];
    ar[index] = ar[i];
    ar[i] = a;
  }
}

Örnek - C++

Aynı algoritmanın C++ ile gerçekleştirilmiş için şöyle yaparız. rand() exclusive olduğu için uzunluğun bir fazlası verilir.

void shuffleString (std::string& s){
  for(int i=s.size()-1;i>0;i--){
    std::swap(s[rand()%i+1],s[i]));
  }
}

Örnek - C

Şöyle yaparız. Burada kendi rand_ranged_inclusive() metodumuz olduğu için uzunluğun bir küçüğü verilir.

// Fisher-Yates (Durstenfield)
int shuffle(int arr[], int len)
{
  for (int i = 0; i < len; ++i) {
    int j = rand_ranged_inclusive(i, len-1);
    SWAP_INT(arr[i], arr[j]);
  }
}