Kelebek algoritması için fikir istiyorum

Python PyQt
1

Öğrenci sınav oturma düzeni oluşturuyorum. 4 gruba öğrencileri atıyorum. Aynı gruptaki öğrenciler yan yana oturmayacak. Fakat şöyle bir durum var. Gruptaki öğrenci sayıları yakın olmayınca artan grup öğrencileri yan yana gelmek zorunda kalıyor. Bu problemi çözebilmek için nasıl bir algoritma yapabiliriz.

Öğrenci sayıları şu şekilde diyelim:
1.grup : 180 öğrenci
2.grup : 150 öğrenci
3.grup : 140 öğrenci
4.grup : 90 öğrenci

Öğrencileri random gruplardan seçiyorum. Burada 1.grup fazla olduğu için o gruptan daha fazla random çekmem lazım ki sayıyı azaltabileyim.

Gruplardaki öğrenci sayılarına göre algoritma yapay zeka gibi karar almalı.

2

Graph coloring - Wikipedia problemi.

Ogrenciler ipte dizili gibi yanyana oturuyorlarsa basit bir varyanti.

Soyle bir sey olur gibi geldi:
ABABABABABABABA (A’lar bitti) BCBCBCBCBCB (B’ler bitti) CDCDCDCDCDC (D’ler bitti)
Kalan C’leri AB arasina yerlestir.

Sona kalanlari yerlestirmek kolay olsun diye gruplar buyukten kucuge dizilebilir (ama gerek yok sanki)

Baska bir yontem de sayilar esitlenene kadar en buyuk ikisini XYXYXYXY seklinde dizmek. (y ile z ikinci sira icin yarisiyorsa XyXzXyXzXyXz olacak…) Esitlendikten sonra ABCD.ABCD.ABCD…

3 Beğeni
3

Teşekkür ederim bi deneyim Python’da.

4

random.sample() konusuna bakmanı öneririm ben de.

Edit: Olmuyormuş, yan yana koyuyor şimdi farkettim.

5

Şöyle bi kod yazdım bi bakar mısınız? Adım 4’te artan gruptaki öğrencileri araya yerleştiriyorum.

6

Hımm, maalesef olmamış sanki;

Yazdığınız kod d = {"a": 431, "b": 175, "c": 150, "d": 106} için sonsuz döngüye giriyor. Halbuki bu sözlükteki değerlere göre de aynı gruptaki elemanlar yan yana gelmeyecek şekilde dağıtım yapılabilir.

Algoritmanızda biraz değişiklikler yapmanız gerekiyor.

@aib’in bahsettiği yöntemi uygulamayı da deneyebilirsiniz.

Yöntemi Gör 
def distribute_members(d: dict, x: str = "", order: list = None, d_copy: dict = None):
    if not order:
        order = []
    if not d_copy:
        d_copy = d.copy()
    if not x:
        x = max(d_copy, key=d_copy.get)
        if d_copy[x] > sum({k: d_copy[k] for k in d_copy if k != x}.values()):
            raise ValueError("The desired distribution cannot be made according to the given values.")
    if without_x := {k: d_copy[k] for k in d_copy if k != x}:
        y = max(without_x, key=without_x.get)
        x, y = (x, y) if d_copy[x] > d_copy[y] else (y, x)
        order += [x, y] * d_copy[y]
        d_copy[x] -= d_copy[y]
        d_copy.pop(y)
        return distribute_members(d_copy, x, order)
    else:
        for i in range(d_copy[x]):
            order = order[:i * 2] + [x] + order[i * 2:]
        return order

Fonksiyonu çağıralım:

d = {"a": 431, "b": 175, "c": 150, "d": 106}

distributed = distribute_members(d)

# Ardışık iki elemanın aynı olup olmadığını kontrol edelim.
if any(distributed[i] == distributed[i + 1] for i in range(len(distributed) - 1)):
    raise ValueError("Two consecutive items are same!")

# Eksik eleman olup olmadığını kontrol edelim.
if any(distributed.count(k) != v for k, v in d.items()):
    raise ValueError("There's a missing item.")

print(distributed)

a’ya özellikle 431 yazdım. Çünkü 431, b + c + d’nin değeri.

Yani, maksimum eleman sayısına sahip grubun eleman sayısı, diğer grupların eleman sayılarının toplamından daha fazla olursa, yapacağımız dağıtımda ister istemez aynı gruptaki elemanlar yan yana gelecektir. Bunu önlemek için, verili değerlerin dağıtımı esnasında sorun çıkıp çıkmayacağını dağıtıma geçmeden önce kontrol etmek gerekiyor. Aşağıdaki sorguyla da bu kontrolü sağladık.

        x = max(d_copy, key=d_copy.get)
        if d_copy[x] > sum({k: d_copy[k] for k in d_copy if k != x}.values()):
            raise ValueError("The desired distribution cannot be made according to the given values.")
1 Beğeni
7

Dediğiniz gibi sonsuz döngüye girdi. Bahsettiğiniz yönteme göre yaptım zaten.

8

Testi baskasi yazdiktan sonra cozum uretmesi zevkli:

def check(original, distributed):
	print("".join(distributed))

	# Ardışık iki elemanın aynı olup olmadığını kontrol edelim.
	if any(distributed[i] == distributed[i + 1] for i in range(len(distributed) - 1)):
		raise ValueError("Two consecutive items are same!")

	# Eksik eleman olup olmadığını kontrol edelim.
	if any(distributed.count(k) != v for k, v in original.items()):
		raise ValueError("There's a missing item.")

	print("OK")

d1 = {"a": 431, "b": 175, "c": 150, "d": 106}
#check(d1, distribute_members(d1))
d2 = {"a": 3, "b": 5, "c": 1, "d": 4}
#check(d2, distribute_members(d2))

# Soyle bir sey olur gibi geldi:
# ABABABABABABABA (A’lar bitti) BCBCBCBCBCB (B’ler bitti) CDCDCDCDCDC (D’ler bitti)
# Kalan C’leri AB arasina yerlestir.
def dist1(d):
	d = d.copy()
	ans = []

	while True:
		d = { k: v for k, v in d.items() if v > 0 }
		groups = list(d.keys())

		if len(groups) == 0:
			break

		if len(groups) >= 2:
			x, y = groups[0], groups[1]
			if len(ans) > 0 and ans[-1] == x:
				x, y = y, x

			ans.append(x)
			ans.append(y)
			d[x] -= 1
			d[y] -= 1
		else:
			x = groups[0]
			def ins():
				for i in range(len(ans)):
					if (True if i == 0 else ans[i - 1] != x) and (True if i == len(ans) - 1 else ans[i] != x):
						ans.insert(i, x)
						d[x] -= 1
						return
				raise ValueError("Impossible")
			ins()

	return ans

check(d1, dist1(d1))
check(d2, dist1(d2))

# Baska bir yontem de sayilar esitlenene kadar en buyuk ikisini XYXYXYXY seklinde dizmek.
# (y ile z ikinci sira icin yarisiyorsa XyXzXyXzXyXz olacak…)
# Esitlendikten sonra ABCD.ABCD.ABCD…
def dist2(d):
	d = d.copy()
	ans = []

	while True:
		ds = sorted(d.items(), key=lambda kv: -kv[1])
		if all(map(lambda kv: kv[1] == ds[0][1], ds)):
			break

		ans.append(ds[0][0])
		d[ds[0][0]] -= 1

		if ds[1][1] > 0: # Toplamin tek sayi oldugundaki problemi on gorememisim
			ans.append(ds[1][0])
			d[ds[1][0]] -= 1

	return ans

check(d1, dist2(d1))
check(d2, dist2(d2))

Edit: dist2 abcd.abcd fazina girmiyor. Iste bu yuzden test case onemli.

1 Beğeni
9

Üretilen çıktılar farklı ama her 3 yöntemle üretilen çıktılar da mevcut testi geçtiler. dist2’nin çıktısına bakarsak, önce ab.ab.ab fazında ilerliyor sonra da abcd.abcd fazına geçiyor. Hangi test durumunda dist2 abcd.abcd fazına geçmiyor?

# distribute members
cdcacdcacdcacdcacdcacdcacdcacdcacdcacdcacdcacdcacdadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadadabdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcbcb
OK
# dist1
dadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdabababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababacacacacacacacacacacacacacacacacacacacacacacacacacdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdc
OK
# dist2
dadadadadadadadadadadadadadadadadadadadadadadadadadadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdadbdcdadbdcdadbdcdadbdcdadbdcdadbdcdadbdcdadbdcdadbdcdadbdcdadbdcdadbdcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcd
OK
10

Deneyelim teşekkür ederim.

11

Hmm, evet. a=b=c=d olunca once a+b, sonra esitlik bozuldugu icin c+d yapiyor, ve tekrar ediyor. Bahsettigim (abcd)xn kismini yazmayi unutmusum ama gerek kalmamis; optimizasyonmus.

Bunu goz ardi edebiliriz sanirim, gece gec saatte gormemisim gectigini :slight_smile:

Ama daha fazla test case yazmak her zaman lazim. Ozellikle edge case’leri.

12

Aklıma şu geldi yazılanları okuyunca. Önce ilk iki grubu eşleyerek başlasak.
abab…
2. grup 3 grup sayısına eriştiğinde abc lere başlarız, 4. gruba düşene kadar devam eder. Problem şu hale gelir.

  1. grup 120
  2. grup 90
  3. grup 90
  4. grup 90
    Sonrasına bakmak lazım tabi ne yapılabilir.
13

Test değerlerini üretmek için şöyle bir fonksiyon yazdım:

def test_cases(n: int, r: int, stop: int = 0):
    if not r:
        yield []
        return
    for v in test_cases(n, r - 1, stop + 1):
        for i in range(n + 1):
            if (k := [i, *v]) and len(k) != r + stop or max(k) <= sum(sorted(k)[:-1]) and all(k):
                yield k

Bu fonksiyon ile test durumlarını oluşturuyoruz.
Bir örnek yapalım:

for test_case in test_cases(n=10, r=3):
    print(test_case)

[1, 1, 1]
[2, 1, 1]
[1, 2, 1]
[2, 2, 1]
[3, 2, 1]
[2, 3, 1]
[3, 3, 1]
[4, 3, 1]
[3, 4, 1]
[4, 4, 1]
[5, 4, 1]
[4, 5, 1]
[5, 5, 1]
[6, 5, 1]
[5, 6, 1]
[6, 6, 1]
[7, 6, 1]
[6, 7, 1]
[7, 7, 1]
[8, 7, 1]
[7, 8, 1]
[8, 8, 1]
[9, 8, 1]
[8, 9, 1]
[9, 9, 1]
[10, 9, 1]
[9, 10, 1]
[10, 10, 1]
[1, 1, 2]
[2, 1, 2]
[3, 1, 2]
[1, 2, 2]
[2, 2, 2]
[3, 2, 2]
[4, 2, 2]
[1, 3, 2]
[2, 3, 2]
[3, 3, 2]
[4, 3, 2]
[5, 3, 2]
[2, 4, 2]
[3, 4, 2]
[4, 4, 2]
[5, 4, 2]
[6, 4, 2]
[3, 5, 2]
[4, 5, 2]
[5, 5, 2]
[6, 5, 2]
[7, 5, 2]
[4, 6, 2]
[5, 6, 2]
[6, 6, 2]
[7, 6, 2]
[8, 6, 2]
[5, 7, 2]
[6, 7, 2]
[7, 7, 2]
[8, 7, 2]
[9, 7, 2]
[6, 8, 2]
[7, 8, 2]
[8, 8, 2]
[9, 8, 2]
[10, 8, 2]
[7, 9, 2]
[8, 9, 2]
[9, 9, 2]
[10, 9, 2]
[8, 10, 2]
[9, 10, 2]
[10, 10, 2]
[2, 1, 3]
[3, 1, 3]
[4, 1, 3]
[1, 2, 3]
[2, 2, 3]
[3, 2, 3]
[4, 2, 3]
[5, 2, 3]
[1, 3, 3]
[2, 3, 3]
[3, 3, 3]
[4, 3, 3]
[5, 3, 3]
[6, 3, 3]
[1, 4, 3]
[2, 4, 3]
[3, 4, 3]
[4, 4, 3]
[5, 4, 3]
[6, 4, 3]
[7, 4, 3]
[2, 5, 3]
[3, 5, 3]
[4, 5, 3]
[5, 5, 3]
[6, 5, 3]
[7, 5, 3]
[8, 5, 3]
[3, 6, 3]
[4, 6, 3]
[5, 6, 3]
[6, 6, 3]
[7, 6, 3]
[8, 6, 3]
[9, 6, 3]
[4, 7, 3]
[5, 7, 3]
[6, 7, 3]
[7, 7, 3]
[8, 7, 3]
[9, 7, 3]
[10, 7, 3]
[5, 8, 3]
[6, 8, 3]
[7, 8, 3]
[8, 8, 3]
[9, 8, 3]
[10, 8, 3]
[6, 9, 3]
[7, 9, 3]
[8, 9, 3]
[9, 9, 3]
[10, 9, 3]
[7, 10, 3]
[8, 10, 3]
[9, 10, 3]
[10, 10, 3]
[3, 1, 4]
[4, 1, 4]
[5, 1, 4]
[2, 2, 4]
[3, 2, 4]
[4, 2, 4]
[5, 2, 4]
[6, 2, 4]
[1, 3, 4]
[2, 3, 4]
[3, 3, 4]
[4, 3, 4]
[5, 3, 4]
[6, 3, 4]
[7, 3, 4]
[1, 4, 4]
[2, 4, 4]
[3, 4, 4]
[4, 4, 4]
[5, 4, 4]
[6, 4, 4]
[7, 4, 4]
[8, 4, 4]
[1, 5, 4]
[2, 5, 4]
[3, 5, 4]
[4, 5, 4]
[5, 5, 4]
[6, 5, 4]
[7, 5, 4]
[8, 5, 4]
[9, 5, 4]
[2, 6, 4]
[3, 6, 4]
[4, 6, 4]
[5, 6, 4]
[6, 6, 4]
[7, 6, 4]
[8, 6, 4]
[9, 6, 4]
[10, 6, 4]
[3, 7, 4]
[4, 7, 4]
[5, 7, 4]
[6, 7, 4]
[7, 7, 4]
[8, 7, 4]
[9, 7, 4]
[10, 7, 4]
[4, 8, 4]
[5, 8, 4]
[6, 8, 4]
[7, 8, 4]
[8, 8, 4]
[9, 8, 4]
[10, 8, 4]
[5, 9, 4]
[6, 9, 4]
[7, 9, 4]
[8, 9, 4]
[9, 9, 4]
[10, 9, 4]
[6, 10, 4]
[7, 10, 4]
[8, 10, 4]
[9, 10, 4]
[10, 10, 4]
[4, 1, 5]
[5, 1, 5]
[6, 1, 5]
[3, 2, 5]
[4, 2, 5]
[5, 2, 5]
[6, 2, 5]
[7, 2, 5]
[2, 3, 5]
[3, 3, 5]
[4, 3, 5]
[5, 3, 5]
[6, 3, 5]
[7, 3, 5]
[8, 3, 5]
[1, 4, 5]
[2, 4, 5]
[3, 4, 5]
[4, 4, 5]
[5, 4, 5]
[6, 4, 5]
[7, 4, 5]
[8, 4, 5]
[9, 4, 5]
[1, 5, 5]
[2, 5, 5]
[3, 5, 5]
[4, 5, 5]
[5, 5, 5]
[6, 5, 5]
[7, 5, 5]
[8, 5, 5]
[9, 5, 5]
[10, 5, 5]
[1, 6, 5]
[2, 6, 5]
[3, 6, 5]
[4, 6, 5]
[5, 6, 5]
[6, 6, 5]
[7, 6, 5]
[8, 6, 5]
[9, 6, 5]
[10, 6, 5]
[2, 7, 5]
[3, 7, 5]
[4, 7, 5]
[5, 7, 5]
[6, 7, 5]
[7, 7, 5]
[8, 7, 5]
[9, 7, 5]
[10, 7, 5]
[3, 8, 5]
[4, 8, 5]
[5, 8, 5]
[6, 8, 5]
[7, 8, 5]
[8, 8, 5]
[9, 8, 5]
[10, 8, 5]
[4, 9, 5]
[5, 9, 5]
[6, 9, 5]
[7, 9, 5]
[8, 9, 5]
[9, 9, 5]
[10, 9, 5]
[5, 10, 5]
[6, 10, 5]
[7, 10, 5]
[8, 10, 5]
[9, 10, 5]
[10, 10, 5]
[5, 1, 6]
[6, 1, 6]
[7, 1, 6]
[4, 2, 6]
[5, 2, 6]
[6, 2, 6]
[7, 2, 6]
[8, 2, 6]
[3, 3, 6]
[4, 3, 6]
[5, 3, 6]
[6, 3, 6]
[7, 3, 6]
[8, 3, 6]
[9, 3, 6]
[2, 4, 6]
[3, 4, 6]
[4, 4, 6]
[5, 4, 6]
[6, 4, 6]
[7, 4, 6]
[8, 4, 6]
[9, 4, 6]
[10, 4, 6]
[1, 5, 6]
[2, 5, 6]
[3, 5, 6]
[4, 5, 6]
[5, 5, 6]
[6, 5, 6]
[7, 5, 6]
[8, 5, 6]
[9, 5, 6]
[10, 5, 6]
[1, 6, 6]
[2, 6, 6]
[3, 6, 6]
[4, 6, 6]
[5, 6, 6]
[6, 6, 6]
[7, 6, 6]
[8, 6, 6]
[9, 6, 6]
[10, 6, 6]
[1, 7, 6]
[2, 7, 6]
[3, 7, 6]
[4, 7, 6]
[5, 7, 6]
[6, 7, 6]
[7, 7, 6]
[8, 7, 6]
[9, 7, 6]
[10, 7, 6]
[2, 8, 6]
[3, 8, 6]
[4, 8, 6]
[5, 8, 6]
[6, 8, 6]
[7, 8, 6]
[8, 8, 6]
[9, 8, 6]
[10, 8, 6]
[3, 9, 6]
[4, 9, 6]
[5, 9, 6]
[6, 9, 6]
[7, 9, 6]
[8, 9, 6]
[9, 9, 6]
[10, 9, 6]
[4, 10, 6]
[5, 10, 6]
[6, 10, 6]
[7, 10, 6]
[8, 10, 6]
[9, 10, 6]
[10, 10, 6]
[6, 1, 7]
[7, 1, 7]
[8, 1, 7]
[5, 2, 7]
[6, 2, 7]
[7, 2, 7]
[8, 2, 7]
[9, 2, 7]
[4, 3, 7]
[5, 3, 7]
[6, 3, 7]
[7, 3, 7]
[8, 3, 7]
[9, 3, 7]
[10, 3, 7]
[3, 4, 7]
[4, 4, 7]
[5, 4, 7]
[6, 4, 7]
[7, 4, 7]
[8, 4, 7]
[9, 4, 7]
[10, 4, 7]
[2, 5, 7]
[3, 5, 7]
[4, 5, 7]
[5, 5, 7]
[6, 5, 7]
[7, 5, 7]
[8, 5, 7]
[9, 5, 7]
[10, 5, 7]
[1, 6, 7]
[2, 6, 7]
[3, 6, 7]
[4, 6, 7]
[5, 6, 7]
[6, 6, 7]
[7, 6, 7]
[8, 6, 7]
[9, 6, 7]
[10, 6, 7]
[1, 7, 7]
[2, 7, 7]
[3, 7, 7]
[4, 7, 7]
[5, 7, 7]
[6, 7, 7]
[7, 7, 7]
[8, 7, 7]
[9, 7, 7]
[10, 7, 7]
[1, 8, 7]
[2, 8, 7]
[3, 8, 7]
[4, 8, 7]
[5, 8, 7]
[6, 8, 7]
[7, 8, 7]
[8, 8, 7]
[9, 8, 7]
[10, 8, 7]
[2, 9, 7]
[3, 9, 7]
[4, 9, 7]
[5, 9, 7]
[6, 9, 7]
[7, 9, 7]
[8, 9, 7]
[9, 9, 7]
[10, 9, 7]
[3, 10, 7]
[4, 10, 7]
[5, 10, 7]
[6, 10, 7]
[7, 10, 7]
[8, 10, 7]
[9, 10, 7]
[10, 10, 7]
[7, 1, 8]
[8, 1, 8]
[9, 1, 8]
[6, 2, 8]
[7, 2, 8]
[8, 2, 8]
[9, 2, 8]
[10, 2, 8]
[5, 3, 8]
[6, 3, 8]
[7, 3, 8]
[8, 3, 8]
[9, 3, 8]
[10, 3, 8]
[4, 4, 8]
[5, 4, 8]
[6, 4, 8]
[7, 4, 8]
[8, 4, 8]
[9, 4, 8]
[10, 4, 8]
[3, 5, 8]
[4, 5, 8]
[5, 5, 8]
[6, 5, 8]
[7, 5, 8]
[8, 5, 8]
[9, 5, 8]
[10, 5, 8]
[2, 6, 8]
[3, 6, 8]
[4, 6, 8]
[5, 6, 8]
[6, 6, 8]
[7, 6, 8]
[8, 6, 8]
[9, 6, 8]
[10, 6, 8]
[1, 7, 8]
[2, 7, 8]
[3, 7, 8]
[4, 7, 8]
[5, 7, 8]
[6, 7, 8]
[7, 7, 8]
[8, 7, 8]
[9, 7, 8]
[10, 7, 8]
[1, 8, 8]
[2, 8, 8]
[3, 8, 8]
[4, 8, 8]
[5, 8, 8]
[6, 8, 8]
[7, 8, 8]
[8, 8, 8]
[9, 8, 8]
[10, 8, 8]
[1, 9, 8]
[2, 9, 8]
[3, 9, 8]
[4, 9, 8]
[5, 9, 8]
[6, 9, 8]
[7, 9, 8]
[8, 9, 8]
[9, 9, 8]
[10, 9, 8]
[2, 10, 8]
[3, 10, 8]
[4, 10, 8]
[5, 10, 8]
[6, 10, 8]
[7, 10, 8]
[8, 10, 8]
[9, 10, 8]
[10, 10, 8]
[8, 1, 9]
[9, 1, 9]
[10, 1, 9]
[7, 2, 9]
[8, 2, 9]
[9, 2, 9]
[10, 2, 9]
[6, 3, 9]
[7, 3, 9]
[8, 3, 9]
[9, 3, 9]
[10, 3, 9]
[5, 4, 9]
[6, 4, 9]
[7, 4, 9]
[8, 4, 9]
[9, 4, 9]
[10, 4, 9]
[4, 5, 9]
[5, 5, 9]
[6, 5, 9]
[7, 5, 9]
[8, 5, 9]
[9, 5, 9]
[10, 5, 9]
[3, 6, 9]
[4, 6, 9]
[5, 6, 9]
[6, 6, 9]
[7, 6, 9]
[8, 6, 9]
[9, 6, 9]
[10, 6, 9]
[2, 7, 9]
[3, 7, 9]
[4, 7, 9]
[5, 7, 9]
[6, 7, 9]
[7, 7, 9]
[8, 7, 9]
[9, 7, 9]
[10, 7, 9]
[1, 8, 9]
[2, 8, 9]
[3, 8, 9]
[4, 8, 9]
[5, 8, 9]
[6, 8, 9]
[7, 8, 9]
[8, 8, 9]
[9, 8, 9]
[10, 8, 9]
[1, 9, 9]
[2, 9, 9]
[3, 9, 9]
[4, 9, 9]
[5, 9, 9]
[6, 9, 9]
[7, 9, 9]
[8, 9, 9]
[9, 9, 9]
[10, 9, 9]
[1, 10, 9]
[2, 10, 9]
[3, 10, 9]
[4, 10, 9]
[5, 10, 9]
[6, 10, 9]
[7, 10, 9]
[8, 10, 9]
[9, 10, 9]
[10, 10, 9]
[9, 1, 10]
[10, 1, 10]
[8, 2, 10]
[9, 2, 10]
[10, 2, 10]
[7, 3, 10]
[8, 3, 10]
[9, 3, 10]
[10, 3, 10]
[6, 4, 10]
[7, 4, 10]
[8, 4, 10]
[9, 4, 10]
[10, 4, 10]
[5, 5, 10]
[6, 5, 10]
[7, 5, 10]
[8, 5, 10]
[9, 5, 10]
[10, 5, 10]
[4, 6, 10]
[5, 6, 10]
[6, 6, 10]
[7, 6, 10]
[8, 6, 10]
[9, 6, 10]
[10, 6, 10]
[3, 7, 10]
[4, 7, 10]
[5, 7, 10]
[6, 7, 10]
[7, 7, 10]
[8, 7, 10]
[9, 7, 10]
[10, 7, 10]
[2, 8, 10]
[3, 8, 10]
[4, 8, 10]
[5, 8, 10]
[6, 8, 10]
[7, 8, 10]
[8, 8, 10]
[9, 8, 10]
[10, 8, 10]
[1, 9, 10]
[2, 9, 10]
[3, 9, 10]
[4, 9, 10]
[5, 9, 10]
[6, 9, 10]
[7, 9, 10]
[8, 9, 10]
[9, 9, 10]
[10, 9, 10]
[1, 10, 10]
[2, 10, 10]
[3, 10, 10]
[4, 10, 10]
[5, 10, 10]
[6, 10, 10]
[7, 10, 10]
[8, 10, 10]
[9, 10, 10]
[10, 10, 10]

Test durumları şu mantığa göre oluşturuluyor: Maksimum değeri, diğer elemanların toplamından büyük olmayan her türlü durum bizim test durumumuzdur.

Kontrol mekanizmasını da uygulayalım:

def check(original, distributed, n, r, test_case, func):
    info = f"Func: {func}, n = {n}, r = {r}, test_case = {test_case}"
    if any(distributed[i] == distributed[i + 1] for i in range(len(distributed) - 1)):
        raise ValueError(f"{info} - Two consecutive items are same!")
    if any(distributed.count(k) != v for k, v in original.items()):
        raise ValueError(f"{info} - There's a missing item.")
    print(f"{info} - OK")

distribute_members fonksiyonunun ismini dist1, senin yazdığın fonksiyonların isimlerini de sırasıyla dist2 ve dist3 olarak değiştiriyorum:

def dist1(d: dict, x: str = "", order: list = None, d_copy: dict = None):
    if not order:
        order = []
    if not d_copy:
        d_copy = d.copy()
    if not x:
        x = max(d_copy, key=d_copy.get)
        if d_copy[x] > sum({k: d_copy[k] for k in d_copy if k != x}.values()):
            raise ValueError("The desired distributing cannot be made according to the given values.")
    if without_x := {k: d_copy[k] for k in d_copy if k != x}:
        y = max(without_x, key=without_x.get)
        x, y = (x, y) if d_copy[x] > d_copy[y] else(y, x)
        order += [x, y] * d_copy[y]
        d_copy[x] -= d_copy[y]
        d_copy.pop(y)
        return dist1(d_copy, x, order)
    else:
        for i in range(d_copy[x]):
            order = order[:i * 2] + [x] + order[i * 2:]
        return order


def dist2(d):
    d = d.copy()
    ans = []
    while True:
        d = {k: v for k, v in d.items() if v > 0}
        groups = list(d.keys())
        if len(groups) == 0:
            break
        if len(groups) >= 2:
            x, y = groups[0], groups[1]
            if len(ans) > 0 and ans[-1] == x:
                x, y = y, x
            ans.append(x)
            ans.append(y)
            d[x] -= 1
            d[y] -= 1
        else:
            x = groups[0]

            def ins():
                for i in range(len(ans)):
                    if (True if i == 0 else ans[i - 1] != x) and (True if i == len(ans) - 1 else ans[i] != x):
                        ans.insert(i, x)
                        d[x] -= 1
                        return
                raise ValueError("Impossible")
            ins()
    return ans


def dist3(d):
    d = d.copy()
    ans = []
    while True:
        ds = sorted(d.items(), key=lambda kv: -kv[1])
        if all(map(lambda kv: kv[1] == ds[0][1], ds)):
            break
        ans.append(ds[0][0])
        d[ds[0][0]] -= 1
        if ds[1][1] > 0:
            ans.append(ds[1][0])
            d[ds[1][0]] -= 1
    return ans

Şimdi test fonksiyonunu oluşturuyorum:

from string import ascii_lowercase


def test():
    # Test, 3 elemanlı bir sözlük ile başlayacak...
    for r in range(3, 11):
        # Sözlükteki r sayıdaki elemanların sayısal değerinin toplamını 10 ile başlatalım.
        for n in range(10, 100):
            # Yukardaki duruma göre kaç tane test durumumuz varsa hepsini deneyelim:
            for test_case in test_cases(n=n, r=r):
                d = {ascii_lowercase[index]: k for index, k in enumerate(test_case)}
                check(d, dist1(d), n, r, test_case, func="dist1")
                check(d, dist2(d), n, r, test_case, func="dist2")
                check(d, dist3(d), n, r, test_case, func="dist3")

Sonra da test’i çağırıyorum ve şu sonucu aldım:

Func: dist1, n = 10, r = 3, test_case = [1, 1, 1] - OK
Func: dist2, n = 10, r = 3, test_case = [1, 1, 1] - OK
Traceback (most recent call last):
  File "C:\Users\tanberk\Desktop\Python\v1.py", line 103, in <module>
    test()
  File "C:\Users\tanberk\Desktop\Python\v1.py", line 100, in test
    check(d, dist3(d), n, r, test_case, func="dist3")
  File "C:\Users\tanberk\Desktop\Python\v1.py", line 76, in check
    raise ValueError(f"{info} - There's a missing item.")
ValueError: Func: dist3, n = 10, r = 3, test_case = [1, 1, 1] - There's a missing item.

Şöyle yapıyorum şimdi:

from string import ascii_lowercase


def test():
    # Test, 3 elemanlı bir sözlük ile başlayacak...
    c = 0
    for r in range(3, 11):
        # Sözlükteki i sayıdaki elemanların sayısal değerinin toplamı 10 ile başlatalım.
        for n in range(10, 100):
            # Yukardaki duruma göre kaç tane test durumumuz varsa hepsini deneyelim:
            for test_case in test_cases(n=n, r=r):
                d = {ascii_lowercase[index]: k for index, k in enumerate(test_case)}
                check(d, dist1(d), n, r, test_case, func="dist1")
                check(d, dist2(d), n, r, test_case, func="dist2")
                try:
                    check(d, dist3(d), n, r, test_case, func="dist3")
                except ValueError:
                    c += 1
                    print(f"dist3 hata sayısı: {c}")

Şöyle göstereyim:

[...]
dist3 hata sayısı: 101278
Func: dist1, n = 30, r = 3, test_case = [21, 9, 20] - OK
Func: dist2, n = 30, r = 3, test_case = [21, 9, 20] - OK
dist3 hata sayısı: 101279
Func: dist1, n = 30, r = 3, test_case = [22, 9, 20] - OK
Func: dist2, n = 30, r = 3, test_case = [22, 9, 20] - OK
dist3 hata sayısı: 101280
Func: dist1, n = 30, r = 3, test_case = [23, 9, 20] - OK
Func: dist2, n = 30, r = 3, test_case = [23, 9, 20] - OK
[...]

Gözlemlediğim kadarıyla, dist1 ve dist2 fonksiyonları, n=50 ve r=3 test koşulundaki bütün durumlara kadar hatasız gittiler.

14

Hmm, ilginc bir yaklasim: There are Only Four Billion Floats–So Test Them All! | Random ASCII – tech blog of Bruce Dawson

dist0 yapaydin :smiley:

“abcd” kismi iste:

		if all(map(lambda kv: kv[1] == ds[0][1], ds)):
			ans += [kv[0] for kv in ds] * ds[0][1]
			break

veya

        if all(map(lambda kv: kv[1] == 0, ds)):
            break
15

Çok yorucu bir test olmuş evet. :face_with_hand_over_mouth:

Exhaustive testing works brilliantly for functions that take a single float as input. I used this to great effect when rewriting all of the CRT math functions for a game console some years ago. On the other hand, if you have a function that takes multiple floats or a double as input then the search space is too big. In that case a mixture of test cases for suspected problem areas and random testing should work. A trillion tests can complete in a reasonable amount of time, and it should catch most problems.

16

Test durumlarını üreten fonksiyonu, [1, 2, 1] ve [2, 1, 1] gibi benzer durumları üretmesin diye şöyle değiştiriyorum:

def test_cases(n: int, r: int, stop: int = 0, array: list = None):
    if not array:
        array = []
    if not r:
        yield []
        return
    for v in test_cases(n, r - 1, stop + 1):
        for i in range(n + 1):
            if (
                (k := [i, *v])
                and
                len(k) != r + stop
                or
                max(k) <= sum((sorted_k := sorted(k))[:-1])
                and
                all(k)
                and
                sorted_k not in [sorted(j) for j in array]
            ):
                array += [k]
                yield k

for test_case in test_cases(n=10, r=3):
    print(test_case)

[1, 1, 1]
[2, 1, 1]
[2, 2, 1]
[3, 2, 1]
[3, 3, 1]
[4, 3, 1]
[4, 4, 1]
[5, 4, 1]
[5, 5, 1]
[6, 5, 1]
[6, 6, 1]
[7, 6, 1]
[7, 7, 1]
[8, 7, 1]
[8, 8, 1]
[9, 8, 1]
[9, 9, 1]
[10, 9, 1]
[10, 10, 1]
[2, 2, 2]
[3, 2, 2]
[4, 2, 2]
[3, 3, 2]
[4, 3, 2]
[5, 3, 2]
[4, 4, 2]
[5, 4, 2]
[6, 4, 2]
[5, 5, 2]
[6, 5, 2]
[7, 5, 2]
[6, 6, 2]
[7, 6, 2]
[8, 6, 2]
[7, 7, 2]
[8, 7, 2]
[9, 7, 2]
[8, 8, 2]
[9, 8, 2]
[10, 8, 2]
[9, 9, 2]
[10, 9, 2]
[10, 10, 2]
[3, 3, 3]
[4, 3, 3]
[5, 3, 3]
[6, 3, 3]
[4, 4, 3]
[5, 4, 3]
[6, 4, 3]
[7, 4, 3]
[5, 5, 3]
[6, 5, 3]
[7, 5, 3]
[8, 5, 3]
[6, 6, 3]
[7, 6, 3]
[8, 6, 3]
[9, 6, 3]
[7, 7, 3]
[8, 7, 3]
[9, 7, 3]
[10, 7, 3]
[8, 8, 3]
[9, 8, 3]
[10, 8, 3]
[9, 9, 3]
[10, 9, 3]
[10, 10, 3]
[4, 4, 4]
[5, 4, 4]
[6, 4, 4]
[7, 4, 4]
[8, 4, 4]
[5, 5, 4]
[6, 5, 4]
[7, 5, 4]
[8, 5, 4]
[9, 5, 4]
[6, 6, 4]
[7, 6, 4]
[8, 6, 4]
[9, 6, 4]
[10, 6, 4]
[7, 7, 4]
[8, 7, 4]
[9, 7, 4]
[10, 7, 4]
[8, 8, 4]
[9, 8, 4]
[10, 8, 4]
[9, 9, 4]
[10, 9, 4]
[10, 10, 4]
[5, 5, 5]
[6, 5, 5]
[7, 5, 5]
[8, 5, 5]
[9, 5, 5]
[10, 5, 5]
[6, 6, 5]
[7, 6, 5]
[8, 6, 5]
[9, 6, 5]
[10, 6, 5]
[7, 7, 5]
[8, 7, 5]
[9, 7, 5]
[10, 7, 5]
[8, 8, 5]
[9, 8, 5]
[10, 8, 5]
[9, 9, 5]
[10, 9, 5]
[10, 10, 5]
[6, 6, 6]
[7, 6, 6]
[8, 6, 6]
[9, 6, 6]
[10, 6, 6]
[7, 7, 6]
[8, 7, 6]
[9, 7, 6]
[10, 7, 6]
[8, 8, 6]
[9, 8, 6]
[10, 8, 6]
[9, 9, 6]
[10, 9, 6]
[10, 10, 6]
[7, 7, 7]
[8, 7, 7]
[9, 7, 7]
[10, 7, 7]
[8, 8, 7]
[9, 8, 7]
[10, 8, 7]
[9, 9, 7]
[10, 9, 7]
[10, 10, 7]
[8, 8, 8]
[9, 8, 8]
[10, 8, 8]
[9, 9, 8]
[10, 9, 8]
[10, 10, 8]
[9, 9, 9]
[10, 9, 9]
[10, 10, 9]
[10, 10, 10]
17

Evet. Şimdi üçü de hata vermeden çalışıyor. :+1:

[...]
Func: dist1, n = 25, r = 3, test_case = [17, 14, 14] - OK
Func: dist2, n = 25, r = 3, test_case = [17, 14, 14] - OK
Func: dist3, n = 25, r = 3, test_case = [17, 14, 14] - OK
Func: dist1, n = 25, r = 3, test_case = [18, 14, 14] - OK
Func: dist2, n = 25, r = 3, test_case = [18, 14, 14] - OK
Func: dist3, n = 25, r = 3, test_case = [18, 14, 14] - OK
Func: dist1, n = 25, r = 3, test_case = [19, 14, 14] - OK
Func: dist2, n = 25, r = 3, test_case = [19, 14, 14] - OK
Func: dist3, n = 25, r = 3, test_case = [19, 14, 14] - OK
[...]
18

Bu arada, çok fazla tekrar yapan bir test oluşturmuşum. Şöyle yapsaymışım olurmuş:

def test():
    # Test, 3 elemanlı bir sözlük ile başlayacak...
    for r in range(3, 11):
        for test_case in test_cases(n=100, r=r):
            d = {ascii_lowercase[index]: k for index, k in enumerate(test_case)}
            check(d, dist1(d), test_case, func="dist1")
            check(d, dist2(d), test_case, func="dist2")
            check(d, dist3(d), test_case, func="dist3")

def check(original, distributed, test_case, func):
    info = f"Func: {func}, test_case = {test_case}"
    if any(distributed[i] == distributed[i + 1] for i in range(len(distributed) - 1)):
        raise ValueError(f"{info} - Two consecutive items are same!")
    if any(distributed.count(k) != v for k, v in original.items()):
        raise ValueError(f"{info} - There's a missing item.")
    print(f"{info} - OK")
19

Arkadaşlar teşekkür ederim çalışmışsınız. Şimdi ben databese’den sınıf adlarını çekerek 4 grup halindeki listbox1, listbox2, listbox3 ve listbox4 e atacağım. Daha sonra listboxlarda yer alan sınıf adlarına göre öğrencileri çekip dağıtımı yapacağım.? Sizin paylaştığınız koddaki hangi kısımlarda oynamalıyım? Öğrencileri sözlüğe mi atayım?

20

Bu durum doğal değil mi? Mesela 1. Grupta 200 öğrenci var ve diğer 3 gruptaki öğrenci sayısı ilk grubun toplamı kadar etmiyorsa aralarına yerleştirseniz dahi aynı gruptakilerin yan yana gelmeme şartını sağlamayacaktır değil mi?

Yani bu problem koşullar uygun değilse çözülemez durumdadır.

Çözmek için düşünürken,

Random seçmemelisin, en fazla olan gruptan çekip diğer gruplardan aralara ekleyerek devam eden bir algoritma kullanabilirsin. Bir grup bitince diğerinden çekmeye devam edebilirsin. Ama tüm gruplar bittiği halde ilk grupta kalırsa yan yana gelmeye devam edecektir.

Önce bu yeterlilik koşulunu kontrol ederseniz zaten çözüm olup olmadığını görür ve ona göre devam edebilirsiniz.

Mesela bu soru 1. Grup 100, 2. grup 10, 3. grup 10 ve 4. grup 10 olduğunda çözümsüzdür çünkü diğer üç gruptaki 30 öğrenciyi ancak ilk grubun arasında 31 tanesinin arasına yerleştirebilirsiniz. Geri kalan 69 tane 1ilk grup öğrenci yan yana kalacaktır.

İkinci aşamada yapay zeka gibi bir algoritma demişsiniz bu tür sorular için bir kaç algoritma var, right shift, backtracking gibi iteratif yöntemler ile çözülebileceği gibi genetik algoritma ile de çözülebilir, aslında burada genetik algoritma örneği vermeyi düşünmüştüm ama çözüme yönelik kodlar gördüğümden çok da örnekleme ihtiyacı duymadım.

Yani önce, herhangi bir grubun sayısının, diğer üç grubun toplamından büyük olduğu koşullarda yan yana gelme durumu ile ön kontrolden geçirilmeli. Böyle bir durum varsa uyarı verip çözüm oladuğı bildirimeli, koşullar sağlanıyorsa grubu birleştirme koduna geçilmeli.

Kodu birleştirirken crossover, ve diğer genetik çaprazlama denemeleri ile optimum bir çözüm aranabilir.

Database de kaç sınıf adı var? Dört listbox a koymaktaki amacınız nedir? Dört sınıf çekersem her birinde bir tane sınıf adı olacağından label yada textbox kullanmaktan sizi alıkoyan nedir?

Sınıf adlarına göre öğrencileri çekip dağıtacağım derken? Öğrencilerin isimleri mi var veri tabanında? Yoksa sınıf adları ile öğrenci sayıları temsili varsa sadece sıra sayıları mı dağıtılacak?

Daha da önemlisi, bu listbox ve labellar hangi python gui’sini kullanıyor? Tkinter mi? Qt mi? yada diğerlerinden biri mi?

Eminim siz sorununuzu iyi biliyorsunuz ama cevaplamak isteyen biri olarak anlamamız için çok ucu açık nokta var buralara da değinirseniz daha tutarlı cevaplar verebiliriz.