BİLDİRİ DETAY

Murat Erşen BERBERLER, Mehmet Oğuz YARDIMCI, Uğur ELİİYİ, Zeynep Nihan BERBERLER
KOMBİNASYON VE PERMÜTASYON SAYIMLAMA İÇİN ÖZET FONKSİYON ÖNERİLERİ
 
Giriş: Kombinasyon n elemanlı bir kümenin r elemanlı alt kümelerinin kaç farklı şekilde düzenlenebileceğini bulmak için kullanılan matematiksel bir ifade olup permütasyon ise n elemanlı bir kümenin r elemanlı bir alt kümesinin sıra gözetilmek suretiyle kaç farklı şekilde düzenlenebileceğini bulmakta kullanılır. Yalnızca düzenlemelerin sayısı ile ilgilenilmeyip aynı zamanda her birinin yazdırılması da istenirse özyinelemeli ve geri izlemeli algoritma teknikleriyle bu amaca ulaşılabilir ve hatta istenirse sözlüksel sırada da yazdırılabilir, dolayısıyla herhangi bir düzenlemenin sözlüksel sırada kaçıncı olduğu tüm durumlar ele alınarak yani sayımlama yoluyla bulunabilir. Amaç: Bu çalışmada kombinasyon için r elemanlı alt kümelerden ve permütasyon için de r elemanlı düzenlemelerden özel olarak seçilen herhangi bir tanesinin tüm düzenlemeler içinde sözlüksel olarak kaçıncı sırada olduğu sayımlama yapılmaksızın önerilen özet fonksiyonlar yardımıyla hesaplanacaktır. Kapsam: n elemanlı kümenin r elemanlı alt kümeleri ve r elemanlı düzenlemelerinin tamamı önerilen özet fonksiyonların kapsamı dahilindedir. Burada r değeri 1 ile n arasında herhangi bir tamsayı olabilmektedir. Sınırlıklar: Teorik olarak herhangi bir sınırlama olmamakla birlikte geleneksel yöntemlerin ve bu çalışmada önerilen özet fonksiyonların hesaplanması için kodlamada kullanılacak programlama dilinin barındırdığı tamsayı veri tipinin büyük sayıları içerecek şekilde seçilmiş olması gerekmektedir. Yöntem: Kombinasyon özet fonksiyonu için önerilen yöntemi basitçe anlatabilmek adına n=4 seçildiğinde olası r değerlerine karşılık elde edilecek alt kümeler boş küme hariç bir, iki, üç ve dört elemanlılar olmak üzere {{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},},{1,2,3,4}} şeklinde olacaktır. Burada r=1 veya r=4 alındığında özel durumlar oluşacağı ve yapı çok basit olacağı için açıklamaya gerek duyulmamıştır. Oysa r=2 seçildiğinde sözlüksel sırayla oluşacak {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}} 6 adet alt kümenin kendi içinde birinci terime göre sırasıyla 3, 2 ve 1 eleman içeren 3 gruba ayrıldığı görülmektedir. Benzer şekilde r=3 seçildiğinde sözlüksel sırayla oluşacak {{1,2,3},{1,2,4},{1,3,4},{2,3,4}} 4 adet alt kümenin kendi içinde birinci terime göre sırasıyla 3 ve 1 eleman içeren 2 gruba ve 3 eleman içeren ilk grupta da ikinci terime göre sırasıyla 2 ve 1 eleman içeren 2 alt gruba ayrıldığı görülmektedir. Yöntemin esası bu gözlem üzerine kuruludur, şöyle ki; öncelikle ilgili elemanın bulunduğu grubun toplam eleman sayısı kadar pozitif katkısı ve elemanın grup içinde yer aldığı pozisyon kadar negatif katkısı hesaplanmalıdır. Bu hesaplamalar sözlüksel sırası belirlenecek kümenin tüm elemanları için yapıldığında ve kümülatif toplandığında istenen değer elde edilecektir. Örneğin, r=2 alınıp beşinci sırada yer alan {2,4} seçildiğinde, bu alt kümenin birinci elemanı olan 2'nin bulunduğu gruptaki eleman sayısı 6 olduğundan pozitif katkı olarak alınacak ve 2'nin grup içindeki başlangıç pozisyonuna ulaşmak için de 3 değeri çıkarılacaktır. 2'den önce gelen eleman olan 1'in bulunduğu grupta kaç kez yer aldığı yani 3 sayısı ise Pascal Üçgeni'nden bir başka deyişle yine kombinasyon yardımıyla hesaplanmıştır. Benzer şekilde alt kümenin ikinci elemanı olan 4'ün bulunduğu gruptaki eleman sayısı 2 olduğundan pozitif katkı olarak alınacak ve 4'ün grup içindeki başlangıç pozisyonuna ulaşmak için de 1 değeri çıkarılacaktır. Sonuç olarak edilen sayılar toplandığında ve sonuca 1 sayısı ilave edildiğinde istenen 6-3+2-1+1=5 değeri bulunacaktır. Permütasyon özet fonksiyonu için önerilen yöntemi basitçe anlatabilmek adına n=4 alınarak ve r=1 seçildiğinde özel durum oluşacağı ve yapı çok basit olacağı için açıklamaya gerek duyulmamıştır. r=3 ve r=4 seçildiğinde sözlüksel sırayla oluşacak 24 adet düzenlemenin kendi içinde birinci terime göre 6 eleman içeren 4 gruba ve ikinci terime göre de 2 eleman içeren 3 gruba ayrıldığı görülmektedir. Yöntemin esası da bu gözlem üzerine kuruludur, şöyle ki; r uzunluklu en son düzenleme referans alınarak her bir grubun kaç eleman içereceği kolaylıkla bulunabilir. r=3 olduğunda en sonda yer alan (4,3,2) düzenlemesinin ikinci elemandan sonrakilerin çarpımı birinci grubun eleman sayısını vermektedir ve burada 6'dır, son olarak üçüncü elemanı da ikinci grubun eleman sayısını vermektedir ve burada 2'dir. Gruplardaki eleman sayıları belirlendikten sonra ilgilenilen düzenlemenin yerini kesin olarak tayin etmede kullanılacak negatif katkı vektörünün hesaplanması gerekmektedir. Bunun için r uzunluklu düzenlemenin ikinci indisindeki elemanından başlanmak üzere kendinden önce gelenlerin kaç tanesinden büyük olduğuna bakılır ve bu değer ilgili indise negatif katkı olarak yazılır, eğer ilgili indisteki değer kendinden önce gelenlerin hepsinden küçük ise katkısı sıfır olarak yazılır. Örneğin (2,3,4) düzenlemesini ele alırsak ikinci indiste bulunan 3 sayısı kendisinden önce gelen 2'den büyük olduğu için negatif katkısı -1 olacaktır, sonrasında ele alınan 4 sayısı kendinden önce gelen 2 ve 3 sayılarından büyük olduğu için negatif katkısı -2 olacaktır. Önerilen özet fonksiyon (2,3,4) düzenlemesi örneği üzerinden anlatılacak olursa öncelikle bu düzenlemeye ait negatif katkı vektörünün [0,-1,-2] olduğu görülecektir. İlk adımda (2,3,4) düzenlemesi ile negatif katkı vektörü toplanır ve [2,2,2] vektörü elde edilir. İkinci adımda elde edilen sonuç vektöründe her bir indise ait değerden 1 sayısı çıkarılır ve böylece [1,1,1] vektörü elde edilir. Üçüncü adımda [1,1,1] vektörü gruplardaki eleman sayıları vektörü [6,2,1] ile skaler olarak çarpılır, 6*1+2*1+1*1=9. Dördüncü ve son adımda ise elde edilen sonuca 1 sayısı eklenir, 9+1=10 ve istenen sonuç elde edilir. Sonuç: Önerilen özet fonksiyon önerileri, özyinelemeli ve geri izlemeli yaklaşımları kullanılarak C programlama dilinde kodlanmış olup 64 bit Windows 7 işletim sistemi bulunan i5 3.3 GHz işlemciye ve 8 GB belleğe sahip bir bilgisayar üzerinde hesaplama denemeleri yapılmıştır. Denemelerde kullanılan tüm kodlar http://kisi.deu.edu.tr/zeynep.berberler/ksibofo/ ve http://kisi.deu.edu.tr/murat.berberler/psibofo/ adreslerinde yer almaktadır. Hesaplama denemelerinde süre üst limiti 600 sn olarak belirlenmiştir; özyinelemeli yöntem kullanılan kombinasyon için n=49 ve geri izlemeli yöntem kullanan permütasyon için de n=19 seçilmiş olup kombinasyonda r=12'den sonra, permütasyonda da r=10'den sonra sonuç alınamamıştır. Oysa önerilen her iki özet fonksiyon ile hesaplama zamanı 0 sn olarak elde edilmiştir.

Anahtar Kelimeler: Kombinasyon, Permütasyon, Sözlüksel sıra, Sayımlama, Özet Fonksiyon



 


Keywords: