[1] Problema orarului școlar echilibrat și limbajul R
[2] V. Bazon - Orare școlare echilibrate și limbajul R https://books.google.ro/books?id=aWrDEAAAQBAJ
În cls23_days.RDS am fixat o repartizare pe zile a lecțiilor P23|C23 unde P23 este un cuplaj de doi sau trei profesori, iar C23 este un cuplu sau un triplet de clase; ansamblul elevilor acestor clase va fi partiționat în două sau trei grupe și la fiecare dintre acestea va intra – într-o aceeași zi și o aceeași oră a zilei – câte un profesor din cuplajul P23.
Dar să observăm că n-am terminat… Încă nu-i vorba de faptul că avem de repartizat (dar nu „manual”) și celelalte 870 de lecții – pe care le-am separat deja în lessons.RDS – ci de faptul că după ce le vom fi repartizat pe zile și pe acestea, va trebui să completăm "orarul" obținut, cu liniile P23|C23|zi din cls23_days.RDS; ori C23 este un vector cu două sau trei clase, nu o clasă propriu-zisă cum avem în lessons.RDS.
Pentru a putea face completarea menționată va trebui să descompunem P23 și C23, după acest model: lecția în cuplaje (și de profesori și de clase) "Ds1Mz1 / 9A 9B / Lu" se descompune în "Ds1 / 9A / Lu" și "Mz1 / 9B / Lu". N-am descompus „din start”, fiindcă vom avea de montat ulterior și coloana "ora" – ceea ce este mai ușor de făcut pe setul „sintetic” cls23_days.RDS, decât după descompunerea acestuia.
Următoarea funcție primește ca argument setul curent – cel inițial din cls23_days.RDS, dar poate fi și o modificare ad_hoc ulterioară a acestuia – și produce descompunerea acestuia după profesorii și clasele din cuplaje:
decompose23 <- function(K23) { K23 <- K23 %>% mutate(prof = as.character(prof)) map_dfr(1:nrow(K23), function(i) { vpr <- strsplit(K23[i, 1], "(?<=.{3})", perl=TRUE)[[1]] vcl <- strsplit(K23[i, 2], " ")[[1]] data.frame(prof = vpr, cls = vcl, zi = K23[i, 3]) }) } P23 <- readRDS("cls23_days.RDS") print(decompose23(P23)[45:58, ]) prof cls zi 45 LG3 12A Ma # LG3LG1LG4 la 12ABD (Ma) 46 LG1 12B Ma 47 LG4 12D Ma 48 LG3 12A Mi # LG3LG1LG4 la 12ABD (Mi) 49 LG1 12B Mi 50 LG4 12D Mi 51 LG3 10E Vi # LG3LG4 la 10EF (Vi) 52 LG4 10F Vi 53 Ds1 10A Jo # Ds1Mz1 la 10AC (Jo) 54 Mz1 10C Jo 55 Ds1 10B Mi # Ds1Mz1 la 10BD (Mi) 56 Mz1 10D Mi 57 Ds1 10E Vi # Ds1Mz1 la 10EF (Vi) 58 Mz1 10F Vi
prof fiind (în CDL și apoi, în subseturile derivate, inclusiv K23) de tip factor, a trebuit să-l transformăm în character pentru a putea să-i aplicăm strsplit(). Precizăm că expresia regulată "(?<=.{3})" asigură izolarea subșirurilor de câte 3 caractere, corespunzătoare celor doi sau trei profesori din cuplajul P23 respectiv.
Va fi ușor să modificăm eventual decompose23(), pentru a avea în vedere și coloana "ora" pe care o vom adăuga pentru fiecare zi, mai încolo.
Când am constituit cls23_days.RDS am urmărit să avem o distribuție a cuplajelor P23 care să fie echilibrată (atât pe zile, cât și pe fiecare cuplaj în parte); dar… descompunerea pe profesorii componenți a acestor cuplaje, nu este neapărat, echilibrată:
dP23 <- decompose23(readRDS("cls23_days.RDS")) > dP23 %>% arrange(zi, prof) prof Lu Ma Mi Jo Vi Sum Ds1 1 1 1 1 1 5 LG1 3 3 4 2 3 15 # repartiție neomogenă LG2 3 3 3 3 3 15 LG3 2 2 2 2 3 11 LG4 1 1 2 1 2 7 Mz1 1 1 1 1 1 5 Sum 11 11 13 10 13 58
Pentru a uniformiza distribuția pe zile a lecțiilor lui LG1 (…de parcă n-am avea ce face), ar trebui să căutăm printre cele 4 lecții care îl angajează în ziua Mi, una pe care să o schimbăm din ziua Mi în ziua Jo (și atunci, LG1 ar avea de făcut câte 3 lecții pe zi); dar aceste lecții sunt pe „clase cuplate”, deci schimbarea dintr-o zi în alta a acelei lecții angajează doi (sau trei) profesori și două (sau trei) clase…
De fapt, nu este cazul de a efectua asemenea schimbări; pe lângă cele 15 lecții în cuplaje, evidențiate mai sus, LG1 are și lecții proprii – rămase în lessons.RDS – și avem de urmărit echilibrarea distribuției tuturor lecțiilor sale (la fel, pentru ceilalți cinci din dP23$prof).
Va fi mai convenabil de schimbat dintr-o zi în alta (în vederea echilibrării distribuțiilor individuale) lecții care nu angajează clase cuplate – deci lecții din lessons.RDS (desigur, după ce le vom fi repartizat pe zile). Să formulăm un tabel informativ prin care să putem distinge când va fi cazul, între lecțiile pe clase cuplate și cele proprii, ale profesorilor din dP23$prof:
p23 <- unique(dP23$prof) k23 <- k1 <- vector("character", length(p23)) for(i in 1:length(p23)) { K <- dP23 %>% filter(prof == p23[i]) %>% pull(cls) %>% unique() k23[i] <- paste(K, collapse=" ") k1[i] <- LSS %>% filter(prof == p23[i] & ! cls %in% K) %>% pull(cls) %>% unique() %>% paste(., collapse=" ") } k23_1 <- data.frame(prof=p23, cls23 = k23, cls1 = k1) prof cls23 cls1 1 Ds1 9A 9C 10A 10B 10E 5A 5B 6A 6B 7A 7B 8A 8B 9E 9F 11E 11F 12E 12F 2 Mz1 9B 9D 10C 10D 10F 5A 5B 6A 6B 7A 7B 8A 8B 9E 9F 12F 3 LG1 10E 10B 10D 12F 9B 11B 12B 6A 6B 9D 4 LG4 10F 11D 12D 5A 7A 7B 9C 10E 5 LG2 10A 10C 12E 9A 11E 9E 5A 5B 8A 8B 6 LG3 11F 9F 11A 12A 10E 7A 7B 11C 12C
În coloana cls23 avem clasele la care trebuie să intre (după cuplarea acestora în perechi sau triplete de clase) profesorii din dP23$prof, iar în coloana cls1 – clasele la care aceștia au ore proprii (intră singuri, nu în cuplaj). Dacă va trebui să echilibrăm distribuția (tuturor) lecțiilor lui LG1 de exemplu, atunci ne vom gândi să schimbăm dintr-o zi în alta lecții ale sale la clasele 6A, 6B sau 9D (cele din coloana cls1).
Vom avea nevoie desigur, de o funcție prin care să putem schimba o lecție dintr-o zi în alta, într-un set dat ("RC") de lecții prof|cls|zi:
change_zl <- function(P, Q, Z, new_zl, RC) { wh <- which(with(RC, prof==P & cls==Q & zl==Z) == TRUE) if(length(wh) > 1) wh <- wh[1] # P are 2 ore la Q în ziua Z? mută numai una RC[wh, "zl"] <- new_zl RC } # alocă o lecţie într-o altă zi, returnând distribuţia modificată
Am avut grijă ca în cazul când P are mai multe ore la clasa Q în ziua zl, atunci să schimbăm ziua numai pentru una dintre lecțiile respective. De observat că în loc de "zi" cum avem în cls23_days.RDS, am folosit "zl" cum avem în funcțiile din [2] pe care urmează acuși să le angajăm (dar rename(RC, zl=zi) corectează imediat lucrurile, dacă este cazul).
Vom avea nevoie mai târziu, de funcțiile change_zl() și decompose23() – așa că le încorporăm într-un fișier utils.R (în care înregistrăm pentru orice eventualitate și tabelul k23_1).
Înainte de a trece la repartizarea pe zile a lecțiilor rămase, trebuie să „curățăm” cumva setul obținut în lessons.RDS și deasemenea, dicționarele dependențelor:
> LSS <- readRDS("lessons.RDS") > load("Tw123.Rda") # dicționarele (inițiale) de dependențe
levels(LSS$prof) conține și cuplajele P23, pe care le separasem mai sus în cls23_days.RDS; am putea aplica droplevels(), dar pentru cele ce urmează preferăm să transformăm ambele coloane, din factor în character:
> LSS <- LSS %>% mutate_if( is.factor, as.character) > saveRDS(LSS, "lessons.RDS") # 870 lecții prof|cls (cu 66 profesori pe 32 clase)
Pe cele 870 de lecții rămase avem mai puține dependențe între profesori, decât cele stabilite inițial (pentru întregul set CDL) în Tw123.Rda; avem de eliminat din Tw1 și Tw2, cheile implicate de cuplajele P23:
load("Tw123.Rda") # dicționarele dependențelor (inițiale) dP23 <- decompose23(P23) xp <- dP23 %>% pull(prof) %>% unique() Tw1[xp] <- NULL # $LI1 [1] "LI1LI3" "LI2LI1" "Tc2LI1" # $LI2 [1] "LI2LI1" "LI2LI3" # $LI3 [1] "LI1LI3" "LI2LI3" # $Tc2 [1] "Tc2LI1" Tw2[P23$prof] <- NULL # $LI2LI1 [1] "LI2" "LI1" "LI2LI3" "LI1LI3" "Tc2LI1" # $LI2LI3 [1] "LI2" "LI3" "LI2LI1" "LI1LI3" # $Tc2LI1 [1] "Tc2" "LI1" "LI1LI3" "LI2LI1" save(Tw1, Tw2, file="Tw12.Rda")
În Tw12.Rda avem dependențele specifice lecțiilor rămase în lessons.RDS. Cheile din Tw1 reprezintă profesorii P din lessons.RDS care au și ore proprii și ore în cuplaje, iar alocarea lecțiilor lui P (pe zile și pe orele zilei) va depinde de alocările făcute cuplajelor înregistrate în Tw1[[P]]. În Tw2 avem cuplajele (de câte doi profesori) care au rămas în lessons.RDS, împreună cu profesorii și cuplajele de care depinde alocarea lecțiilor acestora.
Imităm programul din [2] care angajează funcțiile de repartizare pe zile, a lecțiilor celor neangajați în cuplaje și respectiv, a lecțiilor cuplate de câte doi profesori pe câte o aceeași clasă, existente în lessons.RDS:
# mount_zi.R rm(list = ls()) # elimină obiectele din sesiunea precedentă library(tidyverse) LSS <- readRDS("lessons.RDS") # 870 lecții prof|cls load("Tw12.Rda") # dicționarele dependențelor Zile <- c("Lu", "Ma", "Mi", "Jo", "Vi") perm_zile <- readRDS("lstPerm47.RDS")[[2]] # cele 720 permutări de zile source("by_days.R") # mount_days_necup() și mount_days_cup() (v. [2]) LS1 <- LSS %>% # lecțiile necuplate (în număr de 818) filter(! prof %in% union(names(Tw1), names(Tw2))) LS2 <- anti_join(LSS, LS1, by = c('prof', 'cls')) # lecțiile cuplate (52) prnTime <- function(S = "") cat(strftime(Sys.time(), format="%H:%M:%S"), S) while(TRUE) { prnTime() R1 <- mount_days_necup(LS1) # R2 <- mount_days_cup(LS2) prnTime("\n") s1 <- addmargins(table(R1[c('prof','zl')]))["Sum", 1:5] %>% as.vector() print(s1) if(diff(range(s1)) <= 2) break; }
Am redat aici numai secvența care produce repetat repartiții R1, pentru lecțiile necuplate (repetând până când se obține o repartiție „echilibrată”); înlocuind "R1" cu "R2" și "LS1" cu "LS2" – și folosind "diff(range(s1)) <= 1)" drept condiție de ieșire din ciclul while(TRUE) – va rezulta (prin mount_days_cup()) o repartiție pe zile R2 (echilibrată), pentru lecțiile cuplate.
Lansând programul în diverse momente de timp, se obțin rezultate diferite; redăm un exemplu de lucru:
> source("mount_zi.R") 09:13:07 ******************************** 09:13:24 [1] 162 163 165 164 164 09:13:24 ******************************** 09:14:29 [1] 165 167 163 158 165 09:14:29 ******************************** 09:14:46 [1] 163 161 165 163 166 09:14:46 ******************************** 09:15:18 [1] 165 161 164 163 165 09:15:18 *****************************/ ******************************** 09:16:38 [1] 163 164 161 163 167 09:16:38 ******************************** 09:17:18 [1] 169 164 162 162 161 09:17:18 ******************************** 09:18:02 [1] 163 164 164 163 164 # o repartiție uniformă a celor 818 lecții necuplate > saveRDS(R1, "R1.RDS")
Precizăm în treacăt, că mount_days_necup() (din programul by_days.R) etichetează cu o permutare aleatorie de Zile, lecțiile fiecărei clase – marcând pe ecran trecerea de la o clasă la următoarea, prin "*"; iar când etichetarea lecțiilor clasei curente eșuează, se afișează "/" și se reia de la capăt, schimbând aleatoriu ordinea claselor. "Eșuează" ține de epuizarea permutărilor de Zile pentru a aloca lecțiile clasei curente, dar ține mai ales de „echilibrare”: nu se acceptă alocarea făcută, dacă vreunul dintre profesorii clasei curente capătă la momentul respectiv (ținând seama de lecții alocate anterior) o distribuție pe zile dezechilibrată (cu diferență mai mare de 2 ore, între o zi și alta).
Repartiția pe zile obținută în R1.RDS este una omogenă (câte 163 sau 164 de lecții pe zi), iar profesorii au în R1 distribuții individuale cvasi-omogene (cu diferență de cel mult două ore, între o zi și alta); dar nu toate clasele, au căpătat distribuții echilibrate (însă va fi de văzut cum stau lucrurile, abia după ce vom adăuga și repartiția R2).
După modificarea programului, cum am indicat mai sus – o repartiție echilibrată R2 se obține instantaneu și are această distribuție pe zile:
> table(R2$zl) Lu Ma Mi Jo Vi 10 11 10 11 10
Cumulând distribuțiile pe zile din R1 și R2, am avea o distribuție uniformă (câte 174 pe zi) a lecțiilor din lessons.RDS dacă am schimba din ziua Ma în ziua Lu fie o lecție din R1, fie una din R2. Să facem în acest moment (nu neapărat, cel mai potrivit) o schimbare, anume în R2; întâi inspectăm lecțiile pe primele două zile:
> R2 %>% filter(zl %in% c("Lu", "Ma")) %>% arrange(zl, prof) prof cls zl 1 LI1 12A Lu 2 LI1 9B Lu 3 LI2 10C Lu 4 LI2 9A Lu 5 LI2LI1 10A Lu 6 LI3 11A Lu 7 LI3 11D Lu 8 Tc2 10B Lu 9 Tc2 8A Lu 10 Tc2LI1 12A Lu 11 LI1 10B Ma 12 LI1 12A Ma 13 LI1 12A Ma 14 LI2 5B Ma 15 LI2 6B Ma 16 LI2LI3 9A Ma 17 LI3 11A Ma 18 LI3 11B Ma # de mutat în ziua Lu 19 Tc2 12B Ma 20 Tc2 12B Ma 21 Tc2 9B Ma
Cel mai convenabil este schimbarea lecției lui LI3 la clasa 11B:
> R2 <- change_zl("LI3", "11B", "Ma", "Lu", R2) > table(R2$zl) Lu Ma Mi Jo Vi 11 10 10 11 10 > saveRDS(R2, "R2.RDS")
Prin următoarea secvență reunim cele trei repartiții pe zile, R1, R2 și dP23:
R1 <- readRDS("R1.RDS") # lecțiile prof|cls|zl necuplate (818) R2 <- readRDS("R2.RDS") # prof|cls|zl cu 'prof'=cuplaj de 2 profesori (+ 52) dP23 <- decompose23(readRDS("cls23_days.RDS")) %>% rename(zl = zi) # 'prof' în P23, 'cls' în C23 (+ 58 lecții) R12 <- R1 %>% rbind(R2) %>% rbind(dP23) # 928 lecții prof|cls|zl saveRDS(R12, "R12i.RDS>")
Putem verifica frumos (folosind addmargins(), table() și rbind()), distribuțiile pe zile:
> addmargins(table(R1$zl) %>% rbind(table(R2$zl)) %>% rbind(table(dP23$zl))) Lu Ma Mi Jo Vi Sum . 163 164 164 163 164 818 11 10 10 11 10 52 11 11 13 10 13 58 Sum 185 185 187 184 187 928
Dacă vrem neapărat (și… chiar vrem) ca distribuția finală din R12 să fie una „perfectă” (două zile cu câte 185 și trei zile cu câte 186 de ore), atunci va trebui să mutăm în ziua a 4-a câte o lecție din zilele 3 și 5; bineînțeles că am alege să mutăm lecții din setul R1 (nicidecum din dP23, în care o lecție angajează perechi sau triplete de clase și doi sau trei profesori).
mount_days_cup() asigură ea însăși, că după ce îmbinăm R1 cu R2, nicio clasă nu va avea mai puțin de 3 ore sau mai mult de 8 ore pe zi; dar adăugând și dP23, s-ar putea să avem la unele clase și 9 ore, în vreo zi… În orice caz, trebuie să verificăm distribuția pe zile a lecțiilor pentru fiecare clasă și dacă este cazul, va trebui să mutăm anumite lecții (preferabil, din setul R1) dintr-o zi în alta – căutând să echilibrăm distribuțiile respective, precum și distribuțiile individuale (mai ales,la profesorii care au lecții și în dP23); ne putem folosi în acest scop, de programe R interactive precum cele redate în [2] – prin care de exemplu, se afișează pe ecran repartiția pe zile a uneia sau alteia dintre clase, însoțită de repartițiile pe zile a lecțiilor profesorilor acelei clase și se solicită, pentru îndreptarea anumitor „defecte”, alegerea unei lecții care să fie schimbată prin change_zl().
vezi Cărţile mele (de programare)