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
tane olasılık var, yani isimleri
farklı şekilde atayabiliriz. Tüm permütasyonları oluşturup başarılı permütasyonlari sayarsak olasılığı da, çıkan toplamı
‘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
için de hesaplayabildim ama
için epey zorlandı.
Peki
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
matrisi,
elemanli bir durum için
elemanın kendi adını çektiği durumları içeren bir matris olsun. Burada şöyle ön çıkarımlar yapabiliriz;
–
elemanlı her durum için sonuç sıfırdır, yani 
– Herhangi bir durumda herkesin kendi ismini bulduğu durumlarin sayisi
‘dir, yani
.
Bu durumların dışında ise şunu söyleyebiliriz;
bize
elemanın olduğu durumda
elemanın kendi adını bulduğu, diğerlerinin yani
elemanın ise kendi adından farkli adları bulduğu durumların sayısını versin. Burada
elemanı
farklı şekilde seçebiliriz. Her bir seçenek icin geriye kalan
eleman ise kendi adından farklı bir adı seçecek. Bu da aslında bizim fonksiyonumuzdaki
sonucuna denk geliyor. Yani formülünü yazarsak;
(1) 
Burada tek istisnai durum ise şu;
durumunda ne yapacagiz?
iken denklem
(2) 
oluyor yani sonsuz döngüye giriyor. Bundan da şu şekilde kurtulabiliriz; daha öncesinde tüm olası
değerlerini hesaplamıştık.
satırındaki değerlerin toplamı,
elemanlı durum için permütasyon sayısını veriyor.
değerini de bu mantığı kullanarak
(3) 
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?