PYTHON İLE TEKRARLI PERMÜTASYON ÖRNEĞİ

Soru:

alt text

A'dan B'ye gidilebilecek en kısa kaç yol vardır?

Çözüm: Bu soruda A noktasından başlayacaksak en kısa yol için bütün yolları şu şekilde düşünebiliriz: Sağa ve sağ alta. Zaten sola alta gitmeye gerek yoktur.

4 kere sağ alta 2 kere sağa gitmeyi A'dan B'ye giderkenki en kısa mesafe olarak tanımlayabiliriz. Örneğin sağa alta gitmek için X'i, sağa gitmek için Y değişkenlerini tayin edelim.

Yollar şu şekilde sıralabilir. XXXXYY XXXYYX . . . YYXXXX

Tekrarlı permütasyon olmasını sağlayan kısıtın X ve Y'lerin tekrar etmesi olduğunu görmekteyiz.

O zaman cevap şu şekilde olur. (4+2)! / (4!.2!) = 15

In [0]:

def faktoriyelHesapla(i):
    
    if i==1:       
        return 1
    
    else: 
        return i * faktoriyelHesapla(i-1)

In [6]:

X = 4
Y = 2

sonuc = faktoriyelHesapla(X + Y) / (faktoriyelHesapla(X) * faktoriyelHesapla(Y))
print("Gidilebilecek en kısa yolların sayısı = ",sonuc)

Gidilebilecek en kısa yolların sayısı =  15.0

Soruda şöyle bir değişiklik yaparsak;

alt text

Eğer işaretlenen yerden geçiş yapmak kısıtlanırsa o zaman geçilebilecek en kısa yol sayısı ne olur ?

Çözüm:

alt text

Eğer Tüm durumlardan;

A'dan C'ye gidilen yollar ve D'den B'ye gidilen yollar çıkarılırsa çözüm elde edilir.

Tüm durumları zaten bulmuştuk (15)

O zaman

A'dan C'ye (1 + 1)! / (1! * 1!)

ile

D'den B'ye (2 + 1)! / (2! 1)

sonuçlarını çarpıp tüm durumlardan çıkarırsak sonucu elde etmiş oluruz.

In [7]:

XAC = 1
YAC = 1

XDB = 1
YDB = 2

AC = faktoriyelHesapla(XAC + YAC) / (faktoriyelHesapla(XAC) * faktoriyelHesapla(YAC))
DB =faktoriyelHesapla(XDB + YDB) / (faktoriyelHesapla(XDB) * faktoriyelHesapla(YDB))
print("Gidilebilecek en kısa yolların sayısı = ",sonuc - (AC * DB))

Gidilebilecek en kısa yolların sayısı =  9.0