Bu yazımda, Fisher Yates algoritmasının tanımı ve kullanım alanları hakkında bilgiler vereceğim.

Tanım

Fisher Yates, bir Shuffling algoritmasıdır. Algoritma, sonlu bir diziyi O(n) karmaşıklıkla kendi içerisinde random bir şekilde dağılımını sağlar.

Algoritma N boyutlu bir dizi için;

- Diziden rastgele 0, N-1 indisleri arasında rastgele bir indis seçilir.
- Seçilen indisteki eleman ile dizinin son eleman yer değiştirilir.
- N bir azaltılır ve N = 0 olana kadar adımlar tekrarlanır.

şeklinde çalışır.

Bu yazıda daha çok kullanım alanları ile bilgi vermeye çalışacağım. Tanım için : Fisher Yates

Nereden esti ?

Son zamanlarda oyun ve grafik programlamaya olan ilgimden dolayı youtube üzerinde bir çok kanal takip ediyorum. Bu kanallardan en çok beğendiğim ise Sebastian Lague. Kendisi unity oyun motoru çok ilginç işler ortaya çıkartıyor. Kanalında videolarını incelerken Obstacle Placement videosunda Fisher Yates algoritmasından bahsetmişti. Algoritmanın çözdüğü sorun hoşuma gittiği için bunu bir blog yazısına dökmek istedim. Aynı zamanda ilk blog yazım olma özelliğine de sahiptir bu yazı :)

Birçok programlama dili kendi Collection kütüphaneleri içerisinde shuffle fonksiyonuna sahip. Örneğin; Java, Collection.shuffle(List<?> list) static fonksiyonu ile parametre olarak verdiğiniz koleksiyonu random bir şekilde karıştırmanızı sağlar. Diğer yandan bazı diller bu operasyonun ihtiyaca göre farklı tanımlamalar olabileceği için bunu built-in bir fonksiyona dönüştürmüyolar. Bknz: Dotnet runtime için 2015 yılında açılan bir github issue Add a static Shuffle method to Array and an instance method to List. Bu durumda ek bir paket veya kütüphane kullanmanız veya kendi algoritmamızı ihtiyaçlarımıza göre kendimiz tanımlamamız gerekiyor.

Örnekler

Python İmplementasyonu

import random

arr = [1,2,3,4,5,6,7,8,9]

for i in range(0, len(arr) - 1):
  rand = random.randint(0, len(arr) - 1 - i)
  temp = arr[rand]
  arr[rand] = arr[len(arr) - 1 - i]
  arr[len(arr) - 1 - i] = temp
  
print(arr)

Çıktı :

    [5, 2, 6, 8, 7, 3, 4, 1, 9]

Unity Scritping API ile Random Map

Sebastian Lague yapmış olduğu örnek bana eskiden yayınlanan Şahane Pazar programındaki bir yarışmayı hatırlattı. Yarışmacılar, bir platform üzerinde ilerlemeye çalışıyor ama bu platformdaki kutuların bazılarında boya var ve yarışmacılar hangi kutularda boya olduğunu bilmiyorlar.

Basit olarak bu yarışmanın platformunu Unity aracılığı ile oluşturalım.

Shuffle Fonksiyonu

Fonksiyon parametre olarak bir nesne dizisi alıyor ve içerisindeki nesneleri algoritmaya göre karıştırıyor ve tekrar bir nesne dizisi dönüyor.

public static class MapUtil
{
    public static T[] ShuffleList<T> (T[] list){
        
        System.Random random = new System.Random();
        for (int i = 0; i < list.Length; i++){
            int rand = random.Next(0 , list.Length - 1 - i);
            T temp = list[list.Length - 1 - i];
            list[list.Length - 1 - i] = list[rand];
            list[rand] =  temp;
        }
        return list;
    } 
}

Shuffle fonksiyonuna Map koordinatlarımızı içeren listeyi dizi olarak veriyoruz ve karıştırılmış bir dizi olarak başka bir listeye atıyoruz.

List<Vector3> shuffledPositions = new List<Vector3>(MapUtil.ShuffleList(positions.ToArray()));

Rastgele kutularımızı ise bir döngü içerisinde istediğimiz adet kadar Instantite ediyoruz.

for(int i = 0 ; i < 15; i++){
    GameObject newObstacle = Instantiate(obstacle, shuffledPositions[i], obstacle.transform.rotation);
}

Tüm bunların sonunda oluşan görüntü;

Toparlarsak

Kısaca daha önce Sebastian Lague‘ın 3D yaptığı bir map generator sınıfını 2D uzay için gerçekleştirmiş olduk. İyileştirmeler ile daha ilginç işler ortaya çıkabilir ama basitçe bir Shuffle algoritmasının kullanım alanına değinmiş olduk.

Diğer yazılarda görüşmek üzere 👋.