Hayırlı forumlar 
Arkadaşlar merhaba bir algoritma sorum var ve çözemiyorum yardımcı olur musunuz?
Soru şu:
1’den 48’e kadar olan sayılardan, sayıları istediğimiz kadar kullanarak, bir sürü 8’er küme oluşturuyoruz. Karşımızdaki kişi ise bize 5 tane rastgele sayı söylüyor. Biz sayıları 8’er öyle gruplamalıyız ki o bize hangi 5 sayıyı söylerse söylesin, onun söylediği sayıları içeren bir kümemiz mutlaka olsun. Bu kümelerin sayısı minimum ne olabilir?
48*47*46*45*44
/ 8
Edit: Bölü kısmından emin değilim. 8 * 7 * 6 da olabilir, 8 de olabilir sadece. 8! de olabilir. Düşüneyim biraz.
Son kararım şu şekilde
P(48,5)/P(8/5)
Öncelikle merhaba, cümle olarak anlamadığım bi nokta var. 8’er küme derken neyi kastediyor ?
8 elemanlı mı 8 farklı küme mi ? Bu birincisi. Burada bi mutabık olalım. Bunun dışında anladığım kadarıyla mutabık olacağımız yerde bi değişiklik yok ise cevap C(48,8).C(8,5)/5! olmalıdır.
1 'den 48 kadar sayıları kullanarak 48**8 (48 'in 8 'inci kuvveti) olacaktır. Binom açılım konusu
Örnek X ve Y değerlerini tekrarlı olarak XX, XY, YX, YY şeklinde yazabilirsiniz. 2 değer 2 kez yazılırsa 2 'ni karesi olur. Yani 4 değişik yazılabilir. aynı harfi 3 defa olsa XXX, XXY, XYX, XYY, YYY, YYX, YXX, YXY yani 2 üzeri 3 ve 8 değişik değer elde edilir.
5 sayı seçme kısmında bu kümeleri denk gelen kısmını bende bağlayamadım
Permutasyon/kombinasyondan pek anlamam, ama:
Teorik minimum tam sayi degil. (5, 3, 2) parametrelerini aldigimizda her 3’lu grup soylenen 10 ciftten (C(5, 2)) 3’unu karsilayabiliyor (C(3, 2)). Bolumleri 3.3̅, cevap 4. ((1,2,3), (1,4,5), (2,3,4), (2,3,5))
Formul varsa ⌈C(N, q) / C(k, q)⌉ oldugundan supheleniyorum; taban veya toplama islemi kullanmayan, ozyinelemeli veya parcali olmayan fonksiyonlara da guvenmiyorum.
Oynama koduna da basladim da bugunluk foruma ayirdigim vaktin sonuna geldigim icin havada birakiyorum:
import itertools
def solve(N, g, ask):
Nset = list(range(1, N + 1))
queries = list(itertools.combinations(Nset, ask))
all_sets = list(itertools.combinations(Nset, g))
satisfy = lambda query, sets: any([all([(qe in s) for qe in query]) for s in sets])
assert satisfy([1], [[1], [2]]) == True
assert satisfy([2], [[1], [2]]) == True
assert satisfy([3], [[1], [2]]) == False
assert satisfy([1], [[1, 2], [2, 3]]) == True
assert satisfy([2], [[1, 2], [2, 3]]) == True
assert satisfy([3], [[1, 2], [2, 3]]) == True
assert satisfy([1, 2], [[1, 2], [2, 3]]) == True
assert satisfy([2, 3], [[1, 2], [2, 3]]) == True
assert satisfy([1, 3], [[1, 2], [2, 3]]) == False
assert satisfy([1, 2, 3], [[1, 2], [2, 3]]) == False
satisfy_all = lambda queries, sets: all([satisfy(q, sets) for q in queries])
assert satisfy_all([[1], [2], [3]], [[1], [2]]) == False
assert satisfy_all([[1], [2], [3]], [[1, 2], [3]]) == True
assert satisfy_all([[1, 2], [2, 3]], [[4, 1, 2], [4, 2, 3]]) == True
assert satisfy_all([[1, 2], [2, 3], [1, 3]], [[1, 2, 3]]) == True
assert satisfy_all([[1, 2], [2, 3], [1, 3]], [[1, 2], [2, 3]]) == False
hocam bu kullanım python’a mı ait. hiç duymadığım kullanım sizin gibi python’u nasıl öğrenebilirim.
Merhaba,
Benim fikrim de şu şekilde.
Şimdi 8 elamanlı bir kumeyi ele alalım.
Öncelikle bizim 8 elemanlı bir küme ile en fazla kaç tane istek karşılanabilir buna bakalım. Bunu şu şekilde buluruz:
C(8,5)
Eğer bir küme C(8,5) tane isteği karşılayabiliyorsa 48^5 tane olasılığı karşılamak için kaç tane küme lazım bize. Burası önemli, kemerlerinizi sıkı bağlayın.
İstekler:
1, 2, 3, 4, 5
1, 2, 2, 3, 3
1, 3, 3, 3, 3
Bu istekleri tek bir küme ile rahatça karşılanabilir:
1,2,3,4,5,6,7,46
Yani anlatmaya çalıştığım şey şu: rasgele seçilen sayıların aynı olması önemli bile değil. Eğer biz 5 tane birbirinden farklı rastgele sayı seçersek 5 tane birbirinden aynı sayı ile uğraşmamıza gerek kalmaz, yani anlatmaya çalıştığım şey şu:
1,2,3,4,5 → 1,2,3,4,5
1,2,2,3,3 → 1,2,3
1,3,3,3,3 → 1,3
Bakın 1,2,3,4,5 olarak seçilen sayılar nasıl da 1,2,2,3,3 ve 1,3,3,3,3 ü karşıladı. Sadede gelirsek tüm istekleri karşılayacak minimum küme sayısını bulmamız için
48^5 / C(8,5) yapmamıza gerek bile yok. Doğru cevap bu değil
Doğru cevap:
C(48, 5) / C(8,5)
Cevabımız için yeterlidir. Eğer yanlışım varsa lütfen belirtin bir şeyler öğrenmiş olurum.
Hayır, adamımız ne yazmış sorusunda
Hocam sıralama yapmıyoruz, eleman seçiyoruz. O yüzden permütasyon değil de kombinasyon kullanmak daha mantıklı bence.
Edit:
Hocamızın bu noktasını kaçırmışım cevap o zaman
⌈C(48, 5) / C(8, 5)⌉
Olmalı, müsait bir zamanda tekrar bakmalıyım
açıkçası soru mu hatalı cevaplar mı ben mi anlamadım. çünkü
dediğine göre( ki bu durumda kümeden neden bahsedilmiş) ve 5 sayı seçtiğine göre 3 sayı seçmemiz lazım 48 sayı var. istediğimiz kadar seçebiliyorsak da bi şey değişmicektir(48 * 48 * 48) diye düşünüyorum. kombinasyon ve permütasyonda farklı elemandan oluşan kümeler seçiyorduk değil mi?
ayrıca burda maximum küme demesi gerek miyor mu? nitekim cevaplarda da oluşabilecek tüm ihtimalleri düşünmüşler
Benim anladığım kadarıyla sayısal loto tarzı bir şeyde 5 tutturmak için kaç tane 8 li küme yapmak istediği gibi bir durumu anlamaya çalışıyor.
Merhaba,
Şöyle diyeyim, 9 elemanlı bir kümede alt küme oluşturmak için en fazla 5 sayı kullanabilirsin desek nasıl, olur, istediğin kadar sayı kullanabilirsin desek nasıl olurdu? Bence bu ifade kafanı karistirmasın.
Buna nasıl ulaştın hala anlayamadım. Beynim yandı 
Ama iyi de o zaman ben olayı
2^48 deyip direkt kapatirdim, sorunun da bir esprisi kalmazdı.
iyi ama sayıları istediğimiz kadar kullanabiliyorsak 1,1,1,1,1,1… de bir küme olmaz mı
İşte bu küme olmaz. Aynı sayıdan iki tane olamaz ki bir küme içinde.
import itertools
print(list(itertools.product(range(1,49), repeat=8)))
1 'den 49 ’ a kadar 48 elemanlı 8 'er li tekrarlı 48**8 olur (1,1,1,1,1,1… küme olur ancak
5 sayı seçeceğiz bu sayıların aynı sayıları seçmediğinizi düşünürsek 5 eleman kümeler ise
from itertools import combinations
kom = combinations(range(1,49), 5)
for i in list(kom):
print (i)
İki çıktının kümlerini nasıl değerlendirmek gerektiğini çözemedim burada biraz açıklayıcı bilgi gerekir.
Küçük bir örnekle anlatmak istediğim şey şu A, B, C, D elemanlı 3 'lü tekrarlı permütasyon
(‘A’, ‘A’, ‘A’) …
(‘D’, ‘B’, ‘B’), (‘D’, ‘B’, ‘C’), (‘D’, ‘B’, ‘D’), (‘D’, ‘C’, ‘A’) … bir çıktıda
diğer kümeyide 2 'lü yaptık (‘A’, ‘B’) , (‘A’, ‘C’), (‘A’, ‘D’) … (‘D’, ‘B’) …
(‘D’, ‘B’) şimdi (‘D’, ‘B’, ‘B’), (‘D’, ‘B’, ‘C’), (‘D’, ‘B’, ‘D’) bunların kesişim kümesidir bunu bulmaya çalışıyoruz diye algılıyor.
Doğrumu yoldayız 
bence yeni öğreniyorum problem çözerek öğrenmek daha pekiştiriyor.
Buradan bir sey alacaksan python’daki assert statement’inin kullanim kurallarini degil, kodla beraber (tercihen oncesinde) test yazmanin faydalarini al. Kodun istedigimiz sekilde calistigina olan inancimizi arttirmanin yaninda hata eklemeden degisiklik yapmamizi, hatta anlamamizi bile kolaylastiriyor.
satisfy_all yukarida uretilen queries’i kullanacakti, test yazabileyim diye parametre yaptim. Burada test edilebilen kodun baskasinin tarafindan alip kullanilabilmesinin, yani modullerliginin de arttigini goruyoruz.
Cevabın için öncelikle teşekkürler. Öncelikle küme kavramında 8 elemanlı bir küme ile 8 farklı küme ayrımı olabileceği teyit etmek namına düşündüğümden bu şekilde belirttim. Birde şöyle bi durum var bir kümenin içinde aynı eleman alt küme olarak olabilir ve gene istenen şartları sağlayabilir. Bu şekilde yorumladığımdan ötürü C(48,8).C(8,5)/5! diye düşündüm. Ama soru sorulurken bu kadar komplike düşünüp düşünmeyeceğini konusunda bir fikrim yok. Bu konu üzerinde düşünerek daha bir düzgün cevap bulabiliriz tabii. Tekrardan teşekkürler.