Permutasyon Algoritması

Yazan : Şadi Evren ŞEKER

Bu yazıyı Fatih Bey’in sorusu üzerine siteye eklemeye karar verdim. Fatih Bey’in sorusunu alıntılıyorum:

Hocam merhabalar bir soru sormak icin rahatsız etmiştim sizi,Bir fonksiyonumuz olsun ve parametre olarak zarSayisi alsin ve bu fonksiyon zar sayısına gore olası tum sonucları(zarların permutasyonunu ekrana bassın).ornegin zar sayısı 2 ise asagıdaki gibi sonuc elde etsin.

Cıktı : 11 12 13 14 15 16 21 22 23 24 25 26 31 32 33 34 35 36 41 42 43 44 45 46 51 52 53 54 55 56 61 62 63 64 65 66.

zarSayisi 3 ise aşagıdaki gibi

Cıktı: 111 112 113 114 115 116 121 122 123 124 125 126 211 212… seklinde

Hocam bu düz mantık ile kac zar sayısı varsa okadar ic ice dongu kurarak cozulebilir diye dusunmustum

mesela 3 zar var ise
for(i=1;i<=6;i++)
for(j=1;j<=6;j++)
for(k=1;k<=6;k++)
printf(“%d%d%d”,i,j,k);

Boyle dogru buluyor ancak 5,6,7 hatta 8 adet zar olursa butun durumlar icin ayrı dongu kurmakta sacma olacak.Isin icinden cıkamadıgım icin size sormak istedim hocam.Bunun bir matamatiksel denklemi varmı acaba veya optimum bir sonucu varmıdır ? Umarım anlatabilmişimdir derdimi hocam yardımınızı bekliyorum

Bu ti sorunlar, program yazarken sıklıkla karşımıza çıkabilir. Bu soru klasik bir permütasyon sorusudur, soruda bütün olasılıkların sırayla basılması istenir ( randomly permutate ).

Öncelikle bilgisayar bilimlerinde her şeyin bir hafıza X zaman tercihi (time X memory trade off) olduğunu bilmek gerekir. Yani ya zaman kazanır ya da hafıza kazanırsınız. İkisini birden kazanıyorsanız diğer herşeyi boşverebilirsiniz 🙂

Yukarıdaki problemde görüldüğü üzere aslında 6’nın n’inci kuvveti kadar (6 ⁿ ) işlem gerekmektedir. Bu anlamda bahsettiğiniz problemler, karmaşıklık sınıfı olarak NP sınıfıdır. Yani polinom zamanda çözülemeyen ancak çözümü polinom zamanda kontrol edilebilen (çözümünün doğruluğu) problem sınıfıdır. Malum n üzeri n bir polinom değildir.

Gelelim bu tip soruları nasıl çözebileceğimize. Öncelikle sizin probleminiz, performans kaygısından daha çok, zar sayısına göre bir algoritma geliştirmede çıkıyor. Yani, permütasyon problemleri için 6ⁿ performansına razı olsak bile , n tane zar için yukarıdaki problemin çözümünu algoritma olarak ifade etmemiz gerekiyor. Bunun için çeşitli yöntemler bulunmasına karşılık ben sizin probleminiz için sayılabilirlik teoreminin (countability theorem) iyi anlaşılması gerektiğini düşünüyorum.

Acaba yukarıdaki bu problemi bir sayma problemi haline indirgeye bilir miyiz? Cevabımız evet. Aslında bütün permütasyon problemlerini bu şekilde görmek mümkündür.

Bakın klasik sayı sistemi 10 farklı rakamdan oluşur (0,1,2,3,4,5,6,7,8,9) ve ben size 1’den 1000e kadar sayıları alt alta yazın desem, aslında sizin yaptığınız 3 haneli olarak bu 10 farklı rakamın permütasyonunu almaktır. Diğer bir deyişle bu sayılar arka arkaya arttırılırken aynı zamanda bütün permütasyonlarını belirli bir sırayla dolaşmış olursunuz.

Bizim yukarıdaki problemimizde de bir permütasyon alınması istenmiş ve bu permütasyonun normal sayılara göre iki farklı özel durumu belirtilmiş.

• Birinci farkımız sayılar 1-6 arasında.
• İkinci farkımız ise sayıların sayısı limitli. Yani zar sayısı ile ekrana basılacak sayıların sayısı arasında bir bağlantı bulunmalı.

Bu bilgiler ışığında iki şeyi görmemiz gerekiyor. Şayet ben size 6 sayı tabanında 0’dan başlayarak sayın dersem aşağıdaki şekilde bir sayma olacaktır:

0,1,2,3,4,5,10,11,12,13,14,15,20,21,22,…

Gördüğünüz üzere klasik olarak onluk sayı tabanındaki permütasyon işlemini 5lik sayı tabanına uygulamış oluyoruz. Yukarıdaki sayıların her hanesini 1 arttırırsak problem çözülmüş olur:

11,12,13,14,15,16,21,22,23,24,25,26,31,…

Elbette burada kaç zar olduğu problemi devam etmektedir. Örneğin 3 zar için başlangıç değerini 111 olarak kabul edip, 5 tabanındaki sayma sayılarımızı 111 arttırmalıyız. Yukarıdaki sayma sayılaırının ilk halini arttırdığımızda:

111,112,113,114,115,116,121,122,123,124,125,126,131,..

Şeklinde permütasyonu elde ederiz.

Gelelim bu sayıları arttırmaya ne kadar devam edeceğimize. Bu sorunun çözümü de oldukça basit. Olasılık teorisinden hatırlanacağı üzere n tane zar için 6 üzer n ihtimal bulunur.

Yukarıda bu söylediklerimizi C dilinde ifade edecek ve koda dökecek olursak:

Yukarıdaki kod, problemimizi çözmektedir. Bu kodda, zar sayısını n değişkeninde tutuyrouz. 29-32. satırlar arasında, yukarıda anlattığım zar sayısı kadar 1’den oluşan bir katar ekleniyor. Yani klasik sayma sayılarımız 0’dan başladığına göre örneğin zar sayısı = 5 için 11111 + 0 , 11111+ 1, … şeklinde her zar ihtimaline bir başlangıç değeri ekleniyor.

Kodun 36-39. satırları arasında sorunun çözümü yapılmakta ve görüldüğü üzere 6 üzeri n kadar dönmektedir.

Kodun 28. Satırında görüldüğü üzere basma işleminden hemen önce sayı, 6’lık tabana çevrilmektedir.

Kodun çıktısı aşağıdaki şekildedir:

Kodumuzu analiz ettiğimizde bu haliyle kodun herhangi bir performans artışı sağlamadığını söyleyebiliriz.

Kodun tamamını ayrıca dosya olarak siteye ekliyorum tıklayarak indirebilirsiniz.

Sırasız zar ihtimallerini basan algoritma

Yukarıdaki yazının yayınlanmasından sonra Sayın Cem Çankaya tarafından aşağıda bulunan ve acaba bu zarların sırasız olması halini nasıl basarız sorunu cevaplamaya çalışalım.

Problemi anlamak adına örneğin 2 adet zar atıldığında, 12 ile 21 ihtimalleri aynı oluyor. Yani zarların sırasının bir önemi kalmıyor.

Bu durumda yukarıda yayınladığımız algoritma işe yaramaz. Çözüm olarak problemimizi, yukarıda anlattığımız üzere sayma problemi haline getirmeye çalışalım. Sanırım problemi şu şekilde modellersek hata yapmamış oluruz.

n= 1 için

1,2,3,4,5,6

n=2 için

11,12,13,14,15,16,22,23,24,25,26,33,…

n=3 için

111,112,113,114,115,116,122,123,124,125,126,133,..222,223,224,..

Yukarıda vurgulamak istenen, her durumda birler hanesi 1-6 arasında ilk başta arttırılıyor. Ardından onlar hanesi 2 olduğunda birler hanesi geri 1den başlayıp artmıyor bunun yerine 2den devam ediyor. Yani örneğin 21 şeklinde bir değer hiç olmuyor çünkü bu zaten 12 olarak yazılmış.

Burası önemli çünkü şayet iki zar arasındaki bağlantıyı anlayabilirsek diğerlerini kolayca çözüyoruz.

Dizilimimizde, sağda olan bir zarın değeri hiç bir zaman solundakinden küçük olamaz dersek problem sayma problemi olarak (counting problem) çözülmüş oluyor.

Yani 3 zar için ilk iki zarın değerleri 13 oldutan sonra hiçbir şekilde 131 veya 132 olamaz. Problemin doğru çözülebilmesi için artık birler hanesi (en sağdaki hane) 3’ten başlamalıdır çünkü kendisinden önce bir adet 3 bulunmuş.

Aslında burada kendinden önce 3 bulunmuş ifadesi ile  anlatılmak istenen kendinen önce 3ten küçük sayıların olduğu ihtimaller kapsanmış demektir.

Problemi bu şekilde modelledikten sonra performans artışı için bir de olaya dinamik programlama ekleyelim (dynamic programming).

Problem normalde zar sayısı n olmak üzere,  6 üzeri n kadar (6n) dönüp bu döngüler sırasında uygun olmayan zarları elemeli. Oysaki bu döngülerde istenmeyen zarlar için de döngümüz gereksiz yere dönecek. Acaba bunu engelleyip sadece istediğimiz zarlar kadar döngüyü döndürmenin bir yolu var mıdır?

Bu soruya cevap olarak yukarıda, ilk kodu yazarken yaptığım yorumu hatırlayalım. Bilgisayar bilimlerinde herşey zaman X hafıza tercihidir (time X memory trade off). Dolayısıyla dinamik programlama bize zaman kazandırmak adına, hafızada belirli durumları tutmayı ve bu durumların yeniden hesaplanmamasını sağlamayı hedefler.

Geçen örneğimizde olduğu gibi, bütün zar ihtimallerini tek bir int değişkende tutmak yerine bu sefer, dinamik programlama uyguluyor ve zarın her hanesini ayrı bir dizi değişkeninde tutuyoruz. Örneğin n adet zar için n adet elemanı olan bir dizi oluşturuyoruz.

Problemimiz bu sefer sayma işleminin bu diziye nasıl uygulanacağına dönüşüyor. Ben çözüm olarak aşağıdaki şekilde bir kod yazdım:

Yukarıdaki kodda, amacımız k isminde n elemanlı bir diziyi alıp son hanesini (yani n-1. haneyi) 1 arttırmaktır. Ancak son hane 1 artınca 6 yüzü olan zar için bu değer 2,3,4 gibi sayılar olduğunda problem olmazken 6’dan 7’ye çıkınca problem olmaktadır. Sayma problemimiz icabı, buradaki sayı 7 olunca bir soldaki hanenin arttırılması gerekir.

Örneğin dizinin içindeki değerler 11666 olsun. son hane 1 artınca 11667 olacaktır. Oysaki böyle bir zar ihtimali olamaz. Çözüm olarak bir soldaki hane artacak ve bu haneden 6 çıkarılacaktır. 11671 tekrar düzeltilecek 11711 tekrar düzelecek 12111 olacaktır.

Problemin buraya kadar olan kısmını 7-13. satırlar arasındaki döngü  çözmektedir.

Bu çözüm yine yeterli değildir çünkü daha önce anlattığım üzere sağdaki bir değer, solundaki bir değerden küçük olamaz. Yani yukarıdaki gibi 12111 şeklinde bir değer bulunduysa, bu değerin 12222 olarak düzeltilmesi gerekir.

Problemin bu kısmının çözümü için de 14-16. satırlar arasındaki döngü çalışmakta ve sağdaki bir değerin solunda küçük olması halindde bu değeri eşitlemektedir.

Gelelim bir diğer probleme. Bizim kodumuz n adet zar için kaç tane değer hesaplayacak?

Bu sorunun cevabı belki olasılık teorisine göre formüllenip hesaplanabilir ancak bilgisayarların nümerik güncünü kullanarak bu problemi de kolayca çözebiliriz. Sayma teorimiz gereği, sayma işlemimiz, 6 yüzlü bir zar için 1’den başlayıp 6’da biter. Öyleyse dizimizin ilk hanesi (en soldaki hane) 6 olunca problem bitmiştir 🙂

Bu kontrolde aşağıdaki main kodunda görüldüğü gibi kolayca yapılabilir:

Görüldüğü üzere kodun 35. satırında, dizinin ilk elemanının 6’dan küçük veya eşit olması istenmiştir.

Kodun örnek çalışmaları aşağıda verilmiştir:

Yukarıda, 5e kadar olan durumları test ettim ve bir problem göremedim. Umarım sorunuza cevap olmuştur.

Kodun tamamına erişmek için bu bağlantıyı tıklayabilirsiniz.