momente şi schiţe de informatică şi matematică
To attain knowledge, write. To attain wisdom, rewrite.

Colorarea pe profesori a disciplinelor

R
2026 oct

Avem ca și în [1] sau [2], orarul lecțiilor Cls|zl|ora|obj dintr-o școală "fără profesori", constituit și acesta (exact ca în [1]) după un anumit fișier PDF "Orarul general clase" (preluat de pe un site din care lipsește PDF "Orarul general profesori"):

library(tidyverse)
CN <- readRDS("CN_long.RDS")
    > glimpse(CN)  # inspectează structura orarului
Rows: 1225 lecții
Columns: 4
$ cls <chr> "5A", "5A", "5A", "5A", "5A", "5A", "5A", "5A", "5A", "5A", "5A", …
$ zl  <ord> Lu, Lu, Lu, Lu, Lu, Lu, Ma, Ma, Ma, Ma, Ma, Mi, Mi, Mi, Mi, Mi, Jo…
$ ora <int> 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, …
$ obj <chr> "Engleza", "Mate", "Rom", "Ed.soc.", "Geo", "info-TIC", "Drg", "…

Structurat astfel (în "format lung"), setul de date CN ne permite să aflăm orice informații am dori despre lecțiile respective — exceptând desigur pe cele importante, privitoare la încadrarea profesorilor (care profesor face o lecție sau alta).
De exemplu, vedem imediat că în total sunt 1225 de lecții, iar folosind table() putem vedea imediat câte lecții se desfășoară în fiecare zi, sau câte lecții are fiecare clasă, sau fiecare disciplină; este drept că unele informații se află "mai greu" decât dacă am consulta direct tabelul PDF original — de exemplu să aflăm (și să redăm, dar în formatul normal, nu pe o linie cu 36 de celule) orarul unei clase:

orarul_clasei <- function(Cls)
    CN %>% filter(cls == Cls) %>% split(.$zl) %>%
       lapply(., function(S) {
              row <- S %>% arrange(ora) %>% pull(obj)
              c(row, rep("-", 7-length(row)))
       }) %>% as.data.frame()
> orarul_clasei("9A")
           Lu                 Ma      Mi      Jo      Vi
    1     Geo                Bio Eng-opt  Fizica    Info
    2     TIC   Germana/Franceza    Mate     Rom Eng-opt
    3    Mate               Mate     Rom    Info Engleza
    4 Engleza                Rom Istorie  Chimie  Ch-opt
    5     Rom Ed.plastica/Muzica  Chimie    Mate  Logica
    6       -             Fizica  Fizica Religie       -
    7       -            Ed.fiz.     Drg       -       -

Pe orarul redat vedem că 9A face 4 ore de "Mate", dar nu putem afla cu care dintre profesorii de "Matematică"; și doar, nu ne-ar interesa deloc numele acelui profesor… ne-ar interesa care clase fac parte din încadrarea câte unui aceluiași profesor (pe o disciplină sau alta, dar aici vom aborda doar cazul "Matematică").
9A și de exemplu 9C, fac "Mate" cu un același profesor, sau cu profesori diferiți? Bineînțeles că dacă găsim o zi și oră în care la ambele clase apare "Mate", atunci este clar că au profesori diferiți — dar altfel, poate fi vorba și de un caz și de celălalt…

Să izolăm din setul CN, lecțiile de Mate (incluzând și lecțiile pe "disciplinele" Mate7, Mate8 și altele cu prefixul "Mate", prezente pe fișierul PDF inițial):

Mt <- CN %>% filter(grepl("Mate", obj)) %>% select(-obj)
    > str(Mt)  # inspectăm din consolă
tibble [160 × 3] (S3: tbl_df/tbl/data.frame)
 $ cls: chr [1:160] "5A" "5A" "5A" "5A" ...
 $ zl : Ord.factor w/ 5 levels "Lu"<"Ma"<"Mi"<..: 1 2 3 5 1 2 3 5 1 2 ...
 $ ora: int [1:160] 2 3 1 4 1 4 2 3 3 4 ...

Deci avem 160 de lecții Mate; dacă "norma didactică" ar fi de 20 ore, atunci pentru acoperirea acestor ore ar fi necesari exact 8 profesori de "Matematică" — dar câți sunt în realitate, depinde de numărul de ore pe clasă (unele clase au 4 ore, altele 5 ore, altele doar două) și depinde acum de "Orarul general clase", adică de cum sunt deja alocate pe zile și ore lecțiile respective.
Însă putem găsi o încadrare cu profesori (doar plauzibilă), care să fie compatibilă cu orarul "pe clase" CN; o soluție (poate cam întortochiată) am dat în [2], iar acum prezentăm o soluție mai firească.

Avem de ținut seama că oricare două lecții care cad într-o aceeași zi și oră vor trebui repartizate unor doi profesori distincți.
Considerăm (prin pachetul igraph) graful G care are drept vârfuri clasele care fac Mate (că există și clase la care nu figurează "Mate") și în care două vârfuri sunt adiacente dacă lecțiile respective cad într-o aceeași zi și oră (trebuind "colorate" cu profesori diferiți):

Kls <- unique(Mt$cls)  # clasele (dintre cele 40) care fac "Mate"
Adj <- matrix(0L, nrow = length(Kls), ncol = length(Kls), byrow = TRUE, 
              dimnames = list(Kls, Kls))  # matricea de adiacență
# clasele ale căror lecții "Mate" cad în câte o aceeași zi și oră
E <- lapply( Mt %>% split(list(.$zl, .$ora)), 
             function(S) S %>% pull(cls)) %>% 
     setNames(NULL) %>% compact()
# două clase cu "Mate" într-o aceeași zi și oră sunt adiacente
for(j in 1:(length(E)-1)) {
    Q <- E[[j]]
    for(k in 1:(length(Q)-1))
        for(h in (k+1):length(Q))
            Adj[Q[k], Q[h]] <- Adj[Q[h], Q[k]] <- 1L
}
G <- igraph::graph_from_adjacency_matrix(Adj, mode="undirected")
    IGRAPH a20b26b UN-- 38 309 -- 
+ attr: name (v/c)
+ edges from a20b26b (vertex names):
 [1] 5A--5E  5A--6A  5A--7B  5A--7C  5A--8A  5A--8C  5A--8D  5A--9A  5A--10A
[10] 5A--10C 5A--11A 5A--11B 5A--11C 5A--11E 5A--12E 5B--5C  5B--5D  5B--5E 
+ ... omitted several edges

Graful G are 38 de vârfuri (deci există două clase care nu fac "Mate") și 309 muchii. Pe baza structurii de date G putem obține fel de fel de informații privitoare la clasele care au "Mate" în "Orarul general clase"; de exemplu, care sunt clasele care fac "Mate" cu un alt profesor decât cel de la clasa 9A:

> igraph::neighbors(G, "9A") %>% names()  # adiacenții în G ai vârfului "9A"
 [1] "5A"  "5B"  "5C"  "5D"  "5E"  "6B"  "7A"  "7C"  "9C"  "10A" "10C" "10E"
[13] "11B" "11C" "11E" "12B"

Cele 16 clase listate trebuie să aibă alți profesori de "Mate" decât cel de la 9A — altfel ar însemna ca acesta să intre într-un același timp, la clasa 9A și încă la o clasă dintre acestea 16 care sunt adiacente în G cu 9A.

Orice colorare a grafului G (prin care oricăror două vârfuri adiacente le corespund culori distincte) determină o repartizare pe profesori a claselor (care este în concordanță cu alocarea pe zile și ore existentă pentru lecțiile respective):

P <- igraph::greedy_vertex_coloring(G, heuristic="dsatur") %>% sort()
 5A  5D 12A 12B  7C  7D  8D  9C  5E  9B 10A 10B 11E  6D  6E  8C  9A 12E  7B  8E 
  1   1   1   1   2   2   2   2   3   3   3   3   3   4   4   4   4   4   5   5 
11B 12C  5B  6C 10E 11C  5C  6A  7E  8A  9D  6B  7A  8B  9E 10D 10C 11A 
  5   5   6   6   6   6   7   7   7   7   7   8   8   8   8   8   9   9 

Poate că această colorare nu este optimală (cu numărul minim posibil de culori), dar să vedem totuși câte ore ar reveni fiecăruia dintre cei 9 profesori; mai întâi aflăm câte ore de "Mate" are fiecare clasă:

> CNT <- table(Mt$cls) %>% sort()
10D  9D  9E 10A 10B 10C 10E 11A 11E 12E  5A  5B  5C  5D  5E  6A  6B  6C  6D  6E 
  2   2   3   4   4   4   4   4   4   4   4   4   4   4   4   4   4   4   4   4 
 7A  7E  9A  9B  9C 11B 11C 12A 12B 12C  7B  7C  7D  8A  8B  8C  8D  8E 
  4   4   4   4   4   5   5   5   5   5   5   5   5   5   5   5   5   5 

Pentru fiecare dintre cei 9 — pentru care înființăm ca nume, "Mt" sufixat cu indexul 1:9 — însumăm numărul de ore indicat în CNT pentru clasele atribuite prin colorarea P profesorului respectiv:

> sapply(1:9, function(k) CNT[names(P[P == k])] %>% sum()) %>% 
        setNames(paste0("Mt", 1:9))
    Mt1 Mt2 Mt3 Mt4 Mt5 Mt6 Mt7 Mt8 Mt9
     18  19  20  21  20  17  19  18   8

Prin urmare — fără a leza vreo "lege a drepturilor personale" — avem o încadrare cu profesori de "Mt" care este plauzibilă, dacă acceptăm o normă de circa 18 ore/săptămână (iar în unele cazuri, acceptăm "jumătăți" de normă) și care este compatibilă cu alocarea lecțiilor din setul inițial CN.

Putem adapta "orarul_clasei()" pentru a formula orarul unui profesor de "Mt":

orar_prof <- function(Color) 
    Mt %>% filter(cls %in% names(P[P == Color])) %>% 
        split(.$zl) %>%
        lapply(., function(S) {
            row <- S %>% arrange(ora) %>% pull(cls)
            c(row, rep("-", 7-length(row)))
        }) %>% as.data.frame()

Listând acum orarele celor 9 profesori "Mt", constatăm că toți își încep lecțiile de la prima oră a fiecărei zile și că niciunul nu are vreo fereastră; de exemplu:

> orar_prof(1) # Mt1      > orar_prof(9) # Mt9       > orar_prof(4) # Mt4
   Lu  Ma  Mi  Jo  Vi         Lu  Ma  Mi  Jo  Vi          Lu  Ma  Mi Jo  Vi
1 12B 12B  5A 12B 12B      1 11A 11A 11A 11A 10C       1  8C 12E 12E 6D  8C
2  5A  5A 12B  5D 12A      2 10C 10C 10C   -   -       2 12E  8C  9A 6E  6D
3  5D  5D  5D   -  5A      3   -   -   -   -   -       3  9A  9A  8C 9A  6E
4 12A 12A 12A   -   -      4   -   -   -   -   -       4  6E   -  6D  -  8C
5   -   - 12A   -   -      5   -   -   -   -   -       5  6D   -  6E  - 12E
6   -   -   -   -   -      6   -   -   -   -   -       6   -   -   -  -   -
7   -   -   -   -   -      7   -   -   -   -   -       7   -   -   -  -   -

Să mai observăm că unele clase ar putea fi mutate, păstrând poziția lecțiilor respective, de la un profesor la altul. De exemplu, clasa 5D poate fi transferată de la Mt1 (care ar rămâne astfel cu 14 ore, căpătând și 3 ferestre) la Mt9 (care ar face atunci 12 ore); dacă mai mutăm și clasa 12A, atunci Mt1 va face 9 ore (cu o fereastră, Vi ora a doua), iar Mt9 ar ajunge la 17 ore (fără ferestre).
Însă 12B de exemplu, nu poate fi mutată de la Mt1 la Mt9…

Poate fi redus numărul de profesori "Mt"? Nu, fiindcă toți cei 9 au ocupate primele două ore, în fiecare zi (rezultă indirect, că numărul cromatic al grafului G este 9).

Desigur, procedurile redate mai sus pentru "Mate" pot fi împachetate (și nici n-ar fi greu), încât să le puteam aplica și pe alte discipline existente în "Orarul general clase" — pentru a obține în final o încadrare plauzibilă de profesori pe clasele și disciplinele respective, compatibilă cu orarul "pe clase" existent.

Să observăm în final că fișierul PDF "Orarul general clase" ar putea reflecta și încadrarea profesorilor existentă în școala respectivă: se consideră un set de culori de bază pentru disciplinele principale, iar pentru profesorii de pe o aceeași disciplină principală se consideră un set de nuanțe ale culorii de bază asociate acelei discipline — urmând ca lecțiile redate în tabelul PDF respectiv să fie colorate conform nuanței de culoare asociate profesorului care face disciplina respectivă.
Dar bineînțeles că o asemenea colorare fizică a numelor disciplinelor care apar în "Orarul general clase" ar fi nu numai complicat de efectuat (iar extragerea datelor din fișierul PDF respectiv ar deveni chiar dificilă) — dar ar fi de-a dreptul prostească…

Este și simplu și firesc să se sufixeze numele disciplinelor cu un index de o cifră (rar ar fi necesare două) care să indice câte unul dintre profesorii încadrați pe disciplina respectivă; ignorând indecșii adăugați, avem disciplinele; considerând indecșii și ținând cont de prefixul acestora, avem și profesorii cărora le aparțin lecțiile respective. Astfel procedând, "Orarul general clase" ar deveni orarul școlii, conținând toate informațiile necesare unui orar (că într-un orar nu numele profesorilor, sunt importante), fără a mai fi nevoie și de PDF "Orarul general profesori" (deci fără a ne mai lovi de vreo lege a drepturilor personale; în plus… s-ar face și ceva dovadă de mult clamata "gândire critică", independentă de butoanele exterioare).

vezi Cărţile mele (de programare)

docerpro | Prev |