Algoritma sorusu (permütasyon)

Hayırlı forumlar :slight_smile:

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 :slight_smile:
P(48,5)/P(8/5)

1 Beğeni

Ö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.

  • 8 elemanı da farklıdır. Çünkü kumeden bahsediyoruz.

Ö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.

2 Beğeni

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ı :confused:

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 :smile: 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.

2 Beğeni

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.

1 Beğeni