Ritmuri (ultime clarificări asupra tuplajelor)
[1] Pachetele R days2lessons, hours2lessons și refitgaps
Introducere
Pe orarele școlilor întâlnim cuplaje și tuplaje, de obicei pentru "Muzică" și "Desen", sau pentru limbi străine — cum sugerează poza următoare, decupată de pe imaginea PDF "Orarul general clase" din site-ul Web al unei anumite școli:
În ora a 6-a a zilei respective, elevii clasei 10A sunt despărțiți în două grupe (fixate din start); la o grupă intră un profesor de "Desen", iar la cealaltă unul de "Muzică" și în modul tacit obișnuit, cei doi profesori vor alterna săptămânal grupele ("Muz/Des", apoi "Des/Muz") — încât ritmul acestor discipline este 1/2 ("o oră la două săptămâni").
Pentru clasa 10B, în ora a 5-a avem se pare, aceeași situație de cuplare a doi profesori pe câte o grupă de elevi ai clasei: la o grupă intră un profesor de "Franceză", iar la cealaltă unul de "Germană"; dar să observăm că tot în ora a 5-a, clasa 10A face și ea "Germană" și consultând "Orarul general profesori" constatăm că ambele clase fac "Germană" cu un același profesor (încât acesta ar trebui să intre în ora a 5-a și la 10A și la o grupă a clasei 10B)… Prin urmare, cei doi profesori sunt cuplați nu pe câte o grupă a unei aceleiași clase, ci pe două clase (determinând un "tuplaj"): elevii reuniți din clasele 10A și 10B sunt redistribuiți în două "noi" clase, care în ora a 5-a fac "Germană" și respectiv "Franceză" (… cu ritmul normal, 1/1).
Un tuplaj mai complicat avem pe clasele 10C, 10D și 10E (în ora întâia) și constatăm că sunt implicați trei profesori (doi de "Franceză" și unul de "Germană"); elevii reuniți ai celor trei clase sunt redistribuiți ad-hoc în trei "noi" clase, la care intră (în ora întâia a zilei respective) câte unul dintre cei trei profesori.
Bineînțeles că lecțiile dintr-un același tuplaj trebuie alocate în câte o aceeași zi (iar un același tuplaj poate să figureze în mai multe zile) și într-o aceeași oră a zilei curente; dar în privința tuplajelor, în pachetele [1] avem o diferență cam ciudată: repartizarea finală pe zile include (firește) lecțiile tuplate — dar apoi, pentru a repartiza pe orele zilei se presupune în mod tacit că dintre lecțiile zilei respective s-au exclus lecțiile tuplate (alocarea pe ore a lecțiilor tuplate fiind separată cumva, de alocarea pe ore a lecțiilor obișnuite). Ca urmare, înainte de a trece la alocarea pe ore a lecțiilor zilei curente, utilizatorul pachetelor [1] trebuie să elimine lecțiile tuplate…
Ar fi de completat pachetul days2lessons cu două funcții publice: una care desparte pe zile setul tuplajelor (și care de fapt, extinde funcția days2tupl(), introdusă în ultima versiune a pachetului) și una care elimină din setul lecțiilor unei zile, lecțiile aferente tuplajelor existente pe ziua respectivă. S-ar putea totuși, să găsim o idee de lucru mai bună, care să evite "necesitatea" (cam artificială) de a elimina lecțiile tuplate…
Pentru exemplificări ne vom servi de datele orarelor în format PDF de pe care am ilustrat mai sus, dar fără a mai pomeni modul (deja îndelung discutat anterior, pe aici) în care am extras datele respective din poza PDF a orarului; profităm totuși de acest prilej pentru încă o revedere a pachetelor [1].
Problema orarului școlar (clarificări principiale)
În planul de încadrare pregătit pentru noul an școlar de către conducerea școlii, se precizează pentru fiecare profesor al școlii, numele și prenumele, gradul didactic, disciplinele pe care este încadrat, clasele repartizate și numărul corespunzător de ore. Normativele existente asupra numărului maximal de ore pe profesor, pe clasă și pe obiect (disciplină) fac posibilă încropirea unui orar săptămânal, pentru desfășurarea tuturor lecțiilor prof|obj|cls prevăzute în planul de încadrare (și de fapt, sunt posibile foarte multe orare, mai bune sau mai rele fie pentru elevi, fie pentru profesori).
De obicei, mai în toate școlile, orarul școlar este produs sârguincios prin aplicația comercială ascTimetables (sau adaptarea SIVECO "aSc Orare", semnată în subsolurile paginilor PDF prin care este prezentat orarul pe site-ul școlii).
Pe de altă parte… ca teorie, “problema orarului școlar” (School Timetable Problem) are o vechime consistentă de peste 50 de ani, fiind tratată mai peste tot (în reviste științifice și lucrări de doctorat) ca “problemă combinatorială de optimizare” (v. de exemplu: Pillay, N. (2014).A Survey of School Timetabling Research.Annals of OperationsResearch, 218(1), 261-293).
Dar putem vedea STP și așa (ne-academic): se dă un set de date, conținând toate lecțiile prof|cls desprinse din planul de încadrare al școlii; acest set inițial trebuie completat cu o coloană zi pe care să se înscrie ziua din săptămână în care este repartizată fiecare lecție, astfel încât repartiția pe zile rezultată să fie echilibrată pe zile, pe profesori și pe clase (ceea ce constituie sarcina pachetului days2lessons). Apoi, fiecare dintre subseturile de lecții repartizate în câte o aceeași zi, trebuie completat cu o coloană ora având ca valori acele ore 1:7 ale zilei, în care am putea aloca fiecare dintre lecțiile respective astfel încât oricare două lecții să nu se suprapună într-o aceeași oră a zilei (ceea ce a constituit subiectul pachetului hours2lessons).
Ar rezulta astfel câte un orar, pentru fiecare zi în parte; problema care se mai pune constă în ajustarea orarelor zilnice, astfel încât numărul total de ferestre să devină cât se poate de mic (și aceasta constituie tema pachetului refitgaps).
Un orar săptămânal ar fi și “bun”, dacă: este echilibrat (în fiecare zi, avem cam același număr de lecții, iar lecțiile fiecărui profesor, ca și cele ale fiecărei clase, ca și cele pe un același obiect la fiecare clasă, sunt repartizate uniform, sau măcar "cvasi-uniform", pe zile); iar numărul total de ferestre este unul rezonabil, cât se poate de mic.
Pentru a constitui setul inițial de date, nu avem nevoie de nume și prenume, nici de denumirile disciplinelor școlare; cel mai convenabil este să abreviem disciplinele pe câte două litere și să desemnăm profesorii concatenând numele abreviat al disciplinei principale pe care este încadrat fiecare, cu un număr de ordine între cei de pe o aceeași disciplină. De exemplu, Bi1, Bi2 și Bi3 ar reprezenta cei trei profesori de “Biologie”, iar Gr3Fr2 ar fi un profesor fictiv (reprezentând un cuplaj) pentru lecțiile “pe grupe” ale unei clase (în ora respectivă, Fr2 face “Franceză” cu o grupă, iar Gr3 face “Germană” cu cealaltă grupă).
În general, orarele întâlnite pe site-urile școlilor sunt dezechilibrate în privința numărului de ore pe zi (ținând cont mai degrabă de interese, decât de principii): într-o zi se fac 180 de lecții, vinerea se fac doar 150; o clasă are 7 ore într-o zi și numai 4 într-o alta, un profesor are 2 ore într-o zi și 7 într-o alta; deasemenea, la unele clase cele 3 sau 4 ore pe un obiect de învățământ se expediază în două zile; iar unele clase au ”liber” prima oră a zilei, sau încheie ziua cu câte o singură grupă.
Noi am urmărit consecvent principiul care pare a fi cel mai favorabil pentru procesul de învățare: distribuim lecțiile în mod echilibrat pe zile, clase și profesori; la fiecare clasă, lecțiile pe un același obiect sunt repartizate câte una pe zi; toate clasele își încep programul zilnic la o aceeași oră a zilei; în cazul cuplajelor, grupele sunt prezente simultan. În plus, explicităm de la bun început, cuplajele și tuplajele; pentru tuplaje, fiind în număr mic față de totalul lecțiilor, ne putem gândi din start la o repartizare pe zile separată față de lecțiile obișnuite (dar nu neapărat fixată, ci ajustabilă în mod dinamic, pentru a o corela cu repartizarea lecțiilor obișnuite).
Setul dat al tuturor lecțiilor (obișnuite); setul tuplajelor
Fișierul Lessons.RDS (în format specific "R Data Serialization") conține toate lecțiile "obișnuite" prof|cls de desfășurat în săptămâna curentă — unde prof este în general un profesor propriu-zis, iar în unele cazuri un "profesor fictiv" (reprezentând un cuplaj de doi profesori pe grupe ale unei aceleiași clase), dar astfel încât lecția prof|cls respectivă nu face parte din vreun tuplaj (adică este o "lecție obișnuită"). De exemplu, pentru unul dintre profesorii de "Română" sunt înregistrate aceste 10 lecții:
prof cls prof cls prof cls
1 Ro8 10D 4 Ro8 11A 7 Ro8 12A
2 Ro8 10D 5 Ro8 11A 8 Ro8 12A
3 Ro8 10D 6 Ro8 11A 9 Ro8 12A
10 Ro8 12A
Probabil că în planul general de încadrare, pentru Ro8 s-a specificat numărul de ore 3 la clasele 10D, 11A și 12A și s-a adăugat o oră (de "Dirigenție", sau poate pe o disciplină secundară) la clasa 12A; dar pentru orar trebuie avută în vedere fiecare lecție, încât în setul tuturor lecțiilor trebuie să avem de 3 ori lecția Ro8|10D, de 3 ori lecția Ro8|11A, și de 4 ori lecția Ro8|12A (trebuind ca fiecare dintre aceste 10 lecții să fie alocată pe câte o zi și oră, încât Ro8 să le poată face pe toate, pe parcursul săptămânii).
Pe disciplinele "Muzică" și "Desen" avem 4 profesori, pe câte una sau două ore/săptămână, iar la 5 clase aceștia lucrează câte doi (în câte o oră):
prof cls prof cls prof cls prof cls prof cls
1 Ds1Mz1 10B 12 Ds1 5C 23 Mz1 6C 34 Mz1 7C 45 Mz1 8C
2 Ds1Mz1 10E 13 Mz1 5C 24 Ds1 6D 35 Ds1 7D 46 Ds1 8D
3 Ds1Mz1 11E 14 Ds1 5D 25 Mz1 6D 36 Mz1 7D 47 Mz1 8D
4 Mz1 11E 15 Mz1 5D 26 Mz1 6D 37 Ds1 7E 48 Ds1 8E
5 Ds1Mz2 12E 16 Ds2 5E 27 Ds1 6E 38 Mz2 7E 49 Mz1 8E
6 Mz2 12E 17 Mz1 5E 28 Mz1 6E 39 Ds1 8A 50 Ds1Mz1 9A
7 Mz2 12E 18 Ds2 6A 29 Ds1 7A 40 Mz1 8A 51 Ds2 9E
8 Ds2 5A 19 Mz2 6A 30 Mz1 7A 41 Ds1 8B 52 Mz1 9E
9 Mz2 5A 20 Ds1 6B 31 Ds1 7B 42 Mz2 8B
10 Ds2 5B 21 Mz2 6B 32 Mz1 7B 43 Ds1 8C
11 Mz1 5B 22 Ds1 6C 33 Ds1 7C 44 Ds1 8C
De pe liniile 5-7 vedem că Mz2 are de făcut 3 lecții la 12E, dintre care una este în cuplaj cu Ds1; probabil că una dintre celelalte două este pe vreo disciplină secundară (de exemplu "OMuz", cum putem citi pe fișierul PDF de pe care extrăsesem datele).
Dar știm că normativele curente alocă (în principiu) "o oră la două săptămâni" pentru "Desen" și "Muzică", la toate clasele a 9-a și a 10-a — ori pe cele 52 de linii de date redate mai sus nu apar toate aceste clase… Însă pe clasele a 9-a și a 10-a omise în lista de mai sus avem nu cuplaje obișnuite, ci câte un tuplaj — iar tuplajele sunt înregistrate separat, în fișierul Tuplaje.RDS:
prof cls prof cls
1 Ds1 Mz1 9B 10A 11 Fr1 Gm2 11D 11E
2 Ds1 Mz2 10C 9C 12 Fr1 Gm2 9D 9E
3 Ds2 Mz2 10D 9D 13 Fr1 Gm2 9D 9E
4 Ds2 Mz2 10D 9D 14 Fr2 Gm1 9B 9C
5 Fr1 Fr2 Gm1 10C 10D 10E 15 Fr2 Gm1 9B 9C
6 Fr1 Fr2 Gm1 10C 10D 10E 16 Fr2 Gm2 10A 10B
7 Fr1 Fr2 Gm2 11C 11D 11E 17 Fr2 Gm2 10A 10B
8 Fr1 Fr2 Gm2 11C 11D 11E 18 Fr2 Gm2 12D 12E
9 Fr1 Gm1 12B 12C 19 Fr2 Gm2 12D 12E
10 Fr1 Gm1 12B 12C 20 Fr2 Gm2 12D 12E
Un "tuplaj" (Prof1 Prof2 | Cls1 Cls2) are următoarea interpretare tacită: într-o aceeași zi și oră, Prof1 și Prof2 intră respectiv la clasele Cls1 și Cls2 în săptămânile de rang impar și intră respectiv la clasele Cls2 și Cls1 în săptămânile de rang par (ceea ce echivalează, dar fără a fi "același lucru", cu două cuplaje: Prof1Prof2 Cls1 și Prof1Prof2 Cls2). Dar aceasta nu înseamnă că ar trebui să avem două orare (după paritatea săptămânii curente) — fiindcă putem gândi mai general, astfel: elevii claselor dintr-un același tuplaj sunt redistribuiți ad-hoc (după criterii stabilite inițial de către profesorii implicați în acel tuplaj) în "noi" clase, la fel denumite ca și cele inițiale, și profesorii respectivi intră conform orarului la clasele respective.
De exemplu, tuplajul de pe linia 1 (Ds1 Mz1 | 9B 10A) spune că lecțiile Ds1|9B și Mz1|10A se desfășoară simultan (într-o aceeași zi și oră), dar cei doi profesori trebuie să aibă grijă să redistribuie săptămânal elevii celor două clase, încât în săptămânile pare "9B" să conțină elevii clasei 10A, iar "10A" pe cei din 9B.
Iar pentru tuplajul din linia 5 (și analog pentru liniile 6-8), elevii reuniți din clasele 10C, 10D și 10E sunt redistribuiți în trei noi clase "10C", "10D" și "10E", la care vor intra într-o aceeași zi și oră, respectiv cei trei profesori; faptul că liniile 5 și 6 sunt identice spune că trebuie să avem două zile în care lecțiile Fr1|10C, Fr2|10D și Gm1|10E să cadă în câte o aceeași oră a zilei curente.
Repartizarea lecțiilor pe zile
days2lessons::mount_days() produce la fiecare nouă execuție câte o repartizare pe zile, cvasi-omogenă, a tuturor lecțiilor; preferăm să o folosim cam așa:
library(tidyverse) library(days2lessons) # versiunea 0.1.2 (însă nu-i ultima versiune...) show_time <- function(NL = " ") cat(strftime(Sys.time(), format="%H:%M:%S"), NL) LS <- readRDS("Lessons.RDS") # 1183 lecții prof|cls din afara tuplajelor TUP <- readRDS("Tuplaje.RDS") # 44 lecții tuplate (în 20 tuplaje) show_time(" ") # timpul inițial repeat { DZ <- mount_days(LS, TUP) # cu valoarea implicită Dfh=2 show_time(" ") # timpul curent doz <- addmargins(table(DZ[c("cls","zl")]))["Sum", 1:5] %>% as.vector() # distribuția pe zile a totalului lecțiilor print(doz) if(diff(range(doz)) < 4) break }
Se repetă mount_days() până ce distribuția pe zile rezultată DZ are proprietatea că pentru numărul total de lecții, diferența între zile a numărului de ore/zi este cel mult 3; iar de data aceasta am avut noroc, fiindcă în momentul respectiv au fost suficiente numai două repetări (repetând a doua zi, au fost necesare vreo 15 repetări):
> source("cni4.R") # lansează (din consolă) programul redat mai sus # 10:45:42 10:46:20 [1] 242 246 243 250 246 # 10:46:28 [1] 247 245 245 244 246 > saveRDS(DZ, "DZ-1.RDS")
Distribuția pe zile rezultată (salvată în fișierul "DZ-1.RDS") conține 1227 lecții (1183 lecții obișnuite plus 44 lecții tuplate) prof|cls|zl (pe 70 de profesori și 40 de clase):
> str(DZ) 'data.frame': 1227 obs. of 3 variables: $ prof: Ord.factor w/ 72 levels "Bi1"<"Bi2"<"Bi3"<..: 65 65 5 5 21 ... $ cls : chr "10A" "10A" "10A" "10A" ... $ zl : Factor w/ 5 levels "Lu","Ma","Mi",..: 1 2 5 3 4 1 2 5 3 4 ...
Iar mount_days() a asigurat pentru DZ următoarele proprietăți: pentru fiecare profesor, distribuția pe zile a numărului de ore ale sale este cvasi-uniformă (cu diferență de cel mult două ore de la o zi la alta); fiindcă ne-am bazat pe valoarea implicită 2 a parametrului Dfh, pentru fiecare clasă distribuția pe zile a numărului total de ore ale sale este deasemenea, cvasi-uniformă (dacă apelam cu Dfh=1, puteam obține eventual — dar în cazul de față, într-un timp așa de mare încât mai bine renunțăm — distribuții uniforme pentru orele claselor).
Sunt acceptabile distribuțiile cvasi-uniforme (și nu neapărat uniforme), pentru orele profesorilor; dar și dacă n-am fi prea pretențioși, tot nu putem fi mulțumiți:
> table(DZ[c("cls", "zl")]) # distribuția numărului de ore/zi la clase zl cls Lu Ma Mi Jo Vi 10A 7 7 6 5 5 # distribuție cvasi-uniformă 10B 6 6 7 5 6 10C 7 6 6 5 6 10D 7 6 7 7 6 # distribuție uniformă 10E 6 7 7 6 5 11A 6 6 6 6 6 # distribuție uniformă 11B 6 6 6 6 6 # ... 7B 6 6 7 8 6 # distribuție cvasi-uniformă 7C 7 7 6 6 6 # distribuție uniformă 7D 7 6 6 6 7 # ... 9D 6 8 6 7 6 # distribuție cvasi-uniformă 9E 7 7 5 6 6
Pentru clase ar fi de dorit (dacă nu chiar obligatoriu) să avem distribuții uniforme ale numărului de ore/zi — ori vedem că în DZ multe clase au distribuții cvasi-uniforme și mai grav, există clase (7B și 9D) care ajung în câte o zi la 8 ore/zi.
Prin urmare este necesar să modificăm repartiția DZ și putem folosi pentru aceasta funcțiile interactive din pachetul recastlessons — în principal, funcția cls_quasihom() care ne listează distribuțiile numărului de lecții ale claselor rămase cvasi-omogene în cadrul setului curent DZ, funcția prof_2days() care ne listează distribuțiile profesorilor între care se poate schimba ziua alocată unei clase comune (păstrând sau chiar îmbunătățind caracterul uniform al distribuțiilor zilnice ale celor doi profesori ale căror lecții am ales să le interschimbăm dintr-o zi în alta) și funcția change_day() care modifică DZ, schimbând ziua alocată anterior unei lecții.
Modificând iterativ DZ (până ce cls_quasihom() returnează NULL), am obținut în fișierul "DZ-2.RDS" o distribuție pe zile care în plus față de "DZ-1.RDS", are proprietatea că fiecare clasă are o distribuție uniformă a numărului de ore ale ei, iar totalul lecțiilor are deasemenea, distribuție unifomă pe zile:
> DZ <- readRDS("DZ-2.RDS") > recastlessons::cls_quasihom(DZ) NULL # deci toate clasele au distribuții uniforme de ore/zi > table(DZ$zl) Lu Ma Mi Jo Vi 245 246 245 246 245 # în fiecare zi, 245 sau 246 lecții (distribuție uniformă)
Precizăm în treacăt că funcția prof_bad_dis() listează profesorii din afara cuplajelor, cu distribuții curente doar cvasi-omogene de ore/zi și dacă vrem (dar numai de dragul perfecțiunii, dacă o fi cazul) putem să ne ocupăm iterativ și de uniformizarea completă a acestora…
Am vrut desigur să vedem și cum au fost repartizate pe zile în DZ, lecțiile tuplate; însă pentru funcția invocată în acest scop, am primit atenționarea că ea… nu există — moment în care ne-am dat seama că încărcasem o versiune de pachet anterioară celeia în care adăugasem și funcția respectivă; am reinstalat pachetul (ceea ce aduce de la CRAN ultima versiune a sa) și acum putem folosi funcția days2tupl():
> remove.packages("days2lessons") # nu avea funcția days2tupl()... > install.packages("days2lessons") # actualizează pachetul (0.1.3) > days2tupl(DZ, TUP) # repartiția pe zile a tuplajelor prof cls zl 1 Fr1 Fr2 Gm1 10C 10D 10E Lu Mi 2 Fr1 Fr2 Gm2 11C 11D 11E Vi Jo 3 Fr1 Gm2 9D 9E Ma Lu 4 Fr1 Gm2 11D 11E Mi 5 Fr2 Gm1 9B 9C Vi Jo 6 Fr1 Gm1 12B 12C Ma Lu 7 Fr2 Gm2 12D 12E Mi Vi Jo 8 Fr2 Gm2 10A 10B Ma Lu 9 Ds1 Mz1 9B 10A Mi 10 Ds1 Mz2 10C 9C Vi 11 Ds2 Mz2 10D 9D Jo Ma
Subliniem că mount_days() montează zilele pe lecțiile tuplate în mod dinamic, repetând cumva până ce distribuțiile profesorilor angajați în tuplaje (socotind și lecțiile acestora din afara tuplajelor) devin toate, omogene sau cvasi-omogene.
Desigur, prin DZ %>% filter(grepl("Fr|Gm", prof) == TRUE)) putem vizualiza (și confrunta cu tabelul de mai sus) repartiția pe zile a tuturor lecțiilor (tuplate sau nu) de "Franceză" sau "Germană". Pentru un exemplu mai scurt (față de cazul "Fr|Gm"), redăm aici repartizarea pe zile rezultată în DZ pentru lecțiilor unuia de "Matematică":
> DZ %>% filter(prof == "Mt1") %>% arrange(zl) prof cls zl prof cls zl prof cls zl prof cls zl prof cls zl 1 Mt1 10B Lu 5 Mt1 5C Ma 9 Mt1 10B Mi 14 Mt1 10B Jo 19 Mt1 10B Vi 2 Mt1 5C Lu 6 Mt1 7B Ma 10 Mt1 5C Mi 15 Mt1 5C Jo 20 Mt1 5C Vi 3 Mt1 7B Lu 7 Mt1 7E Ma 11 Mt1 5C Mi 16 Mt1 7B Jo 21 Mt1 7E Vi 4 Mt1 7E Lu 8 Mt1 9B Ma 12 Mt1 7B Mi 17 Mt1 7E Jo 22 Mt1 9B Vi 13 Mt1 9B Mi 18 Mt1 9B Jo
Pentru cele 22 de lecții ale lui Mt1, în DZ a rezultat o distribuție uniformă a numărului de ore pe zi, anume (4 4 5 5 4), iar lecțiile sale la o aceeași clasă apar câte una pe zi.
Avem și situații cam nefericite (dat fiind că nu ne-am ocupat și de omogenizarea interactivă a distribuțiilor individuale), de exemplu:
prof cls zl prof cls zl prof cls zl prof cls zl prof cls zl 1 Ro8 10D Lu 4 Ro8 11A Ma 5 Ro8 10D Mi 7 Ro8 12A Jo 8 Ro8 10D Vi 2 Ro8 11A Lu 6 Ro8 12A Mi 9 Ro8 11A Vi 3 Ro8 12A Lu 10 Ro8 12A Vi
Cele 10 ore ale lui Ro8 sunt distribuite cvasi-omogen, (3 1 2 1 3), dar ceea ce cu siguranță deranjează este faptul că în două zile ar veni la școală pentru câte o singură oră; având ore puține, s-ar cuveni să-i condensăm distribuția — de exemplu, mutând lecția sa la clasa 11A din ziua Ma, în ziua Jo (și pentru a nu strica echilibrele existente în DZ, mutând invers, o lecție la 11A din ziua Jo, în ziua Ma, la un profesor, dacă există, care are ore la clasa respectivă în ziua Jo dar nu și în ziua Ma).
În fine — având o distribuție pe zile precum DZ, să zicem acceptabilă, urmează să ne ocupăm de alocarea pe orele 1:7 a lecțiilor repartizate în câte o aceeași zi. Dar pentru aceasta sunt necesare anumite pregătiri; mai întâi, funcția existentă less2days() produce o listă care asociază fiecărei zile subsetul lecțiilor prof|cls care în DZ au fost repartizate în acea zi:
> lDZ <- less2days(DZ) > str(lDZ[["Lu"]]) # structura subsetului de lecții repartizate în ziua Lu 'data.frame': 245 obs. of 2 variables: $ prof: Ord.factor w/ 72 levels "Bi1"<"Bi2"<"Bi3"<..: 65 21 31 47 60 7 3 ... $ cls : chr "10A" "10A" "10A" "10A" ... > saveRDS(lDZ, "day_lessons.RDS")
De observat că am păstrat prof ca "factor" (cum era în DZ); dar mai târziu (trecând la montarea orelor), va trebui să-l convertim la "character"… Un alt "defect" (dar minor) putem observa listând câteva linii de date:
> lDZ[["Lu"]] [1:5, ] prof cls 1 Sp3 10A 6 Fi2 10A 11 In1 10A 16 Mt6 10A 21 Ro7 10A
Anume, numele de linie nu sunt cele obișnuite (1, 2, 3, ...), ci referă liniile extrase din DZ (ceea ce este în general o legătură importantă, dar care aici nu mai prezintă interes); de exemplu pe linia 16 din DZ găsim lecția marcată mai sus cu "16":
> DZ[16, ]
prof cls zl
16 Mt6 10A Lu
Preferăm de obicei, să avem ca "nume de linie" indecșii uzuali (numărul de ordine în cadrul setului respectiv, al liniei curente):
> Zile <- levels(DZ$zl) > for(zi in Zile) rownames(lDZ[[zi]]) <- NULL > lDZ[["Lu"]] [1:5, ] prof cls 1 Sp3 10A 2 Fi2 10A 3 In1 10A 4 Mt6 10A 5 Ro7 10A > saveRDS(lDZ, "day_lessons.RDS")
Apoi, trebuie să pregătim deasemenea, o listă care asociază fiecărei zile setul tuplajelor repartizate prin DZ în acea zi; probabil că vom updata oficial (la CRAN) funcția days2tupl(), pentru a produce această listă (în loc de tabelul TUP redat mai sus), dar până atunci producem ad-hoc lista respectivă:
TP <- days2tupl(DZ, TUP) # selectează din DZ tuplajele (prof ...|cls ...|zl ... ) lTP <- lapply(Zile, function(Z) { wh <- which(grepl(Z, TP$zl) == TRUE) # indecșii liniilor cu Z în câmpul zl data.frame(prof = TP$prof[wh], cls = TP$cls[wh]) }) %>% setNames(Zile) > lTP[["Lu"]] # (exemplificare) Lecțiile tuplate repartizate în ziua Lu prof cls 1 Fr1 Fr2 Gm1 10C 10D 10E 2 Fr1 Gm2 9D 9E 3 Fr1 Gm1 12B 12C 4 Fr2 Gm2 10A 10B > saveRDS(lTP, "day_tupl.RDS")
În sfârșit (cu aceasta încheiem pregătirile anunțate mai sus), prin funcția următoare (de adăugat cândva, dacă nu îndreptăm între timp lucrurile, în pachetul day2lessons), pentru fiecare zi, eliminăm din subsetul lecțiilor acesteia, lecțiile tuplate existente pe ziua respectivă:
skip_tupl <- function(lDZ) { lTP <- readRDS("day_tupl.RDS") for(zi in names(lDZ)) { TP <- lTP[[zi]] WH <- vector() # indecșii liniilor de eliminat din lDZ[[zi]] for(i in 1:nrow(TP)) { Pr <- strsplit(TP[i, 1], " ")[[1]] # profesorii și Cl <- strsplit(TP[i, 2], " ")[[1]] # clasele din tuplajul curent wh <- vector("integer", length(Pr)) for(k in 1:length(Pr)) wh[k] <- which(with(lDZ[[zi]], prof == Pr[k] & cls == Cl[k] ) == TRUE)[1] WH <- c(WH, wh) } lDZ[[zi]] <- lDZ[[zi]][-WH, ] # elimină lecțiile tuplajelor zilei lDZ[[zi]] <- lDZ[[zi]] %>% mutate(prof = as.character(prof)) } lDZ # lista pe zile a lecțiilor din afara tuplajelor } > lDZ1 <- skip_tupl(lDZ) > saveRDS(lDZ1, "day_less_tupl.RDS")
A trebuit să luăm seama la acest aspect: se poate întâmpla ca la una dintre clasele unui tuplaj, unul sau altul dintre profesorii implicați să aibă și o lecție obișnuită, pe lângă cea din tuplajul respectiv; am avut grijă mai sus să selectăm prin which()[1] numai prima lecție întâlnită la clasa respectivă în subsetul lecțiilor zilei curente (altfel ar fi fost eliminate ambele lecții, adică și aceea din afara tuplajului).
Să observăm însă, că n-am luat seama și la acest aspect, mai elementar: dacă pe o linie din setul tuplajelor avem să zicem trei profesori pe două clase, atunci skip_tupl() eșuează (în mod normal, referirea Cl[3] va produce o eroare de execuție, fiindcă vectorul CL are dimensiunea 2)…
Dar oare trebuie să ținem seama în program, de toate aspectele "periculoase", care pot compromite execuția programului? Nicidecum (în pofida imperativelor "programării defensive"); dacă se cere o valoare numerică, iar omul introduce "două sute", sau și mai frumos numele său — să-i fie de bine, nu ne stricăm ziua ca să prevedem o secvență banală care să-l atenționeze și să ceară din nou un număr și nu altceva! Onest este să vizezi pe cel care știe ce face.
În cazul de față am ignorat în mod deliberat, "pericolul" menționat. Păi să ne gândim; un "tuplaj" de 2 profesori pe 3 clase nu are sens, fiindcă unuia i-ar reveni prea mulți elevi față de normativele curente; deci numărul de profesori implicați într-un tuplaj trebuie să fie cel puțin egal cu numărul de clase implicate; dar ce ar însemna un tuplaj ca "(P1 P2 P3) | (C1 C2)"? În mod firesc, doi dintre cei trei profesori ar constitui un cuplaj pe o parte rezonabilă (cu dimensiunea unei clase de elevi) din reuniunea elevilor celor două clase, iar al treilea ar intra la partea rămasă; dar care doi să constituie acel cuplaj? Dacă această alegere a fost lăsată programului… atunci cuplajul respectiv va fi "P1P2|C1", adică tuplajul constituit intern va fi "(P1P2 P3) | (C1 C2)" (de doi profesori, înființând tacit unul fictiv, pe două clase); dar utilizatorul ar trebui să știe mai bine situația și atunci ar fi putut introduce din start, cuplajul corect de exemplu "(P1P3 P2) | (C1 C2)", în loc de a se baza pe program. Din păcate, nu am gândit de la bun început așa, încât a rămas cerința ca lecțiile tuplate să nu fie incluse în setul lecțiilor "obișnuite" — încât analizând setul dat de tuplaje, mount_hours() să înființeze dacă este cazul, un profesor fictiv (sau mai mulți) și abia apoi, să adauge lecțiile tuplate rezultate astfel, înapoi în setul tuturor lecțiilor; ne promitem să corijăm cândva acest aspect hilar, cerând utilizatorului să formuleze corect setul de tuplaje (fiecare tuplaj să aibă același număr de profesori ca și de clase).
Mai departe, pentru a monta orele 1:7 pe lecțiile fiecărei zile, vom avea nevoie de fișierul "day_less_tupl.RDS" care conține pe zile lecțiile ne-tuplate (și am avut grijă mai sus, să transformăm $prof din factor în character) și de fișierul "day_tupl.RDS" care conține tuplajele de pe fiecare zi.
Montarea orelor 1:7 pe lecțiile dintr-o aceeași zi
Pentru a începe să facem unele simplificări (deocamdată, asupra lucrului cu tuplaje), am eliminat pachetul hours2lessons și am înființat (local) o nouă versiune a acestuia.
Pentru a obține orarele zilnice procedăm cam așa:
library(tidyverse) library(hours2lessons) # aici, versiunea locală _0.2 lDZ <- readRDS("day_less_tupl.RDS") # seturile zilnice de lecții ne-tuplate lTP <- readRDS("day_tupl.RDS") # tuplajele, pe fiecare zi W <- list() # pregătește lista orarelor zilnice show_time() # 11:04:58 for(zi in names(lDZ)) W[[zi]] <- mount_hours(lDZ[[zi]], lTP[[zi]]) show_time("\n") # 11:05:49 (durată: sub un minut) saveRDS(W, "orar-1.RDS")
Nu-i cazul deocamdată, să redăm aici vreunul dintre orarele zilnice rezultate în lista W; dar poate fi interesant să verificăm orarul lecțiilor tuplate, folosind de exemplu funcția următoare (al cărei mecanism l-am ilustrat pe liniile de comentariu):
orar_tupled <- function(zi) { Pt <- lTP[[zi]] %>% pull(prof) %>% # "P1 P2 P3" "P1 P4" lapply(., strsplit, " ") %>% # ["P1" "P2" "P3"], ["P1" "P4"] unlist() %>% unique() %>% # "P1" "P2" "P3" "P4" paste0(collapse = "|") # "P1|P2|P3|P4" W[[zi]] %>% filter(grepl(Pt, prof)) %>% # orarul fiecăruia dintre cei 4 long2matrix() %>% print(quote = FALSE) # sub formă de "matrice-orar" return(invisible()) }
În coloana prof din setul tuplajelor zilei, avem câte un "șir de caractere" care conține codurile profesorilor din tuplajul respectiv, separate între ele prin câte un spațiu; prin pull() am extras șirurile respective, apoi am aplicat fiecăruia strsplit(), obținând câte un vector care are drept componente codurile de profesor din șirul respectiv; apoi, prin unlist() și unique() a rezultat un vector care conține fără duplicate, codurile profesorilor implicați în tuplajele respective; prin paste0() am formulat apoi un "șir de căutare" în formatul tipic acceptat de grepl(), pentru ca apoi să extragem (prin filter()) din orarul zilei, liniile pe care valoarea din câmpul prof "acoperă" măcar unul dintre codurile de profesor aflate în "șirul de căutare" (am explicat cam minuțios ce am făcut în orar_tupled(), fiindcă anterior, în situații asemănătoare cu tuplajele de aici, am procedat altfel, parcă mai complicat…).
De exemplu, pentru ziua Lu avem:
> orar_tupled("Lu") 1 2 3 4 5 6 7 Fr2 - - 10D - 10A 7B 8A # fereastră în ora 4 Gm1 - 5C 10E 5B 12C - 7C # fereastră în ora 6 Fr1 9D 6B 10C 7A 12B - - Gm2 9E - 7D 7E 10B 6D - # fereastră în ora 2
și rezultă această completare cu o coloană "ora", a setului tuplajelor de pe ziua Lu (completare pe care mount_hours() o speculează dinamic, căutând una care satisface condițiile de ne-suprapunere și cvasi-omogenitate):
prof cls ora
1 Fr1 Fr2 Gm1 10C 10D 10E 3
2 Fr1 Gm2 9D 9E 1
3 Fr1 Gm1 12B 12C 5
4 Fr2 Gm2 10A 10B 5
Să observăm că în orarul rezultat pe Lu, cei patru profesori implicați în tuplaje au căpătat în total, 3 ferestre…
Subliniem că repetând execuția programului de mai sus care ne-a condus la "orar-1.RDS" vom obține un al doilea orar (apoi… un al treilea ș.a.m.d.), cu altă alocare pe ore a lecțiilor.
Reducerea numărului ferestrelor apărute pe orarele zilnice
Orarele zilnice rezultate mai sus sunt în "format lung", cu câte 245 sau 246 de linii (câte lecții sunt pe fiecare zi) prof|cls|ora; în vederea folosirii pachetului refitgaps, trebuie să aducem orarele respective la forma de "matrice-orar" (prin funcția long2matrix() din pachetul hours2lessons), în care codurile profesorilor sunt "nume de linie" și pe fiecare linie avem clasele la care intră profesorul respectiv oră de oră (sau "-" dacă este liber în acea oră).
Calculul numărului total de ferestre este complicat: dacă profesorul este implicat în cuplaje, atunci trebuie să te uiți nu numai pe linia corespunzătoare lui în matricea-orar, dar și pe liniile profesorilor fictivi constituiți pentru cuplaje. De aceea, mount_hours() se îngrijește minimal de ferestre (încât timpul de execuție este așa de mic cum am văzut mai sus), asigurând doar că fiecare profesor care nu intră în vreun cuplaj, nu va căpăta în orarul produs pentru ziua curentă, mai mult de două ferestre; ca urmare, pe orarele zilnice obținute există foarte multe ferestre.
Pachetul refitgaps exportă funcția have_gaps() care listează liniile cu ferestre din matricea-orar indicată; ca aplicație (dar ne-exportată, în versiunea de pe CRAN a pachetului) avem funcția gaps_count() care determină numărul de ferestre. Dacă în MO vom fi obținut matricele-orar corespunzătoare orarelor zilnice rezultate mai sus, putem constata numărul de ferestre pe fiecare zi prin:
> sapply(MO, gaps_count) Lu Ma Mi Jo Vi 64 64 65 65 64
Se vede că numărul de ferestre pe fiecare zi este uriaș, peste un sfert din totalul lecțiilor zilei (faptul că ne-a rezultat o distribuție uniformă, de 64 sau 65 ferestre, este totuși întâmplător). Proporția acceptabilă ar fi de maximum 6% din totalul lecțiilor zilei, adică ar trebui să avem cel mult 6×245/100 = 14 ferestre…
Pentru a transforma orarul zilei într-un orar echivalent dar cu număr pe cât se poate de mic de ferestre, folosim funcția recast() — cam așa:
library(tidyverse) library(hours2lessons) # pentru long2matrix() library(refitgaps) ORR <- readRDS("orar-1.RDS") # lista seturilor de orare zilnice, format lung MO <- lapply(ORR, long2matrix) # lista matricelor-orar ale zilelor Zile <- names(ORR) WW <- list() # pregătește lista noilor orare zilnice for(zi in Zile) { cat(zi, " "); show_time(" ") R <- recast(MO[[zi]]) # generează un prim orar cu mai puține ferestre cat(R[[2]], " ") # numărul de ferestre for(i in 1:4) { # repetă, reținând orarul cu cel mai puține ferestre RR <- recast(MO[[zi]]) # încă un orar cu mai puține ferestre cat(RR[[2]], " ") if(RR[[2]] < R[[2]]) R <- RR } show_time("\n") WW[[zi]] <- R # cel cu minimul de ferestre, dintre orarele generate }
Redăm aici o serie de două execuții consecutive:
> source("cni9.R") Lu 19:38:46 14 15 14 15 15 19:43:31 # durata: sub 5 minute Ma 19:43:31 12 12 11 12 11 19:48:10 Mi 19:48:10 9 9 8 7 8 19:52:38 Jo 19:52:38 13 12 12 13 11 19:57:29 Vi 19:57:29 12 11 11 12 12 20:01:34 > saveRDS(WW, "WW2.RDS") > source("cni9.R") Lu 20:03:12 14 14 13 13 15 20:07:34 Ma 20:07:34 9 11 11 12 10 20:11:43 Mi 20:11:43 9 8 8 8 8 20:15:47 Jo 20:15:47 12 12 12 15 12 20:20:06 Vi 20:20:06 13 12 11 11 12 20:24:12 > saveRDS(WW, "WW3.RDS")
De observat că un nou orar este generat în mai puțin de un minut.
Dintre orarele generate pe o aceeași zi, selectăm pe cel cu cel mai mic număr (boldat mai sus) de ferestre:
> W2 <- readRDS("WW2.RDS") > W3 <- readRDS("WW3.RDS") > W <- list() > W[["Lu"]] <- W3[["Lu"]] # 13 ferestre > W[["Ma"]] <- W3[["Ma"]] # 9 > W[["Mi"]] <- W2[["Mi"]] # 7 > W[["Jo"]] <- W2[["Jo"]] # 11 > W[["Vi"]] <- W2[["Vi"]] # 11 > sapply(names(W), function(zi) W[[zi]][[2]]) # (verificare) Lu Ma Mi Jo Vi 13 9 7 11 11 > saveRDS(W, "Orar.RDS")
În lista obținută în "Orar.RDS" avem acum orare zilnice (în câte o sublistă în care pe primul loc este matricea-orar, iar pe al doilea loc este înregistrat numărul de ferestre) cu număr cât s-a putut de mic, de ferestre — în total, 51 de ferestre (adică 4.156% față de totalul 1227 al lecțiilor).
Concluzii
Avem de updatat pachetele [1], în principal după principiul "să dăm Cezarului ce-i al Cezarului": nu mount_hours() trebuie să se îngrijească de reformularea corectă a tuplajelor (înființând artificial cuplaje, în cazul când tuplajul vizează mai mulți profesori decât clase), ci însuși utilizatorul; acesta cunoaște din start contextul orarului și este cel mai în măsură să stabilească (și corect) cuplajele necesare pentru a asigura că în fiecare tuplaj avem același număr de profesori ca și de clase.
Cu această re-asumare firească de roluri, mount_hours() nu va mai pretinde excluderea prealabilă a lecțiilor tuplate din setul tuturor lecțiilor zilei.
Ca de obicei… îmbunătățirea majoră a unui program decurge prin eliminarea unor anumite părți ale sale; dificultatea majoră constă în a-ți da seama la timp de părțile inutile (justificând inutilitatea acestora).
Precizăm că în final, în conformitate cu aspectele evidențiate mai sus, am actualizat și pe CRAN pachetul hours2lessons (versiunea 1.0.0).
Mai avem de actualizat pachetul days2lessons (în repartiția pe zile returnată de mount_days(), câmpul prof ar trebui să fie character, nu factor; iar days2tupl() ar trebui să returneze lista pe zile a tuplajelor, în loc de un data.frame); bineînțeles că, având în vedere maniera de tratare a tuplajelor la care am ajuns, nu va fi nevoie de funcția skip_tupl(), considerată mai sus.
vezi Cărţile mele (de programare)