Sınav Zaman Tablosu

Değerli arkadaşlarım bir konuda yardım istiyorum. Okulumuzda sorumluluk sınavlarına girecek öğrenciler var. Bu öğrenciler 9.sınıftan ve 10 .sınıftan bazı derslerden sorumlular. Ben 1 haftalık bir sürede sınav zaman tablosu oluşturmak istiyorum ama öğrencilerin gireceği sınavlar zaman tablosunda çakışmayacak. Bunun için nasıl bir algoritma yazmam lazım? Yöntem nasıl olmalı. Bu şekilde yaklaşık 50 öğrenci, sorumlu olunan 255 toplam dersleri ve farklı adda 9. ve 10. sınıf 22 ders var. Elimdeki veriler şu şekilde:
Öğrenci Adı, Sorumlu Olduğu Sınıf , Sorumlu Olduğu Ders
A 9 Türk Dili ve Edebiyatı
A 9 Coğrafya
A 9 Fizik
A 9 Matematik
B 9 Türk Dili ve Edebiyatı
B 9 Fizik
C 9 Kimya
C 10 Türk Dili ve Edebiyatı
.
.
.
.

Merhaba, aslında bu durumu klasik öğretmen ders çizelgesi hazırlama durumu olarak görebiliriz ve sonrasında sizin probleminize evirebiliriz.

Ders dağıtım algoritmaları her zaman “sorun” olmuştur :slight_smile: Aşağıya bırakacağım link işinizi görecektir.

Graf renklendirme algoritması da bu problemin çözümü için uygun gibi görünüyor.

http://www.hasanbalik.com/yayinlar/d/19.pdf

Arkadaşlar verim aşağıdaki gibi. Daha somut örnekler olursa sevinirim. Buradaki dersleri zaman tablosuna yerleştireceğim ama öğrencilerin sınavları çakışmayacak. Sıkıntı şurda sınavlar 5 gün sürecek ve bir öğrenci günde 2 sınava girebiliyor. Yani aynı saatte başka bir sınav daha olacak.

exam_days = [‘Monday’, ‘Tuesday’,’Wednesday’,’Thursday’,’Friday’]
exam_hours = [’10.00’, ’11.00’, ‘12.00’]

student_exams = { “Student1”:[ ‘Lesson1’,’Lesson2’,’Lesson3’],
“Student2”:[ ‘Lesson1’,’Lesson2’,’Lesson3’, ‘Lesson4’,’Lesson5’],
“Student3”:[ ‘Lesson1’,’Lesson2’],
“Student4”:[ ‘Lesson1’,’Lesson2’,’Lesson3’, ‘Lesson4’,’Lesson5’,’Lesson6’],
“Student5”:[ ‘Lesson1’,’Lesson2’,’Lesson3’,’Lesson5’],
……
……
………
}

Hocam verilerinizi tam olarak paylaşabilirseniz(veya bir kısmını) belki daha iyi yardımcı olunur. Çünkü konunun ilk gönderisinde bahsettiğiniz veriler ile son gönderinizdeki veriler farklı. Ben sizin için gönderdiğim pdf içerisindeki örneği açıklamaya çalışayım. Siz kendi verilerinize uygularsınız.

5 öğrenci ve 5 ders var. Öğrenci ve aldığı ders ilişkisi aşağıdaki gibi.

Öğrenci No - Aldığı Ders
ö1 - d1
ö1 - d3
ö1 - d5
ö2 - d2
ö2 - d3
ö3 - d2
ö3 - d4
ö4 - d1
ö4 - d3
ö4 - d5
ö5 - d1
ö5 - d4

Burada dersleri grafın bir düğümü olarak kabul edip şöyle bir graf oluşturuyoruz.

subjects = [1, 2, 3, 4, 5]
students = {
	"Student1":[1, 3, 5],
	"Student2":[2, 3],
	"Student3":[2, 4],
	"Student4":[1, 3, 5],
	"Student5":[1, 4],
}


# Komşuluk matrisi çıkarma
matrix = [[0]*5 for i in range(5)]

for student in students:
	for i,j in itertools.combinations(students[student], 2):
		matrix[i-1][j-1] = 1
		matrix[j-1][i-1] = 1

Bu matrisin çıktısı şöyle bir şey

   1 2 3 4 5
  ----------
1| 0 0 1 1 1
2| 0 0 1 1 0
3| 1 1 0 0 1
4| 1 1 0 0 0
5| 1 0 1 0 0

Şimdi düğümlerinin derecesini elde ediyoruz ve büyükten küçüğe sıralıyoruz.

# Düğüm derecelerini tespit etme ve düğüm derecesine göre sıralama
temp = {index+1:i for index, i in enumerate(matrix)}
sorted_temp = sorted(temp, key=lambda i:temp.get(i).count(1), reverse=True)

Son olarak düğümlere renk veriyoruz. Renk dediğimiz şey için ben alfabenin harflerini rastgele elde ettim. İşlem sonunda aynı harf ile işaretlenmiş derslerin aynı gün ve saatte yapılmasında mahsur yok demektir.

# Daha önce boyanmış düğümleri tekrar boyamamak için
colored = {}

while len(sorted_temp):
	current_node = sorted_temp.pop(0)
	
	current_color = get_random_color()

	while True:
		if current_color in used_colors:
			current_color = get_random_color()
		else:
			break

	used_colors.append(current_color)
	# düğüm boyalıysa es geçiyoruz
	if not (current_node in colored):
		colored[current_node] = current_color
	else:
		continue

	# şu andaki düğümü, aşağıdaki for döngüsünde
	# kendisi ile karşılaştırmamak için dersler listesinden kaldırıyoruz
	subjects.remove(current_node)

	# bir düğüm(yani ders) başka bir düğüm ile komşu değilse
	# aynı renk veriliyor
	for i in subjects:
		if not matrix[current_node - 1][i - 1] and not (i in colored):
			colored[i] = current_color

Çıktı için

# Tüm işlemler sonucunda aynı renk verilmiş tüm dersler
# Aynı gün ve saatte yapılabilir

for i in set(colored.values()):
    print(", ".join([str(x) for x in colored if colored[x]==i]), "dersleri aynı zamanda yapılabilir")

Çıktısı

3, 4 dersleri aynı zamanda yapılabilir
1, 2 dersleri aynı zamanda yapılabilir
5 dersleri aynı zamanda yapılabilir

Dediğim gibi, ben bu algoritmayı kullandım. Somut örnek istediğiniz için paylaştım. Belki katkıda bulunmak isteyen olabilir, yorumda bulunmak isteyen olabilir. Kodun tamamını paylaşıyorum. Evet kod kötü yazılmış, çünkü bağımlı değişkenler var, fazlalıklar var, eksiklikler var. Şimdilik sadece amaca yönelik yazıldığı için böyle. Düzeltilebilir.

import itertools
import random
import string

used_colors = []
def get_random_color():
	return string.ascii_lowercase[random.randint(1, len(string.ascii_lowercase)-1)]


subjects = [1, 2, 3, 4, 5]
students = {
	"Student1":[1, 2],
	"Student2":[2, 3],
	"Student3":[3],
	"Student4":[2, 4, 5],
	"Student5":[5],
}


# Komşuluk matrisi çıkarma
matrix = [[0]*5 for i in range(5)]

for student in students:
	for i,j in itertools.combinations(students[student], 2):
		matrix[i-1][j-1] = 1
		matrix[j-1][i-1] = 1

# Düğüm derecelerini tespit etme ve düğüm derecesine göre sıralama
temp = {index+1:i for index, i in enumerate(matrix)}
sorted_temp = sorted(temp, key=lambda i:temp.get(i).count(1), reverse=True)

# Daha önce boyanmış düğümleri tekrar boyamamak için
colored = {}

while len(sorted_temp):
	current_node = sorted_temp.pop(0)
	
	current_color = get_random_color()

	while True:
		if current_color in used_colors:
			current_color = get_random_color()
		else:
			break

	used_colors.append(current_color)
	# düğüm boyalıysa es geçiyoruz
	if not (current_node in colored):
		colored[current_node] = current_color
	else:
		continue

	# şu andaki düğümü, aşağıdaki for döngüsünde
	# kendisi ile karşılaştırmamak için dersler listesinden kaldırıyoruz
	subjects.remove(current_node)

	# bir düğüm(yani ders) başka bir düğüm ile komşu değilse
	# aynı renk veriliyor
	for i in subjects:
		if not matrix[current_node - 1][i - 1] and not (i in colored):
			colored[i] = current_color

# Tüm işlemler sonucunda aynı renk verilmiş tüm dersler
# Aynı gün ve saatte yapılabilir
for i in set(colored.values()):
	print(", ".join([str(x) for x in colored if colored[x]==i]), "dersleri aynı zamanda yapılabilir")
2 Beğeni

Eyvallah kardeşim coderistan şimdi olayı anladım. Teşekkür ederim yarın uğraşacağım. Somut şekilde görmeyince kafamda oturmuyor ingilizce kaynaktan.

1 Beğeni

matrix = [[0]*5 for i in range(5)]

Komşuluk matrisini 5 ders olduğu için mi range(5) olarak ayarladınız. 22 ders için range(22) mi yapmalıyım matrisin boyunu.
Şu şekilde : matrix = [[0]*22 for i in range(22)]

for i,j in itertools.combinations(students[student], 2):

yukarıdaki 2 ne anlama geliyor?

Çakışma oldu maalesef.

8 ve 17 nolu dersleri kontrol etmiş ama 17 ve 21 i kontrol etmemiş. Sadece 1.ve 2.dersleri kontrol etmiş.
17 ve 21 nolu derslerden aynı öğrenci sorumlu.

8 - 17 de sorun yok
17-21 de sorun var.

Aynı şekilde 1-9 da problem yok.
15-16 sorun var.
16-18 sorun var.

Yani 8 ile 17 yi ve 8 ile 21 i karşılaştırmış. Burada 17 ile 21 i dikkate almamış.

Öğrenci ve dersleri
‘İSMET CENGİZ’ : [15, 16, 17, 18, 19, 20, 21]

Merhaba, ben de şöyle bir çözüm yaptım kendimce ama ne kadar verimli, ne kadar okunaklı kod yazdığımdan emin değilim.

OGRENCI_SAYISI = 5
SINAV_SAYISI = 5
OTURUM_SAYISI = 5 * 3

sinavlar = [0] * SINAV_SAYISI
oturumlar = [0] * OTURUM_SAYISI
plan = [[] for i in range(OTURUM_SAYISI)]


ogrenciler = [
        [0, 2, 4],
        [1, 2],
        [1, 3],
        [0, 2, 4],
        [0, 3],
]

for k in range(5):
    for i in ogrenciler[k]:
        # burada her sınav için o sınavına
        # girecek olan öğrencileri ekledik
        sinavlar[i] |= 1<<k;


for sinav in range(SINAV_SAYISI):
    for oturum in range(OTURUM_SAYISI):
        sinav_atandi_mi = True
        for ogrenci in range(OGRENCI_SAYISI):
            # öğrencinin hem ilgili sınavda
            # yer alıp almadığını
            # ve o oturumda daha önce
            # sınavı olup olmadığını
            # kontrol ediyoruz
            if(oturumlar[oturum] & sinavlar[sinav] & (1<<ogrenci)):
                sinav_atandi_mi = False
                break

        if(sinav_atandi_mi):
            # sınav atandıysa, ilgili güne sınavı ekliyoruz
            plan[oturum].append(sinav)
            # ilgili ogrencileri oturuma ekliyoruz
            for ogrenci in range(OGRENCI_SAYISI):
                oturumlar[oturum] |= (sinavlar[sinav] & 1<<ogrenci)
            break


# son olarak
# ilgili_oturum: ilgili sınavlar
# şelinde output bastırılır.
for i in range(15):
    print("oturum: ", i, end=" || ")
    for j in plan[i]:
        print(j, end=" ")

algoritma şu şekilde çalışıyor:

her sınav için 1. oturumdan başlayarak bütün oturumları kontrol ediyoruz
eğer kontrol ettiğimiz oturum, ilgili sınavı eklemek için uygunsa sınavı ve öğrencileri ilgili güne ekliyoruz.

Biliyorum pek anlatamadım meramımı ama bit optimization diye aratırsanız belki bir şeyler anlayabilirsiniz.

Hayırlı akşamlar.

1 Beğeni

Çakışmayan sınavları aynı saate koyuyor mu?

Örnek vereyim:

  1. oturuma bir sınav koyduk diyelim. Elimizde ikinci bir sınav daha var diyelim. Öncelikle 1. oturumu kontrol eder, eğer 1. ve 2. sınavlar çakışmıyorsa 2. sınav da 1. oturuma atanır.

Yani evet

Edit: sonlarda j yerine j+1 bastırmişim, onu j diye düzeltebilir misiniz?

Evet 5 ders olduğu için. 2’nin anlamı, tüm dersleri 2’li kombinasyonlar şeklinde gruplamak. Müsait zamanda örneğe bakayım hocam, diğer algoritmalara da bakabiliriz.

2 li kombinasyon yapınca mesala 8 , 17, 21 de
8-17 ve 8-21 kombinasyonu yapmış. 17-21 de çakışma oldu. Bi arkadaşımız daha uğraşıyor çözdü gibi. Teşekkür ederim yardımların için.

1 Beğeni

Yukarıda @Cihat_Altiparmak tarafından paylaşılan örnek çalışıyor mu?

Çözümü atacağım ama öğrenci listesi var. Kişisel veriler. Kod kısmını atayım tam kontol edince.

Evet düzenleme yaptı @Cihat_Altiparmak ama yukarıdaki gibi değil. Kodu paylaşacağım kontrol edince. Biraz karışık :slight_smile:

1 Beğeni

Kodları gözden geçirdim, yaptığım hatayı farkettim. Zaten ilk seferinde hatasız kod paylaşsaydım şaşardım :sweat_smile:

Aynı anda yapılacak dersleri belirlerken, oturuma eklenecek dersin sadece ilk dersle karşılaştırması yapılmış. Halbuki aynı oturumdaki diğer derslerle komşu olup olmadığı da kontrol edilmeli. Özelden hocamızın paylaştığı verilerle teyit ettim, çalışıyor.

import itertools
import random
import string


def get_color():
	s = string.ascii_lowercase
	for i in itertools.product(s):
		yield "".join(i)


# ders listesi, numaralar şeklinde belirlendi
subjects = list(range(1,23))
students = {
"Student1" : [1],
"Student2" : [1],
"Student3" : [1],
"Student4" : [1],
"Student5" : [2, 3, 4, 1],
"Student6" : [1],
"Student7" : [1],
"Student8" : [1],
"Student9" : [1],
"Student10" : [5, 2, 3, 6, 4, 1],
"Student11" : [1],
"Student12" : [1],
"Student13" : [1],
"Student14" : [1],
"Student15" : [7, 8, 9],
"Student16" : [8],
"Student17" : [1],
"Student18" : [1],
"Student19" : [1],
"Student20" : [10, 5, 2, 3, 6, 11, 8, 1, 12],
"Student21" : [5, 2, 3, 6, 4, 11, 1, 12],
"Student22" : [1],
"Student23" : [1],
"Student24" : [2, 3, 1],
"Student25" : [5, 2, 3, 6, 4, 11, 1],
"Student26" : [2, 3, 4, 7, 1],
"Student27" : [5, 2, 3, 6, 4, 11, 8, 1, 12],
"Student28" : [1],
"Student29" : [2, 3, 6, 4, 11, 7, 8, 1, 12],
"Student30" : [1],
"Student31" : [1],
"Student32" : [8],
"Student33" : [10, 5, 2, 3, 6, 11, 7, 1, 12],
"Student34" : [10, 5, 2, 3, 6, 4, 11, 7, 1],
"Student35" : [1],
"Student36" : [1],
"Student37" : [1],
"Student38" : [5, 2, 3, 6, 4, 11, 8, 1, 12, 13],
"Student39" : [1],
"Student40" : [1],
"Student41" : [2, 3, 6, 4, 7, 1],
"Student42" : [1],
"Student43" : [1],
"Student44" : [1],
"Student45" : [1],
"Student46" : [1],
"Student47" : [1],
"Student48" : [1],
"Student49" : [1],
"Student50" : [1],
"Student51" : [5, 3, 7, 1],
"Student52" : [1],
"Student53" : [10, 5, 2, 3, 6, 4, 11, 7, 1, 13],
"Student54" : [1],
"Student55" : [5, 2, 3, 6, 4, 11, 7, 1, 12],
"Student56" : [1],
"Student57" : [1],
"Student58" : [1],
"Student59" : [1],
"Student60" : [1],
"Student61" : [8],
"Student62" : [1],
"Student63" : [1],
"Student64" : [1],
"Student65" : [1],
"Student66" : [10, 5, 2, 3, 6, 4, 11, 7, 1, 12],
"Student67" : [1],
"Student68" : [1],
"Student69" : [5, 2, 3, 4, 11, 1],
"Student70" : [1],
"Student71" : [1],
"Student72" : [1],
"Student73" : [1],
"Student74" : [1],
"Student75" : [1],
"Student76" : [1],
"Student77" : [1],
"Student78" : [1],
"Student79" : [1],
"Student80" : [1, 14],
"Student81" : [1, 14],
"Student82" : [1],
"Student83" : [14],
"Student84" : [14],
"Student85" : [1, 14],
"Student86" : [15, 16, 17, 18, 19, 20, 21],
"Student87" : [1, 14],
"Student88" : [1, 14],
"Student89" : [14],
"Student90" : [14],
"Student91" : [1],
"Student92" : [14],
"Student93" : [1, 14],
"Student94" : [1, 14],
"Student95" : [14],
"Student96" : [1],
"Student97" : [1],
"Student98" : [8, 9, 14],
"Student99" : [1, 14],
"Student100" : [1],
"Student101" : [1, 14],
"Student102" : [1],
"Student103" : [1],
"Student104" : [1, 14],
"Student105" : [14],
"Student106" : [9],
"Student107" : [1, 14],
"Student108" : [14],
"Student109" : [1, 14],
"Student110" : [1],
"Student111" : [22, 15, 16, 8, 9, 18, 19, 20],
}

# Komşuluk matrisi çıkarma
matrix = [[0]*len(subjects) for i in range(len(subjects))]
for student in students:
	for i,j in itertools.combinations(students[student], 2):
		matrix[i-1][j-1] = 1
		matrix[j-1][i-1] = 1


# Düğüm derecelerini tespit etme ve düğüm derecesine göre sıralama
temp = {index+1:i for index, i in enumerate(matrix)}
subjects_temp = sorted(temp, key=lambda i:temp.get(i).count(1), reverse=True)

# Boyama verilerini tutmak ve 
# daha önce boyanmış düğümleri tekrar boyamamak için
colored = {}
color = get_color()

while len(subjects_temp):
	current_node = subjects_temp.pop(0)
	current_color = next(color)
	
	if not (current_node in colored):
		colored[current_node] = current_color
	

	# şu andaki düğümü, aşağıdaki for döngüsünde
	# kendisi ile karşılaştırmamak için dersler listesinden kaldırıyoruz
	subjects.remove(current_node)

	# bir düğüm(yani ders) başka bir düğüm ile komşu değilse
	# aynı renk veriliyor. Kısaca, bir dersle aynı anda
	# yapılabilecek diğer dersler aranıyor burada. Bunun için
	# bir liste oluşturacağız ve komşu olmayanları listeye ekleyeceğiz
	same_time_subjects = []
	for i in subjects:
		
		if not matrix[current_node - 1][i - 1] and not (i in colored):
			
			# ancak aynı zamanda yapılacak dersler
			# listesi oluşturabilmek için yeni eklenecek dersin
			# gruba daha önce eklenmiş diğer derslerle de komşu olmaması gerekir
			can_added = True
			for c in same_time_subjects:
				if matrix[int(c) - 1][i - 1]:
					can_added = False

			if can_added:
				same_time_subjects.append(i)
				colored[i] = current_color


# Tüm işlemler sonucunda aynı renk verilmiş tüm dersler
# Aynı gün ve saatte yapılabilir
x = 0
for i in set(colored.values()):
	x = x+1
	print(", ".join([str(x) for x in colored if colored[x]==i]), "dersleri aynı zamanda yapılabilir")

print("minimum", x, "oturumda yapılabilir")

Kod çalıştırılırsa çıktı şöyle olur.

8, 17 dersleri aynı zamanda yapılabilir
11 dersleri aynı zamanda yapılabilir
5, 20 dersleri aynı zamanda yapılabilir
4, 19 dersleri aynı zamanda yapılabilir
13 dersleri aynı zamanda yapılabilir
12 dersleri aynı zamanda yapılabilir
6, 22 dersleri aynı zamanda yapılabilir
10 dersleri aynı zamanda yapılabilir
2, 16 dersleri aynı zamanda yapılabilir
3, 18 dersleri aynı zamanda yapılabilir
1, 9, 21 dersleri aynı zamanda yapılabilir
7, 14, 15 dersleri aynı zamanda yapılabilir
minimum 12 oturumda yapılabilir

Burada neden dersleri komşu sayısına göre sıraladık? Çünkü algoritmaya göre her zaman komşu sayısı çok olandan başlanmalıdır. Böylece minimum oturum sayısına ulaşılabilir. Yani ilk hangi düğümden başladığı da önemlidir. Listeyi random.shuffle() ile karıştırıp işleme soktuğumda bazen 14 oturum sayısına da ulaşabiliyordum. Örneğin;

5 dersleri aynı zamanda yapılabilir
3, 19 dersleri aynı zamanda yapılabilir
4 dersleri aynı zamanda yapılabilir
10 dersleri aynı zamanda yapılabilir
7, 16 dersleri aynı zamanda yapılabilir
6, 18 dersleri aynı zamanda yapılabilir
12 dersleri aynı zamanda yapılabilir
2, 14, 15 dersleri aynı zamanda yapılabilir
13, 21, 22 dersleri aynı zamanda yapılabilir
11 dersleri aynı zamanda yapılabilir
20 dersleri aynı zamanda yapılabilir
8 dersleri aynı zamanda yapılabilir
9, 17 dersleri aynı zamanda yapılabilir
1 dersleri aynı zamanda yapılabilir
minimum 14 oturumda yapılabilir

Görüldüğü gibi çakışma yok, ama oturum sayısı bir önceki durumdan fazla.

1 Beğeni

Aybettin hocam, hatasız kul olur mu (Müslüm Gürses :slight_smile: ) Tekte hatasız kod yazıyorum diyen de gelip şurda delikanlıyım demesin zaten(print(“hello world”) dışında).

Bu arada ben de benim kodla sizinkinin outputunu karşılaştırdım, dersleri oturumlara atama şekli farklı ama 12 oturumda sizinkiyle anlaşıyoruz :yum:

1 Beğeni

Eyvallah kardeşim :slight_smile:

Evet birden fazla oturum kombinasyonu oluşturulabiliyor. Artık hocamız hoşuna gideni kullanır :sweat_smile:

1 Beğeni