Dün akşam bir tane soruya denk geldim. Bir tane şirket soruyu yazmış, bunu çözebiliyorsanız başvurun falan demiş. Soru şu şekilde;
8 tane amca var, kağıtlara kendi isimlerini yazıp bir kutuya atıyorlar. Sonra hepsi kutudan rastgele bir kağıt çekiyor. Bu da herkes kendi adından farkli bir kağıt çekene kadar devam ediyor. Herkesin kendi adından farklı kağıt çekme olasılığı kaçtır?
Brute force çözüm olarak düşününce elimizde toplam \({n!}\) tane olasılık var, yani isimleri \({n!}\) farklı şekilde atayabiliriz. Tüm permütasyonları oluşturup başarılı permütasyonlari sayarsak olasılığı da, çıkan toplamı \({n!}\)'e bölerek bulabiliriz. Yani aşağıdaki gibi.
|
|
import itertools n = 8 is_ok = lambda arr: reduce(lambda x, y: x and y[0] != y[1], enumerate(arr), True) res = len([1 for a in itertools.permutations(list(xrange(n)), n) if is_ok(a)]) print res / float(reduce(lambda n1, n2: n1 * n2, xrange(1, n+1), 1)) |
Kodu en kısa nasıl olabilir diye yazdığım için performans olarak idealden uzak. Bu haliyle \(n=9\) için de hesaplayabildim ama \(n=10\) için epey zorlandı.
Peki \(n > 9\) gibi durumlar için ne yapabiliriz? Burada tüm olasılıkları hesaplamak artık biraz zorlaşıyor. Onun yerine bir fonksiyon tanımlayip soruyu daha kısa zamanda cözebiliriz.
Diyelim ki \(D\) matrisi, \(n\) elemanli bir durum için \(k\) elemanın kendi adını çektiği durumları içeren bir matris olsun. Burada şöyle ön çıkarımlar yapabiliriz;
- \(0\) elemanlı her durum için sonuç sıfırdır, yani \(D_{0, i} = 0, i = 0 .. n\)
- Herhangi bir durumda herkesin kendi ismini bulduğu durumlarin sayisi \(1\)'dir, yani \(D_{i, i} = 1, i = 1 .. n\).
Bu durumların dışında ise şunu söyleyebiliriz; \(D_{i, k}\) bize \(i\) elemanın olduğu durumda \(k\) elemanın kendi adını bulduğu, diğerlerinin yani \(i-k\) elemanın ise kendi adından farkli adları bulduğu durumların sayısını versin. Burada \(k\) elemanı\(\binom{i}{k}\) farklı şekilde seçebiliriz. Her bir seçenek icin geriye kalan \(i-k\) eleman ise kendi adından farklı bir adı seçecek. Bu da aslında bizim fonksiyonumuzdaki \(D_{i-k, 0}\) sonucuna denk geliyor. Yani formülünü yazarsak;
\[D_{i, k} =\binom{i}{k} * D_{i-k, 0}\]
Burada tek istisnai durum ise şu; \(k = 0\) durumunda ne yapacagiz? \(k = 0\) iken denklem
\[D_{i, 0} =\binom{i}{0} * D_{i, 0}\]
oluyor yani sonsuz döngüye giriyor. Bundan da şu şekilde kurtulabiliriz; daha öncesinde tüm olası \(D_{i, k}\) değerlerini hesaplamıştık. \(D_i\) satırındaki değerlerin toplamı, \(i\) elemanlı durum için permütasyon sayısını veriyor. \(D_{i, 0}\) değerini de bu mantığı kullanarak
\[D_{i, 0} ={i!} - \sum\limits_{k=1}^i D_{i, k}\]
formülüyle hesaplayabiliriz.
Bunun da kodunu kısa olsun diye uğraşarak aşağıdaki gibi yazdim
|
|
n = 8 fact = [reduce(lambda a, b: a * b, xrange(1, num+1), 1) for num in xrange(0, n + 1)] cmb = [[fact[c] / (fact[c-k] * fact[k]) for k in xrange(c+1)] for c in xrange(n+1)] dp = [[0 for _ in xrange(n+1)] for __ in xrange(n+1)] for i in xrange(1, n+1): dp[i][i] = 1 for i in xrange(n+1): for j in xrange(i-1, 0, -1): dp[i][j] = cmb[i][j] * dp[i-j][0] dp[i][0] = fact[i] - sum(dp[i]) print float(dp[n][0]) / fact[n] |
Kodlarda ya da mantığımda herhangi bir hata var mı sizce?
