[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 CDL avem 928 de lecții prof|obj|cls repartizate deja pe zile și pe orele zilei (reprezentând cu anumite simplificări orarul original, care fusese generat folosind aScTimetables); constituim lista l5z care asociază fiecărei zile setul lecțiilor din acea zi:
Zile <- c("Lu", "Ma", "Mi", "Jo", "Vi") l5z <- map(Zile, function(z) CDL %>% filter(zi == z) %>% select(-c(zi))) %>% # excludem câmpul 'zi' setNames(Zile)
Am păstrat câmpul obiectelor (principale sau secundare) obj; pentru cele principale, valorile obj se pot deduce din codurile prof – dar lecțiile pe discipline secundare constituie totuși 8.51% din totalul lecțiilor (deci n-ar fi de neglijat…):
> osc <- readRDS("df_obj_sec.RDS") # datele pentru disciplinele secundare > map_int(1:nrow(osc), function(i) length(strsplit(osc$cls[i], " ")[[1]])) %>% sum() [1] 79 # lecții pe discipline secundare (8.51% din totalul 928 al lecțiilor)
Având lista orarelor zilnice, putem stabili ușor distribuția pe zile a celor 928 de lecții:
> map_int(Zile, function(z) nrow(l5z[[z]])) %>% setNames(Zile) Lu Ma Mi Jo Vi 189 189 186 184 180 # ore pe zi
Era posibilă (probabil) și o distribuție echilibrată: două zile a câte 185 de ore plus 3 zile a câte 186 de ore (total, 928 ore).
Ne-ar interesa în ce măsură, orele fiecărui profesor sunt distribuite echilibrat pe zile (să nu aibă de exemplu, 2 ore într-o zi și peste 4 ore într-o altă zi); întâi, trebuie să factorizăm câmpul zi după vectorul Zile (e drept – era de făcut înainte de a descompune pe zile):
CDL <- CDL %>% mutate(zi = factor(zi, labels=Zile, ordered=TRUE))
fiindcă altfel, orice listare pe zile a unor linii din CDL ar începe alfabetic, cu ziua Jo (și nu cu Lu). Apoi, putem folosi table([W[c('prof', 'zi')]), unde W ar putea desemna setul CDL, sau numai subsetul celor neangajați în cuplaje, sau pe cel al celor angajați în cuplaje, sau subsetul cuplajelor (vom vedea mai încolo, că aceste separări sunt importante pentru a genera orarul); decupăm aici câteva linii:
prof Lu Ma Mi Jo Vi Sum Bl3 5 3 4 3 3 18 # repartiție "cvasi-omogenă" Ch1 4 3 4 4 3 18 # uniformă (omogenă) Ch2 2 3 3 5 5 18 # dezechilibrată Fz3 0 0 0 7 6 13 # (foarte dezechilibrat) Gg1 5 5 5 4 1 20
O repartiție uniformă pentru 13 ore (cât are Fz3, pe "Fizică") ar fi 2 2 3 3 3 (sau o permutare oarecare a acestui vector); probabil, condițiile specifice școlii respective au impus ca aceste 13 ore ale lui Fz3 să fie plasate în numai două (anumite) zile (implicând și faptul că 3 ore de "Fizică" la o aceeași clasă trebuie făcute în două zile – în loc de trei, cum s-ar cuveni pentru o repartizare „echilibrată”).
Condițiile concrete implicate în mod tacit în orarul respectiv discreditează cumva, ideea de repartizare „echilibrată” – încât mai bine abandonăm discuția tocmai inițiată mai sus.
l5z[["Lu"]] listează toate cele 189 de lecții din ziua Lu, câte una pe linie (analog, pentru celelalte zile). Ne-ar conveni mai mult – dar nu doar pentru a afișa orarul zilei – un format matriceal, reprezentând pe fiecare linie orarul câte unui profesor; am avea numai atâtea linii câți profesori au ore în acea zi și pe de altă parte, văzând șabloanele orare de pe linii putem determina (nu chiar „ușor”, trebuind să ținem seama de cuplaje) numărul de ferestre.
O luăm de la capăt…
Putem elimina obj (dacă ar fi cazul, datele din setul df_obj_sec.RDS asigură stabilirea lecțiilor care corespund unor discipline secundare); vrând orarul zilnic pe fiecare profesor, va trebui să împărțim lecțiile după zi și apoi după profesori – deci transformăm zi și prof în factori:
# stats.R rm(list = ls()) # elimină obiectele din sesiunea precedentă library(tidyverse) CDL <- readRDS("CDL.rds") # 928 lecții prof|obj|zi|ora|cls load("Tw123.Rda") # dicționarele dependențelor între profesori (și cuplaje) Zile <- c("Lu", "Ma", "Mi", "Jo", "Vi") CDL <- CDL %>% mutate(zi = factor(zi, levels = Zile, ordered=TRUE), prof = factor(prof)) %>% select(prof, cls, ora, zi) L5 <- map(Zile, function(z) CDL %>% filter(zi == z) %>% select(-c(zi))) %>% setNames(Zile) saveRDS(L5, "listCDL_zi.RDS")
Dacă în K am avea lecțiile dintr-o aceeași zi ale unuia dintre profesori, atunci prin pivot_wider() am ajunge la un format matriceal: valorile 1:7 din coloana ora ar deveni coloanele „matricei”, iar valorile din câmpul cls ar fi plasate corespunzător pe aceste coloane (folosind constanta NA, când în ora respectivă profesorul este liber). Numai că acum (spre deosebire de [2]) avem excepțiile evidențiate anterior în tabelul claselor cuplate Twc1; de exemplu, în unele zile cuplajul LG2LG3 are într-o aceeași oră clasele 11E și 11F – ceea ce ar însemna că în coloana orară respectivă, pivot_wider() trebuie să pună două valori.
În mod normal, nu se admit suprapuneri de valori; totuși, putem folosi parametrul values_fn, în care trebuie indicată o funcție care să unifice cumva, valorile respective (evitând astfel, eroarea de suprapunere). De exemplu, vectorul cu două valori ("11E", "11F") poate fi transformat (prin paste()) în șirul "11E11F", sau mai bine – ținând seama de faptul că pe fiecare linie din Twc1$Cls avem clase de pe un același nivel – în șirul "11EF".
Putem folosi expresii regulate, pentru a „unifica” un vector de clase din Twc1$Cls; șablonul unui astfel de vector repetă de două sau de trei ori (după numărul de clase cuplate), expresia "\\d+[[:alpha:]]" (reprezentând nivelul claselor și litera fiecăreia); reținem prima clasă și-i alipim literele celorlalte (încă una, sau două litere):
format_Twc <- function(v_cls) sub("(\\d+[[:alpha:]])\\d+([[:alpha:]])\\d*([[:alpha:]]*)", "\\1\\2\\3", paste(v_cls, collapse="")) > format_Twc(c("12A", "12B", "12D")) # [1] "12ABD" > format_Twc(c("12A", "12B")) # [1] "12AB"
Subliniem că "*" (cum am folosit la a treia clasă, în loc de "+") depistează zero sau mai multe apariții – încât dacă a treia clasă lipsește, referința "\\3" este înlocuită cu "".
Preferăm totuși următoarea formulare, parcă mai „simplă” (dar mai generală – pentru oricâte clase, cuplate pe un același nivel):
unify_Twc <- function(v_cls) { niv <- str_extract(v_cls, "\\d+") cls <- paste(str_extract(v_cls, "[A-Z]"), collapse="") paste0(niv[1], cls) # alipește primul nivel și literele claselor } > unify_Twc(c("10A", "10B", "10C", "10D", "10E")) # [1] "10ABCDE"
Următoarea funcție produce „matricea orară” a lecțiilor unei zile (din lista L5):
hourly_matrix <- function(Dorar) { # prof|cls|ora (pe ziua curentă) orz <- Dorar %>% droplevels() %>% split(.$prof) %>% map_df(., function(K) pivot_wider(K, names_from="ora", values_from="cls", values_fn = unify_Twc)) orz <- orz[, c('prof', sort(colnames(orz)[-1]))] %>% replace(is.na(.), '-') M <- as.matrix(orz) row.names(M) <- M[, 1] M[, 2:ncol(M)] } # prof: |1|2|3|4|5|6|7 (clasele profesorului, în fiecare oră)
Am păstrat numai profesorii care au ore în ziua respectivă (prin droplevels() am eliminat nivelele factorului prof corespunzătoare celor care nu au ore în acea zi); prin split() am obținut o listă care asociază fiecărui profesor, setul K al lecțiilor cls|ora ale sale; aplicând pivot_wider() pe această listă (și implicând unify_Twc() pentru cazul claselor cuplate) – rezultă în variabila 'orz', un „tabel” (obiect data.frame) în care prima coloană conține profesorii zilei și în celelalte avem clasele (sau clasele cuplate) unde intră aceștia în fiecare oră (sau avem NA când nu există o clasă asociată profesorului în ora respectivă).
A trebuit să așezăm coloanele orare în ordinea firească (folosind sort() și colnames()) și am înlocuit direct valorile NA prin '-' (liber în ora respectivă).
În final, am transformat setul 'orz' în matrice, având drept coloane orele 1:N (N≤7 fiind numărul de ore ale zilei) și având drept nume de linie (nu drept coloană), profesorii respectivi.
Redăm matricea orară a zilei Jo:
> jo <- hourly_matrix(L5[["Jo"]]) > print.table(jo) 1 2 3 4 5 6 1 2 3 4 5 6 Bl1 - 12C 10E - 11C 11A LG2LG1 - - 12EF 10AB - - Bl2 11E 8A - 10C 9E - LG2LG3 - 9EF - - 11EF - Bl3 12D 10B - 9D 6A 11D LG3 - - - 11C - 7B CC1 11C 11A - - 6B - LG3LG1LG4 11ABD - - - - - Ch1 10D 10A 10C 12B - - LG4 - 10E 10F 7B - 7A Ch2 7A - 8B - - - LI1 - 9B - - 12A 12A Ch3 - - 12D - - 11C LI2 - - 9C - - - Ch4 - - 12C 12C - - LI2LI3 9A 9A - - - - Ds1 12E 11F - - - 9F LI3 - - 11A 11D - - Ds1Mz1 - - 10B 10D 9CD - LR1 12B 11B 12A 12A - - ET1 6A 5B 5A - - 6B LR2 9B 5A 6B - 10B - Fl1 - - - 9F - 9B LR3 9F 10C 10D 11F - - Fz1 10C 9D - 9E 10D 10B LR4 8B 7A 7B 8A - - Fz2 - - - 9A 12D 12C LR5 10F - 9D 6A - - Fz4 7B 8B - 7A - - LR6 - 11E - 12F - - Gg1 12A - 12B 11E 10A 9A LR7 - - - - 11D 12D Gg2 12F 12F - 8B 7B 10D Mt1 5A 7B 5B 12D 7A - IH1 11F 11D 11B - - - Mt2 9D 12A 10A 11A - - Is1 10E 6A 7A 6B - - Mt3 10B 12B 9B 11B 11B - Is2 - - 11E 12E 9B 9C Mt4 12C - 11D - - - Is3 - - - - 12C 10A Mt5 - 10D - 10F 10C 10E LE1 - - 6A - 8B 9D Mt6 6B - 8A 9C - - LE2 - - - 9B 9F 12B Mz1 - - - - - 8B LE3 - 12E 11F - 9A 9E Ps2 - - - - - 11F LG1 - 6B - - - 6A Rl1 8A 12D 9F - 12B 10F LG1LG4 - - - - 10EF - Sp1 9E 9C 11C 5A 11A 10C LG2 5B - - - - 8A Sp2 10A 10F 9A 5B 8A 11B Tc1 9C 11C 9E 10E - 11E
Profesorul are fereastră când pe linia lui vedem '-' (liber în ora respectivă) între clase; dar dacă el face parte dintr-un cuplaj, atunci trebuie să verificăm dacă nu cumva fereastra respectivă este una „falsă”, fiind acoperită de cuplajul respectiv; deasemenea, dacă pe linia profesorului nu sunt ferestre, dar el face parte dintr-un cuplaj – atunci trebuie să verificăm dacă nu cumva are o fereastră „ascunsă”, anume o fereastră de pe linia acelui cuplaj.
Astfel, vedem că Ch3 (care nu este angajat în cuplaje) are două ferestre, în orele 4 și 5; Ds1 are aparent 3 ferestre (în orele 3, 4 și 5) – dar face parte din cuplajul Ds1Mz1, care acoperă „ferestrele” respective (în ora a treia se intră „pe grupe” la clasa 10B, apoi la fel la 10D și apoi în ora 5, se intră la clasele cuplate 9CD); iar LG1 are numai aparent 3 ferestre, acestea fiind de fapt ocupate de cuplajele care îl angajează:
> jo[grepl('LG1', rownames(jo)), ] 1 2 3 4 5 6 LG1 "-" "6B" "-" "-" "-" "6A" LG1LG4 "-" "-" "-" "-" "10EF" "-" LG2LG1 "-" "-" "12EF" "10AB" "-" "-" LG3LG1LG4 "11ABD" "-" "-" "-" "-" "-"
Dintre cei 8 profesori angajați în cuplaje, unul singur, LG3 are o fereastră (în ora 3):
> print.table(jo[grepl('LG3', rownames(jo)), ]) 1 2 3 4 5 6 LG2LG3 - 9EF - - 11EF - LG3 - - - 11C - 7B LG3LG1LG4 11ABD - - - - -
Până la urmă nu-i chiar greu, de socotit manual câte ferestre sunt în orarul respectiv – pentru Jo, sunt în total 28 de ferestre. Nu stăm să analizăm și celelalte zile – probabil că în fiecare zi sunt așa de multe ferestre; grija de a asigura desfășurarea lecțiilor cuplate (între profesori și multe, pe clase cuplate) a condus la situația în care cei angajați în cuplaje au în total foarte puține ferestre, în schimb cei care au doar ore proprii (nu în vreun cuplaj) au fost cumva neglijați, căpătând foarte multe ferestre…
Dacă vizăm ferestrele, nu interesează clasa la care intră profesorul (singur, sau într-un cuplaj), ci doar faptul că intră sau nu, la una oarecare dintre clase, într-una sau alta dintre orele zilei. Cu alte cuvinte, interesează șablonul orelor profesorului; de exemplu, în ziua Jo șablonul orelor lui LG3 (al cărui orar tocmai l-am listat mai sus) este "**-***", exprimând faptul că are de intrat (eventual, în cuplaj) la anumite clase în orele 1, 2, 4, 5, 6 și este liber în ora a 3-a a zilei – desigur, acest șablon rezultă „însumând” pe cel corespunzător liniei sale, cu cele corespunzătoare liniilor cuplajelor în care este implicat.
Și interesează ferestrele profesorilor propriu-ziși (ca LG3), nu ale celor „fictivi” (cuplaje, ca LG2LG3) – cu excepția cuplajelor cu un profesor „extern”: acesta nu are ore proprii în ziua respectivă, ci doar în unul sau mai multe cuplaje (atunci, orice fereastră pe suma șabloanelor acestor cuplaje devine o fereastră „ascunsă”, pentru acel profesor).
Bineînțeles că putem înlocui '*' cu 1 și '-' cu 0; indexând orele nu de la stânga spre dreapta (cum avem pe liniile din matricea orară), ci de la dreapta spre stânga (cum sunt indexați biții dintr-un integer) – ajungem (pentru linia lui LG3) la șablonul binar '00111011', care în baza 10 are valoarea 25 + 24 + 23 + 2+1=59.
În „șablonul binar” (de tip byte, sau „octet”), bitul de rang h=0:6 reprezintă ora de rang (h+1) a zilei; următorul vector specifică „măștile” orelor 1:7 ale zilei (valorile 2h, h=0:6):
h2bin <- as.integer(c(1, 2, 4, 8, 16, 32, 64))
Putem produce într-un vector „cu nume”, valorile șabloanelor binare corespunzătoare liniilor matricei orare a unei zile (deci corespunzător profesorilor pe acea zi), prin funcția:
bin_patterns <- function(h_mat) apply(h_mat, 1, function(Row) sum(h2bin[which(! Row %in% "-")])) > bin_patterns(jo) # exemplificare Bl1 Bl2 Bl3 CC1 Ch1 Ch2 Ch3 # ETC. 54 27 59 19 15 5 36
Numărul de ferestre dintr-un șablon binar (dat ca valoare în baza 10) poate fi obținut prin:
count_holes <- function(sb) { # sb: valoarea șablonului binar bits <- which(bitwAnd(sb, h2bin) > 0) # rangurile biților '1' n <- length(bits) bits[n] - bits[1] + 1 - n } # Numărul de biți '0' aflați între biți '1' ("ferestre")
bitwAnd() este (ca de obicei în R) o funcție „vectorizată”: se operează "AND pe biți" între întregul indicat de sb și fiecare întreg din vectorul h2bin, returnând vectorul valorilor rezultate (din care am reținut numai valorile nenule – ale căror indecși în vectorul rezultat (obținuți prin which()) ne dau rangurile biților 1 din octetul sb).
Am subliniat deja, că pentru a socoti corect ferestrele trebuie să ținem seama de „dependențele” curente ale profesorului respectiv; acestea sunt precizate deja – dar global, pe întreaga săptămână – în dicționarele Tw1, Tw2 și Tw3; am putea să le restricționăm la ziua curentă (și este cel mai bine, dicționarele respective servind și în alte scopuri decât pentru numărarea ferestrelor din matricele orare) – dar de fapt, putem ignora acum dicționarele globale respective, procedând ad-hoc (analizăm direct numele de linie ale matricei orar curente):
day_deps <- function(h_mat) { dprof <- rownames(h_mat) Ld <- dprof %>% split(nchar(.)) if(length(Ld)==1) Ld <- append(Ld, rep("", 2)) else {if(length(Ld)==2) Ld <- append(Ld, "")} # Ld[[1]]: cu ore proprii și eventual, apar și în cuplaje # L2[[2]], Ld[[3]]: cuplajele de câte doi, sau trei, profesori # dependențe la cei cu ore proprii care apar și în cuplaje: Deps <- lapply(Ld[[1]], function(P) c(Ld[[2]][grepl(P, Ld[[2]])], Ld[[3]][grepl(P, Ld[[3]])])) %>% setNames(Ld[[1]]) %>% compact() # cei externi se află printre cei angajați în cuplaje: pos <- union(union(union(Ld[[2]] %>% substr(., 1,3), Ld[[2]] %>% substr(., 4,6)), union(Ld[[3]] %>% substr(., 1,3), Ld[[3]] %>% substr(., 4,6))), Ld[[3]] %>% substr(., 7,9)) %>% unique() pex <- setdiff(pos[pos != ""], Ld[[1]]) # externi (apar numai în cuplaje) # cuplajele în care apar cei externi (dacă aceștia există) Ext <- lapply(pex, function(P) { cpl <- c(Ld[[2]][grepl(P, Ld[[2]])], Ld[[3]][grepl(P, Ld[[3]])]) cpl[cpl != ""] }) %>% setNames(pex) %>% compact() list(Deps = Deps, Ext = Ext) }
Nu neapărat în fiecare zi, avem cuplaje; am adăugat elemente „nule” ("") listei Ld în care am partiționat numele de linie ale matricei, în scopul de a preveni eroarea de a accesa ulterior Ld[[3]] sau Ld[[2]] (vectorul cuplajelor de 3 sau 2 profesori, dacă există); bineînțeles că apoi, a trebuit să reținem numai valorile diferite de "".
Exemplificăm pentru ziua Mi:
> mi <- hourly_matrix(L5[["Mi"]]) # matricea orară a zilei > dmi <- day_deps(mi) # dependențele zilei > str(dmi) List of 2 $ Deps:List of 5 ..$ LE3: chr "LE3Mz1" ..$ LG1: chr [1:3] "LG1LG4" "LG2LG1" "LG3LG1LG4" ..$ LG3: chr "LG3LG1LG4" ..$ LG4: chr [1:2] "LG1LG4" "LG3LG1LG4" ..$ Mz1: chr "LE3Mz1" $ Ext :List of 3 ..$ LG2: chr "LG2LG1" ..$ Tc2: chr "Tc2LI1" ..$ LI1: chr "Tc2LI1"
Deci pe Mi sunt 3 profesori externi; ferestrele cuplajului LG2LG1 dacă există, sunt ferestre „ascunse” ale lui LG2; cele ale cuplajului Tc2LI1, dacă există, sunt ferestre ascunse pentru fiecare dintre cei doi profesori implicați.
Să formulăm acum o funcție count_daygaps() care să furnizeze numărul de ferestre din matricea orară curentă… Poate că între timp, modificăm într-un fel sau altul matricea orară a zilei (preluată inițial din lista L5) – de exemplu pentru a „repara” o fereastră; dacă nu adăugăm sau eliminăm vreo lecție (ci doar schimbăm clase dintr-o coloană orară într-o alta), atunci proprietățile de dependență nu vor fi afectate – prin urmare, dependențele date de day_deps() se cuvine să fie obținute „din start” (și nu în interiorul funcției count_daygaps()), făcându-le disponibile calculului intern atât pe matricea orară inițială, cât și pe una rezultată prin modificarea acesteia:
# în exteriorul funcției count_daygaps() zi <- "Mi" # de exemplu HM <- hourly_matrix(L5[[zi]]) dps <- day_deps(HM) Dep <- dps[["Deps"]] # cu ore proprii, dar angajați și în cuplaje Ext <- dps[["Ext"]] # angajați în cuplaje, dar fără ore proprii Nec <- setdiff(rownames(HM), union(names(Dep), names(Ext))) Nec <- Nec[nchar(Nec) == 3] # neangajați în vreun cuplaj count_daygaps <- function(Hm) { # pe matricea orară curentă bpt <- bin_patterns(Hm) # vectorul șabloanelor binare (curente) ng <- 0 # numărul total de ferestre (inițial zero) for(P in names(Dep)) # cu ore proprii, dar și în cuplaje ng <- ng + count_holes(sum(c(bpt[P], bpt[Dep[[P]]]))) for(P in names(Ext)) # cazul celor externi zilei ng <- ng + count_holes(sum(bpt[Ext[[P]]])) # adăugăm ferestrele celor neimplicați în cuplaje ng + sum(unlist(lapply(bpt[Nec], count_holes), use.names=FALSE)) }
Acum putem vedea repartiția pe zile a numărului total de ferestre din orarul inițial:
gaps <- vector("integer", 5) %>% setNames(Zile) for(z in Zile) { HM <- hourly_matrix(L5[[z]]) dps <- day_deps(HM) Dep <- dps[["Deps"]] Ext <- dps[["Ext"]] Nec <- setdiff(rownames(HM), union(names(Dep), names(Ext))) Nec <- Nec[nchar(Nec) == 3] gaps[z] <- count_daygaps(HM) } print(gaps) Lu Ma Mi Jo Vi 27 26 24 28 16 # în total, 121 ferestre
sum(gaps) ne dă numărul total de ferestre, 121 – ceea ce reprezintă 13.04% (foarte mult!) din totalul 928 al lecțiilor din orar; probabil că prin programul de reducere a ferestrelor din [2] s-ar putea ajunge într-un timp rezonabil, la un orar în care numărul total de ferestre este mai puțin de 4% din totalul lecțiilor (sperăm, că așa este… Lucrurile sunt complicate aici, având multe perechi și chiar triplete, de „clase cuplate”).
Dar probabil că trebuie să subliniem: nu aceste numere sunt importante… (ci probabil, aparatul contextual constituit pentru a le evidenția).
—v. Partea a V-a—
dar v. și părțile precedente, unde "v." înseamnă cumva "vezi folosind un laptop" nu telefonul… folosești telefonul pentru mesaje, reclame și plăți – nicidecum pentru povești, mai ales „de programare”
vezi Cărţile mele (de programare)