Orarul şcolar implică 5 variabile: obiect (materiile şcolare de parcurs), profesor (cei meniţi să asigure parcurgerea materiilor), clasă (grupează câte un anumit număr de elevi ai şcolii), zi a săptămânii şi oră din zi; orarul alocă pentru fiecare profesor, câte o zi şi o oră în care acesta să intre la una sau alta dintre clasele care i-au fost repartizate, pentru a parcurge la aceste clase materia pe care este încadrat în acea şcoală.
Profesorii sunt daţi, împreună cu clasele (şi obiectele) pe care sunt încadraţi – variabilele „libere” sunt ziua şi ora, iar acestea trebuie alocate în aşa fel încât să se evite suprapunerile (doi profesori nu pot intra simultan, la o aceeaşi clasă).
În practica dintr-o şcoală concretă trebuie luate în seamă diverse constrângeri (o parte a clasei trebuie să parcurgă "Germană", cealaltă parte – "Chineză"; cutare profesor este indisponibil în anumite zile; etc.); dar aici ignorăm constrângerile, considerând că acestea pot fi lăsate în seama unei ajustări interactive ulterioare generării unui orar.
Fiind vorba de două variabile libere, vedem două etape: mai întâi distribuim orele profesorilor pe zilele de lucru (cu eventuală ajustare finală), apoi – distribuim orele fiecărei zile pe intervalele orare ale zilei (iarăşi, cu ajustare finală).
Avem nevoie deci, de două programe (câte unul pentru fiecare „etapă”); în dezvoltarea noastră de aici, aceste două programe sunt similare, angajând (cu anumite adaptări) un acelaşi „algoritm de etichetare” (care este de fapt, foarte simplu).
Sintetizăm întâi ideile principale din seria [1], privitoare la distribuţia pe zile a orelor.
Orele din planul de încadrare al unei şcoli pot fi tabelate sub forma prof/cls; de exemplu, dacă profesorul "P01" are 3 ore la clasa 12A – atunci înscriem 3 linii identice P01/12A (înregistrăm fiecare oră); dacă în şcoala respectivă se desfăşoară 1202 ore pe săptămână – atunci tabelul orelor (să-i zicem TO) va conţine 1202 linii.
Ordonăm liniile din TO după prof (alfabetic, sau mai bine – după numărul de ore).
Grupăm liniile din TO după cls; obţinem atâtea grupuri, câte clase sunt – fie K unul oarecare; numărul de linii din K este dat de numărul de ore pe săptămână ale clasei respective; în principiu, ordinea liniilor din K este indusă de ordinea liniilor din TO – deci în K orele unui aceluiaşi profesor apar pe linii consecutive.
Adăugăm în K o coloană zl pe care înscriem repetat secvenţa zilelor de lucru (primele 5 linii primesc respectiv „etichetele” 1..5, următoarele 5 linii la fel, etc.). Rezultă astfel o distribuţie pe zilele de lucru a orelor clasei K; dacă profesorul din K are nu mai mult de 5 ore pe săptămână la clasa respectivă – atunci orele sale vor fi alocate prin etichetarea din zl în zile diferite (fiindcă liniile acestor ore sunt consecutive, în K).
Desigur, continuând la fel pentru celelalte clase K – ajungem în situaţia în care unui profesor (cu ore la mai multe clase) îi sunt alocate în total prea multe ore într-o zi, faţă de alte zile (de exemplu, are 20 de ore pe săptămână, iar distribuţia individuală rezultată este (9, 3, 2, 3, 3) – departe de o distribuţie „omogenă”, cum este de dorit).
Prin urmare, dacă în procesul etichetării prin zl a orelor claselor, constatăm pentru clasa curentă K faptul că distribuţiile individuale rezultate până la momentul respectiv devin neomogene, atunci trebuie să modificăm cumva coloana zl din K – de exemplu, cum procedăm în [1]: reordonăm aleatoriu liniile din K (dar păstrând proprietatea orelor unui aceluiaşi profesor, de a fi pe linii consecutive) şi aplicăm din nou, în noua ordine a liniilor, etichetele zl.
În ultimă instanţă, dacă procesul de etichetare curent se blochează la o anumită clasă (nu găsim în timp rezonabil o etichetare zl a orelor acesteia care să menţină distribuţii individuale suficient de omogene) – atunci abandonăm etichetarea curentă şi relansăm procesul de etichetare, schimbând însă (aleatoriu) ordinea claselor K.
Modelând aceste idei prin programele R redate în seria [1], am obţinut un set de vreo 30 de distribuţii pe zilele de lucru a celor 1202 ore ale unei şcoli (cu 76 de profesori şi 41 de clase); din acest set am ales distribuţia cea mai convenabilă (are un număr mic de distribuţii individuale neomogene şi deasemenea, are un număr mic de cazuri în care un profesor cu puţine ore pe săptămână are zile cu câte o singură oră); folosind apoi aplicaţia interactivă /recast (pentru un anumit subset de ore al acestei distribuţii), am redus şi mai mult, numărul de distribuţii individuale neconvenabile – rezultând fişierul final "distr_final.RDS" (repartizare pe zile acceptabilă, a celor 1202 ore ale şcolii).
Este drept că ulterior, am sesizat că numărul total de ore pe zi este distribuit neuniform pe zile şi am folosit din nou /recast, de data aceasta nu pe un subset de ore, ci pe întreaga distribuţie din "distr_final.RDS" – rezultând distribuţia pe care vom lucra în continuare, "df1202x3.RDS" (cu totaluri echilibrate pe zile şi cu distribuţii individuale mai bune decât înainte).
Să vedem totuşi cum arată "df1202x3.RDS", lăsat de [1](v):
> Dzl <- readRDS("df1202x3.RDS") > str(Dzl) 'data.frame': 1202 obs. of 3 variables: $ prof: chr "P01" "P01" "P01" "P01" ... $ zl : chr "Vi" "Vi" "Vi" "Vi" ... $ cls : chr "10A" "10B" "10E" "8B" ...
$prof şi $zl sunt de tip "character" – dar cam peste tot în [1], erau „factori ordonaţi”, într-un "tibble". Transformăm 'Dzl' în "tibble", trecem de la "chr" la "Ordered factor" şi schimbăm ordinea coloanelor la aceea obişnuită în [1]:
Zile <- c("Lu", "Ma", "Mi", "Jo", "Vi") Dzl <- as_tibble(Dzl) %>% mutate(prof = ordered(prof), zl = factor(zl, levels = Zile, ordered=TRUE)) %>% relocate(cls, .after = prof) str(Dzl) tibble [1202 × 3] (S3: tbl_df/tbl/data.frame) $ prof: Ord.factor w/ 76 levels "P01"<"P02"<"P03"<..: 1 1 1 1 1 1 1 1 1 1 ... $ cls : chr [1:1202] "10A" "10B" "10E" "8B" ... $ zl : Ord.factor w/ 5 levels "Lu"<"Ma"<"Mi"<..: 5 5 5 5 5 1 1 1 1 1 ... saveRDS(Dzl, file="tb1202x3.RDS")
De observat că acum, valorile variabilelor $prof şi $zl sunt numere întregi (indecşii etichetelor factorilor respectivi) – ceea ce permite între altele, implicarea unor vectori „cu nume” şi anumite operaţii „pe biţi” (cum vom vedea mai jos).
Mai departe lucrăm cu distribuţia restructurată mai sus şi salvată în "tb1202x3.RDS".
În principiu, vom proceda la fel ca în prima etapă: etichetăm orele prof/cls repartizate deja într-o aceeaşi zi, cu intervale orare.
Ne limităm deocamdată, la cazul când toate orele şcolii se desfăşoară într-un singur schimb; deci „intervalele orare” ale zilei sunt 1..7. Din „etapa I” ştim că fiecare clasă are sau no/5, sau (no/5 + 1) ore pe zi, unde no este numărul de ore pe săptămână ale clasei; în cazul de faţă, la fiecare clasă, numărul de ore pe zi este cuprins între 4 şi 7.
Fie K grupul de linii din distribuţia pe ziua respectivă a orelor, corespunzător unei clase oarecare; K are ko linii (ko=4..7), reprezentând orele din acea zi ale clasei. Etichetăm liniile respective printr-o permutare oarecare a valorilor 1..ko, înscrisă pe o coloană ora anexată lui K (în locul vechii coloane zl).
Această alocare pe orele zilei a liniilor din K poate să inducă un conflict cu alocarea făcută anterior unei alte clase – în cazul când clasele au un profesor comun şi acestuia i s-a alocat o aceeaşi oră din zi, în ambele coloane ora; în acest caz, înscriem pe coloana ora a clasei curente K o altă permutare a valorilor 1..ko şi repetăm până când conflictul este eliminat (şi vom putea trece mai departe, pe rând, la celelalte clase).
Trebuie să avem grijă în prealabil, să ne punem la dispoziţie listele permutărilor de ko=4..7 elemente. Este important cum generăm aceste permutări: ordinea în care le angajăm influenţează decisiv numărul de ferestre ale profesorilor.
Este importantă deasemenea, ordinea în care abordăm clasele, pentru a monta fiecăreia coloana ora; putem proceda şi la întâmplare, obţinând cât de multe orare vrem (în ideea de a alege între acestea pe cel mai convenabil) – dar preferabil ar fi să le abordăm în ordinea descrescătoare a numărului de profesori comuni (fiindcă astfel, schimbările de permutări în ora vor decurge mai devreme). Noi am adoptat un principiu aparent mai slab: am ordonat din start, descrescător după numărul de ore pe săptămână („aparent mai slab” fiindcă de fapt, profesorii care au multe ore sunt implicit, profesori comuni multor clase).
Analog criteriului de omogenitate a distribuţiilor individuale pe zile (din „etapa I”) – am avea acum numărul de ferestre pe zi. Deocamdată nu am impus, în programul redat mai jos, vreo condiţionare asupra alegerii pentru ora a acelei permutări care (pe lângă faptul că nu intră în conflict cu vreo alocare de la o altă clasă) majorează cel mai puţin, numărul curent de ferestre pe zi; amânăm grija ferestrelor (dar vom reveni, cu siguranţă), fiindcă oricum avem de conceput şi o aplicaţie interactivă (un widget jQuery analog cu /recast) prin care să putem retuşa orarul furnizat de program.
Cum am explicat mai sus, vom avea de încercat câte o permutare a secvenţei 1:ko, în coloana ora din K; deci se cuvine să generăm (în prealabil) permutările (pentru ko=4..7) drept coloane ale unei matrice.
La CRAN găsim şi pachete care conţin funcţii de generare a permutărilor (formulate iniţial în C); de exemplu, partitions::perms(n) (care leagă codul compilat al fişierului "permutation.c") produce o matrice ale cărei coloane enumeră lexicografic permutările secvenţei 1:n. Însă pachetul respectiv vizează o arie largă de funcţii şi integrează diverse biblioteci, de care nu avem nevoie; preferăm deci să formulăm direct, o funcţie care să ne furnizeze permutările.
Folosim „descompunerea recursivă” obişnuită: 1) elimină elementul curent; 2) procesează recursiv restul elementelor; 3) pune înapoi elementul curent (unde „curent” referă pe rând, elementele secvenţei iniţiale). De exemplu, să obţinem o matrice având drept coloane permutări ale secvenţei 1:3:
> ( M <- cbind(c(2,3), c(3,2)) ) [,1] [,2] # permutările mulţimii {2, 3} („curent” = 1) [1,] 2 3 [2,] 3 2 > rbind(1, M) # adaugă înapoi 1 [,1] [,2] [1,] 1 1 [2,] 2 3 [3,] 3 2 # rezultă coloane de permutări pe 1:3
rbind(1, M) constituie întâi o matrice cu un singur rând, conţinând 1 pe atâtea coloane cât are M şi apoi, adaugă dedesubt liniile din M – unde M fusese obţinută prin cbind(), alăturând pe coloane permutările lui (1:3)[-1] (adică ale secvenţei 2:3).
Bineînţeles că putem înlănţui cele două comenzi de mai sus, cbind(1, rbind(…)) şi ajungem la această formulare concisă a întregului proces:
# permore.R (colonează lexicografic permutările orelor) cbindPerms <- function(v) { # cu v=1:n P <- NULL k <- length(v) if(k == 1) return(v) for(i in 1:k) P <- cbind(P, rbind(v[i], findPerms(v[-i]))) return(P) } # Exemplu: # > cbindPerms(1:3) # [,1] [,2] [,3] [,4] [,5] [,6] # [1,] 1 1 2 2 3 3 # [2,] 2 3 1 3 1 2 # [3,] 3 2 3 1 2 1 # listă cu permutările orelor 1:ko (ko=4..7) Pore <- lapply(4:7, function(n) cbindPerms(1:n)) saveRDS(Pore, file="lstPerm47.RDS") # > str(Pore) #List of 4 # $ : int [1:4, 1:24] 1 2 3 4 1 2 4 3 1 3 ... # $ : int [1:5, 1:120] 1 2 3 4 5 1 2 3 5 4 ... # $ : int [1:6, 1:720] 1 2 3 4 5 6 1 2 3 4 ... # $ : int [1:7, 1:5040] 1 2 3 4 5 6 7 1 2 3 ...
În final, am aplicat funcţia cbindPerms() pe 4:7 şi am salvat în "lstPerm47.RDS" lista Pore a celor patru matrici rezultate; Pore[[ko]] va accesa matricea care colonează permutările pentru ko ore (unde ko=4..7).
Am putea angaja permutările şi în altă ordine, decât cea lexicografică – însă experimentele ne-au arătat că nu am avea vreun avantaj: folosind în programul care urmează mai jos, liste de permutări "in a minimal-change order" furnizate de combinat::permn(), orarul care ne-a rezultat conţine pentru fiecare zi, cam de două ori mai multe ferestre, decât în cazul când angajam permutările în ordine lexicografică.
Programul următor are doar vreo 40 de linii, dar îl prezentăm ca de obicei, „pas cu pas”; în principal, se instituie funcţia mountHtoDay() care montează coloana ora pe liniile corespunzătoare unei aceleiaşi zile, din distribuţia pe zile a orelor şcolii; în final se aplică mountHtoDay() fiecărei zile.
Mai întâi, recuperăm din fişierele constituite anterior, distribuţia pe zile a orelor şcolii (un obiect "tibble" cu 1202 linii pe 3 variabile, dintre care $prof şi $zl sunt de tip "ordered factor") şi lista celor 4 matrici de permutări:
# mount_in_days.R (mount hours in each day) library(tidyverse) Dzl <- readRDS("tb1203.RDS") # tibble 1202, <ord>prof <chr>cls <ord>zl Pore <- readRDS("lstPerm47.RDS") # lista celor 4 matrice de permutări
Acum şablonăm „global” un obiect esenţial pentru mountHtoDay(), permiţând urmărirea pe parcurs a alocării orelor pentru fiecare profesor:
nrPr <- nlevels(Dzl$prof) Bits <- rep(0L, nrPr) names(Bits) <- levels(Dzl$prof) > str(Bits) ## inspectăm din consolă Named int [1:76] 0 0 0 0 0 0 0 0 0 0 ... - attr(*, "names")= chr [1:76] "P01" "P02" "P03" "P04" ...
Bits este un „vector cu nume”, conţinând 76 (câţi profesori avem aici) de valori întregi (cu valoarea iniţială 0). Primii 7 biţi ai întregului din Bits corespunzător profesorului curent vizat de mountHtoDay(), arată ce ore 1..7 din zi au fost deja alocate până la momentul curent, profesorului respectiv.
De exemplu, dacă Bits["P05"]=45, atunci avem 45=32+8+4+1 = 00101101 şi deducem că "P05" este deja ocupat la câte o anumită clasă, în orele 1 (bitul de rang 0 fiind 1), 3 (bitul de rang 2 fiind 1), 4 şi 6 – deci la momentul curent i se poate aloca pentru clasa curentă, fie ora a doua din zi, fie a cincea, fie a şaptea.
Funcţiile bitwAnd(), bitwOr() şi bitwShiftL() ne vor asigura operaţiile pe biţi necesare întreţinerii pe parcurs a valorilor din vectorul Bits.
De fapt însă, vom folosi Bits numai ca şablon de iniţializare, scutindu-ne de a redefini pentru fiecare zi, tabloul respectiv: la debutul funcţiei mountHtoDay() pentru ziua curentă, vom copia tabloul global Bits (în care toţi octeţii sunt zero) într-o variabilă locală bith şi în bith (nu în Bits) vom întreţine alocările făcute, clasă după clasă, pentru orele profesorilor din ziua respectivă.
După completarea orarului zilei curente, vectorul bith este important şi îl vom păstra drept nouă coloană într-un „tabel” global, pe care îl iniţializăm prin:
dfBits <- data.frame(prof = names(Bits))
După obţinerea orarelor pe fiecare zi, în dfBits rămâne o sinteză asupra distribuţiei temporale a profesorilor, uşor de folosit; de exemplu, dacă dfBits["P59", 2:6] este 88 112 112 12 0 atunci profesorul P59 are în prima zi, orele 4, 5 şi 7 (cu o fereastră în ora 6) – fiindcă 88=1011000 – şi are în a doua şi a treia zi orele a 5-a, a 6-a şi a 7-a (112=1110000), în a patra zi are ora a 3-a şi a 4-a, iar în ultima zi este liber. Folosind dfBits vom putea obţine aproape imediat, diverse statistici asupra numărului de ferestre apărute în orar.
mountHtoDay() are în contextul ei funcţia mountHtoCls(), implicând-o pentru fiecare clasă pentru a eticheta cu o permutare corespunzătoare orele profesorilor de la clasa respectivă, pentru ziua al cărei grup de linii este transmis ca argument:
## alocă profesorii pe orele zilei, pentru fiecare clasă mountHtoDay <- function(Z) { # Z referă orele prof/cls dintr-o aceeaşi zi # iniţializează pentru Z, octeţii de alocare pe orele 1..7, ai profesorilor: bith <- Bits # alocă pe orele 1..7, orele (lecţiile) unei clase mountHtoCls <- function(Q) { # 'Q' conţine liniile din Z cu o aceeaşi 'cls' mpr <- Pore[[nrow(Q)-3]] # matricea de permutări corespunzătoare clasei for(i in 1:ncol(mpr)) { po <- mpr[, i] S <- Q %>% mutate(ora = po) # etichetează cu permutarea curentă # vectorul octeţilor de ore asociaţi acestei permutări: bis <- bitwShiftL(1, S$ora - 1) # vectorul octeţilor de ore alocate deja profesorilor clasei: bhp <- bith[S$prof] # Dacă există suprapuneri (de ore) între cei doi vectori, # atunci angajează coloana următoare a matricei de permutări: if(any(bitwAnd(bhp, bis) > 0)) next j <- anyDuplicated(names(bhp)) if(j > 0) { # dacă în Z, profesorul are 2 ore la acea clasă bis[j-1] <- bis[j] <- bis[j-1] + bis[j] } # actualizează global, octeţii de alocare: bith[S$prof] <<- bitwOr(bhp, bis) return(S) } } # aplică montHtoDay() pentru fiecare clasă orar <- Z %>% map_df(., function(K) mountHtoCls(K)) dfBits <<- cbind(dfBits, bith) # salvează alocările temporale făcute pentru Z return(orar) }
Există o situaţie particulară pe care – când am conştientizat problema – am rezolvat-o ad-hoc folosind anyDuplicated(); este vorba de cazul când un profesor are la o anumită clasă, două ore într-o aceeaşi zi (ceea ce este admis prin programul de distribuire pe zile din [1], numai dacă profesorul are mai mult de 5 ore pe săptămână la acea clasă).
Încercăm să descriem cazul care ne-a atras atenţia asupra subtilităţilor apărute.
Fiindcă P32 are 6 ore pe săptămână la clasa 11E, prin programul din [1] i-au fost repartizate 2 ore la 11E într-o aceeaşi zi Z; 11E are în Z 7 ore, deci coloana $ora pentru 11E este o anumită permutare a secvenţei 1:7 – două valori dintre acestea corespund celor două ore ale lui P32, iar celelalte 5 corespund celorlalţi profesori din Z cu ore la 11E. Dar P32 are ore şi la alte clase, în Z: o oră la 11C şi una la 5A.
Fiindcă în program nu am forţat împărţirea pe clase a liniilor lui Z, preferând-o pe cea implicită (în ordine alfabetică) – orele clasei 11C au fost deja „etichetate” (nu şi cele ale clasei 5A, care urmează după 11E) şi octetul bith["P32"] reflectă ora din zi alocată lui P32 pentru clasa 11C, să zicem ora 5; după ce se face şi alocarea orelor clasei 11E, octetul bith["P32"] este actualizat, reflectând ora 5 (la 11C) şi să zicem 2 şi 3 (la 11E). Programul continuă alocarea pentru clasele următoare, ajungând şi la clasa 5A; dilema, apărută la începutul procesului de „punere la punct” a programului, consta în faptul că 5A este alocată lui P32 în ora 2 – ceea ce este greşit (nu poate intra într-o aceeaşi oră şi la 11E şi la 5A); de unde se trage, această greşală?.
În R operaţiile sunt în mod implicit, „vectorizate”, decurgând printr-o singură instrucţiune pe toate componentele unui vector de valori; de exemplu, linia din program bis <- bitwShiftL(1, S$ora - 1) deplasează spre stânga cu câte un bit toate valorile din coloana $ora (diminuate cu 1, fiindcă orele sunt 1:7 iar biţii sunt indexaţi 0:7) şi depune în bis cele 7 valori rezultate.
În R „numele” sunt deosebit de importante, fiind folosite pentru referirea liniilor şi coloanelor din diverse structuri tabelare (inclusiv, matrici), referirea elementelor listelor şi chiar pentru referirea valorilor dintr-un vector numeric oarecare. Prin linia din program bhp <- bith[S$prof], se extrag din vectorul cu nume bith cele 7 valori corespunzătoare numelor din coloana S$prof, care pentru clasa 11E conţin de două ori consecutiv "P32" (pentru cele două ore ale lui P32 la clasa 11E) şi se depun cele 7 valori (moştenind şi numele acestora) în bhp.
În final, bitwOr(bhp, bis) adună în paralel valorile din bhp şi bis, rezultând un vector cu nume de 7 valori, dintre care două cu acelaşi nume, "P32"; problema (sau „defectul” inerent) apare la copierea rezultatului în bith (prin operatorul de atribuire spre exteriorul contextului funcţiei, <<-): în bith există bineînţeles, o singură valoare cu numele "P32", încât cele două valori cu acest nume ale rezultatului din partea dreaptă a atribuirii sunt copiate succesiv sub numele "P32" existent în bith (pierzând-o deci, pe prima).
Prin urmare, pentru P32, la clasa 11E se înregistrează în bith nu 2 şi 3 cum „ziceam” mai sus, ci numai 3 (încât ulterior, ajungând la clasa 5A nu se vede în bith că ora 2 este şi ea, deja alocată).
Pentru a repara greşala, am adăugat anyDuplicated(names(bhp)) – care pentru cazul evocat, furnizează indexul primei repetări a numelui "P32" – şi am însumat cele două valori de acelaşi nume din bits. Trebuie să observăm că este o reparaţie ad-hoc, foarte simplă, dar care „nu ţine” dacă ar fi vorba de trei ore la o aceeaşi clasă (fiindcă anyDuplicated() furnizează doar indexul primei repetări); ar fi desigur de imaginat o altă soluţie (dar neapărat, simplă) – însă deocamdată nu este necesar: în distribuţia pe zile preluată din [1] ne-am asigurat că nici un profesor nu are 3 ore pe zi la o aceeaşi clasă şi în plus, nici un profesor nu are într-o aceeaşi zi, mai mult de o singură clasă la care să aibă 2 ore în ziua respectivă.
Revenind la program – rămâne să disociem din distribuţia globală pe zile, liniile corespunzătoare câte unei zile şi să aplicăm pentru ziua respectivă (după despărţirea pe clase) mountHtoDay(); bineînţeles că în final, vom salva împreună (într-o listă) cele 5 orare zilnice rezultate (şi marcăm prin numele zilelor, coloanele din dfBits):
lTMT <- vector("list") Zile <- c("Lu", "Ma", "Mi", "Jo", "Vi") for(zi in Zile) { lTMT[[zi]] <- Dzl %>% filter(zl == zi) %>% select(prof, cls) %>% arrange(prof) %>% split(.$cls) %>% mountHtoDay(.) } saveRDS(lTMT, file="tmt5.RDS") # lista orarelor zilnice names(dfBits)[2:6] <- Zile saveRDS(dfBits, file="dfBits5.RDS") # harta binară a alocării orelor
Rulând programul din consola R (prin source("mount_in_days.R")), am avut surpriza de a obţine "tmt5.RDS" (lista orarelor zilnice) şi "dfBits5.RDS" (harta binară a distribuţiei temporale a orelor profesorilor) în mai puţin de 5 minute (dar "5" din numele date fişierelor nu ţine de minute, ci mai degrabă de faptul că avem 5 orare zilnice).
dfBits5.RDS reprezintă prin câte un octet, distribuţia orelor pe parcursul fiecărei zile, pentru fiecare profesor:
btm <- readRDS("dfBits5.RDS") # harta de biţi a distribuţiei pe orele zilelor str(btm) 'data.frame': 76 obs. of 6 variables: $ prof: chr "P01" "P02" "P03" "P04" ... $ Lu : int 31 31 31 15 31 15 23 15 15 15 ... $ Ma : int 31 15 15 31 31 31 15 15 15 15 ... $ Mi : int 31 31 31 31 7 31 31 31 31 31 ... $ Jo : int 63 31 31 15 31 15 31 15 31 15 ... $ Vi : int 31 31 31 31 47 31 31 31 15 23 ...
Bitul de rang k=0..6 din octetul respectiv indică dacă profesorul trebuie să intre la o anumită clasă în a (k+1)-a oră a zilei; de exemplu, dacă "P05" are în orarul zilei primele 4 ore şi apoi, a şasea oră – atunci ultimii 6 biţi din octetul asociat sunt 101111, deci valoarea numerică a octetului este 1 + 2 + 22 + 23 + 25 = 47; bitul de rang 5 fiind '0' – şi anume, un „zerou semnificativ”, adică aflat între biţi '1' – deducem că profesorul are o „fereastră” în a 5 oră a zilei.
Masca binară a orei (k+1) a zilei este 2k (k=0..6):
msk <- c(1, 2, 4, 8, 16, 32, 64) # măştile binare ale orelor 1..7
Toţi octeţii din btm au valori mai mici decât 27=128, fiindcă într-o zi sunt maximum 7 ore. bitwAnd(octet, msk) va extinde octetul indicat la un vector de lungimea vectorului msk şi va produce ca rezultat un vector în care valoarea de rang k este fie msk[k], fie 0 – după cum bitul de rang k din octet este '1', respectiv 0. Pentru „ferestre”, ne interesează valorile 0 (zero) ale rezultatului, dar nu cele iniţiale (dacă profesorul începe de la ora a 3-a, atunci primele două valori sunt 0 – dar nu corespund unor ferestre) şi nici cele finale (dacă profesorul îşi termină orele cu a 4-a oră din zi, atunci ultimele trei valori sunt 0 – dar nu corespund unor ferestre).
Cu aceste precizări, avem următoarea funcţie pentru a obţine numărul de ferestre dintr-o distribuţie orară indicată printr-un octet:
gaps <- function(oct) { # maximum 2^7-1 = 127 (fiind maximum 7 ore) if(oct %in% c(01, 3, 7, 15, 31, 63, 127)) # biţi identici, deci 0 ferestre return(0) bH <- bitwAnd(oct, msk) # dacă oct=47: 1 2 4 8 0 32 0 H <- which(bH == 0) # 5 7 (indecşii valorilor 0) s <- 1 # va indica prima valoare nenulă din bH (indecşii încep cu 1, nu 0) d <- 7 # va indica ultima valoare nenulă din bH while(bH[s] == 0) s <- s + 1 s <- s - 1 while(bH[d] == 0) d <- d - 1 length(H[H > s & H < d]) # numărul de zerouri semnificative ("ferestre") }
Acum, lapply(btm[, 2], gaps) de exemplu (aplicând gaps() pe a doua coloană din btm), ne-ar lista numărul de ferestre din prima zi, pentru fiecare profesor – şi putem formula uşor statistica dorită, folosind map_df():
gps <- map_df(2:6, function(j) data.frame(zi=j, gap=unlist(lapply(btm[, j], gaps)))) G <- as.matrix(addmargins(table(gps[c('zi', 'gap')]))) rownames(G) <- c(Zile, "Total") colnames(G)[7] <- "Total" > G # 76 prof x 5 octeţi-distribuţie_orară = 380 valori gap zi 0 1 2 3 4 5 Sum Lu 38 16 17 5 0 0 76 Ma 42 16 11 6 1 0 76 Mi 35 20 14 6 1 0 76 Jo 40 15 13 7 1 0 76 Vi 42 18 9 6 0 1 76 Total 197 85 64 30 3 1 380
În prima zi avem 16 ferestre de câte o oră, 17 de câte două şi 5 de câte trei ore; în total, pe întreaga săptămână, avem 85 de ferestre de câte o oră, 64 de câte două ore, ş.a.m.d. Au rezultat foarte multe ferestre (cam 15% dintre cele 1202 ore) – dar nici nu am impus încă, în programul care ne-a generat orarele, vreo condiţionare legată de numărul de ferestre; dat fiind că orarele au fost produse în mai puţin de 5 minute – are sens să ne gândim la adăugarea unor condiţii suplimentare, încât să nu rezulte prea multe ferestre.
Dar şi dacă ar fi puţine ferestre, tot se vor găsi la sfârşit, anumite aspecte de „corectat”; urmează să elaborăm o aplicaţie interactivă ("widget" jQuery) prin care să se poată face uşor anumite modificări ale orarului unei zile, vizând în principal reducerea numărului de ferestre; operând concret pe o asemenea aplicaţie, ne putem da seama poate, cam cum ar trebui să completăm programul în scopul generării unui orar cu cât mai puţine ferestre.
vezi Cărţile mele (de programare)