Servindu-ne de "Orarul general clase" — care prezintă pe zile și ore, disciplinele de la fiecare clasă — putem constitui, de exemplu pentru Mate, un graf G în care două clase sunt adiacente dacă au Mate într-o aceeași zi și oră (trebuind să aibă profesori diferiți); numărul cromatic $\chi$(G) al acestui graf ne va spune câți profesori ar fi necesari pentru acoperirea lecțiilor existente pe acea disciplină (respectând alocarea inițială pe zile și ore a acestora), iar o colorare pe vârfuri a lui G ne-ar da o încadrare pe clase (mai mult sau mai puțin acceptabilă) a profesorilor respectivi.

Pentru Mate, fiecare clasă are de obicei 4 sau 5 ore/săptămână și dacă numărul de clase este mare (vreo 30 de clase), atunci $\chi$(G) este în general, greu de aflat (o colorare exactă, aplicând backtracking sau o metodă de programare întreagă, ar dura exorbitant de mult), încât trebuie să ne mulțumim cu o colorare "greedy" (prin care de obicei, vor rezulta ceva mai mulți profesori decât ar fi necesar). Dacă dispunem și de "Orarul general profesori" — ceea ce n-a fost cazul în [1] — atunci vom putea verifica dacă rezultatul obținut prin colorarea grafului G este acceptabil…

Considerăm un alt caz față de [1], anume un caz în care dispunem de ambele orare:

library(tidyverse)
CL <- readRDS("tgn_cls.RDS")   # datele din "Orarul general clase"
PR <- readRDS("tgn_prof.RDS")  # datele din "Orarul general profesori"

CL și PR conțin datele din fișierele PDF originale, în formatul tabelar binecunoscut: câte o linie lungă pentru fiecare clasă și respectiv profesor, conținând în ordinea zilelor și orelor zilei, disciplinele și respectiv, clasele unde are de intrat profesorul. Cele două "orare" prezintă de fapt unul și același orar al lecțiilor de desfășurat în școală, doar că în CL lipsesc profesorii care fac disciplinele, iar în PR lipsesc disciplinele; bineînțeles că putem reuni datele din cele două orare, încât o "lecție" să spună și profesorul și disciplina și clasa și desigur, ziua și ora la care trebuie făcută acea lecție…

Dar înainte de a normaliza astfel datele (separându-le pe cele cinci variabile independente evidențiate mai sus), trebuie să verificăm dacă vorbim de aceleași clase — așa ar fi normal! — în CL și respectiv în PR… Iar situațiile reale sunt de obicei altfel, decât zicem noi că ar fi "normal"; în CL clasele apar în prima coloană, în PR apar în celelalte coloane (împreună cu "", când în ora respectivă profesorul este liber):

> CL[, 1] %>% unique()
 [1] ".V A"    ".V B"    ".VI A"   ".VI B"   ".VII"    ".VIII A" ".VIII B"
 [8] "IX RA"   "IX RB"   "IX RC"   "IX RD"   "IX UA"   "IX UB"   "IX UC"  
[15] "X RA"    "X RB"    "X RC"    "X RD"    "X RE"    "X UA"    "X UB"   
[22] "X UC"    "XI RA"   "XI RB"   "XI RC"   "XI RD"   "XI RE"   "XI UA"  
[29] "XI UB"   "XI UC"   "XII RA"  "XII RB"  "XII RC"  "XII RD"  "XII RE" 
[36] "XII UA"  "XII UB"  "XII UC" 
> unlist(PR[-1], use.names = FALSE) %>% unique() %>% sort()
 [1] ""             ".V A"         ".V B"         ".VI A"        ".VI B"       
 [6] ".VII"         ".VII I A"     ".VII I B"     "IX\nRA/ X RA" "IX\nRB/ X RB"
[11] "IX\nRC/ X RC" "IX\nRD/ X RD" "IX RA"        "IX RB"        "IX RC"       
[16] "IX RD"        "IX RD X RD"   "IX UA"        "IX UB"        "IX UC"       
[21] "X\nRE/ X UC"  "X\nUA/ X UB"  "X RA"         "X RB"         "X RC"        
[26] "X RD"         "X RE"         "X UA"         "X UA X UB"    "X UB"        
[31] "X UC"         "XI RA"        "XI RB"        "XI RC"        "XI RD"       
[36] "XI RE"        "XI UA"        "XI UB"        "XI UC"        "XII RA"      
[41] "XII RB"       "XII RC"       "XII RD"       "XII RE"       "XII UA"      
[46] "XII UB"       "XII UC"

Vedem că pentru clase au fost aplicate denumiri elegante (folosind cifrele romane) și ambițioase, indicând și profilul ("Real" sau "Uman")… N-am înțeles de ce s-a folosit "." drept prefix al notației claselor de gimnaziu; ".VII I A" care apare nefericit în PR înseamnă desigur, confruntând cu numele din CL, ca fiind clasa ".VIII A"; iar "X\nUA/ X UB", sau în alt loc "X UA X UB", desemnează un cuplaj (sau poate un tuplaj) pe o anumită disciplină, a claselor respective (iar pentru a reflecta și cuplajele existente, numărul de "clase" din PR ajunge să fie mai mare decât cel din CL).

Aici ne va interesa numai disciplina "Matematică" și numai clasele la care se face așa ceva (că unele clase de "Uman" nu au "Matematică" în programă — ceea ce este cu siguranță, o greșală "strategică" regretabilă dacă "liceu" mai înseamnă ceva, nu "pregătire pentru BAC"); în CL avem bineînțeles, termenii "Matem atica" și "Matem atica - opt", că în celulele PDF de pe care am extras datele, cuvintele prea lungi apar despărțite pe rânduri.
Prin urmare prima grijă a noastră este să eliminăm spațiile din numele disciplinelor și claselor (putând apoi și să reunim cele două seturi, pe clasele comune lor):

CL <- CL %>% apply(., 2, str_remove_all, " ") %>% 
      as.data.frame()  # transformă "Matem atica - opt" în "Matematica-opt", etc. 
PR <- PR %>% apply(., 2, str_remove_all, " ") %>% 
       as.data.frame()  # transformând ".VII I A" în ".VIIIA" etc.

Să normalizăm acum, cele două seturi de date (adică să dispunem datele conform semnificației lor: nume de disciplină, nume de clasă, de zi, etc.):

Zile <- c("Lu", "Ma", "Mi", "Jo", "Vi")
normalize <- function(ORR, var_name)
    ORR %>% 
    pivot_longer(2:36, names_to = "ziOra", values_to = var_name) %>%
    separate(ziOra, c("zl", "ora"), sep = 2) %>%
    mutate(ora = as.integer(ora), 
           zl = factor(zl, levels = Zile, ordered = TRUE))
Cn <- normalize(CL, "obj") %>% filter(obj != "" & !is.na(obj))
Pn <- normalize(PR, "cls") %>% filter(cls != "" & !is.na(cls))

Cn conține toate lecțiile claselor, pe câte o linie cls|zl|ora|obj, iar Pn conține toate lecțiile profesorilor, pe câte o linie prof|zl|ora|cls; firește, cele două seturi trebuie să conțină un același număr de lecții:

> sapply(list(Pn, Cn), nrow)
[1] 1131 1131  # numărul de lecții

și în mod normal, putem îmbina datele din cele două seturi:

or2 <- left_join(Pn, Cn, by = c("zl", "ora", "cls"))  # prof|zl|ora|cls|obj

Noul set de date or2 conține 1131 lecții prof|zl|ora|cls|obj. Ne interesează aici numai lecțiile de "Matematică" (fiindcă sunt multe); dar am constatat că orele de "Matematică-opt" sunt date, în două dintre cele trei cazuri, câte unui alt profesor decât cel care face "Matematică" la clasa respectivă (probabil drept "completare de normă didactică", nu prea credem că datorită unui deosebit interes pentru "Matematică" al elevilor claselor respective) — așa că aici vom exclude cele trei lecții "opționale":

Mt <- or2 %>% filter(obj == "Matematica") %>% 
      select(-obj)  # 130 lecții prof|zl|ora|cls (de "Matematică")

Setul rezultat Mt conține toate lecțiile de "Matematică", în număr de 130; la o normă didactică de 20 de ore ar trebui să avem 6 sau 7 profesori — dar fiindcă am păstrat și câmpul "prof", putem constata câți sunt în realitate:

> Mt$prof %>% unique() %>% length()
[1] 6  # profesori "Mt"

și rămâne de văzut dacă vom putea găsi o colorare a grafului G amintit la început, cu numai 6 profesori…

Să simplificăm totuși numele claselor care apar în setul Mt, folosind un procedeu tipic pentru limbajul R: transformăm câmpul cls în "factor", listăm în consolă nivelurile acestui factor și folosim funcția levels() pentru a le modifica după cum dorim, apoi readucem cls la valori de tip "character":

Mt <- Mt %>% mutate(cls = factor(cls))
# > levels(Mt$cls)  # numele și ordinea inițială a claselor
# [1] ".VA"    ".VB"    ".VIA"   ".VIB"   ".VII"   ".VIIIA" ".VIIIB" "IXRA"  
# [9] "IXRB"   "IXRC"   "IXRD"   "IXUA"   "IXUB"   "IXUC"   "XIIRA"  "XIIRB" 
#[17] "XIIRC"  "XIIRD"  "XIIRE"  "XIIUC"  "XIRA"   "XIRB"   "XIRC"   "XIRD"  
#[25] "XIRE"   "XIUC"   "XRA"    "XRB"    "XRC"    "XRD"    "XRE"    "XUA"   
#[33] "XUB"    "XUC" 
Kls <- levels(Mt$cls) <- c("5A", "5B", "6A", "6B", "7A", "8A", "8B", "9A", "9B",  "9C", "9D", "9E", "9F", "9G", "12A", "12B", "12C", "12D", "12E", "12F", "11A", "11B", "11C", "11D", "11E", "11F","10A", "10B", "10C", "10D", "10E", "10F", "10G", "10H") 
Mt <- Mt %>% mutate(cls = as.character(cls))

Cum ne așteptam, în Mt avem numai 34 de clase, dintre cele 38 existente în CL.

Acum să înființăm graful G în care două clase dintre cele existente în Mt sunt adiacente dacă apar într-o aceeași zi și oră:

library(igraph)
Adj <- matrix(0L, nrow = length(Kls), ncol = length(Kls), byrow = TRUE, 
              dimnames = list(Kls, Kls))  # șablonul matricei de adiacență
E <- lapply( Mt %>% split(list(.$zl, .$ora)), 
             function(S) S %>% pull(cls)) %>%   # clasele din ziua și ora
     setNames(NULL) %>% compact()
for(j in 1:(length(E)-1)) {
    Q <- E[[j]]
    for(k in 1:(length(Q)-1)) {
        h <- k+1
        while(h <= length(Q)) {
            Adj[Q[k], Q[h]] <- Adj[Q[h], Q[k]] <- 1L
            h <- h+1
        }
    }
}
G <- graph_from_adjacency_matrix(Adj, mode = "undirected")
#    > vcount(G)   [1] 34 vârfuri
#    > ecount(G)   [1] 202 muchii

Graful G se dovedește a fi prea mare pentru a reuși o colorare exactă (cu 6 profesori, în cazul de față); în [1] am folosit greedy_vertex_coloring() din pachetul igraph, dar cu parametrul heuristic="dsatur" — caz în care la orice repetare a comenzii obținem o aceeași colorare (chiar și dacă am reordona vârfurile), cu mai mult de 6 profesori…
Însă metoda obișnuită de colorare (fără a implica DSatur) produce colorări diferite dacă reordonăm vârfurile și repetând de un anumit număr de ori, putem găsi eventual o colorare optimală (cu numărul minim posibil, de culori):

CNT <- table(Mt$cls) %>% sort()  # numărul de "Matematică" pe fiecare clasă
sink("gvcol.txt")  # pentru a reține totuși, colorările efectuate
repeat {
    G <- permute(G, sample(vcount(G)))  # permută aleatoriu vârfurile
    P <- greedy_vertex_coloring(G)  # colorarea curentă
    pr_mt <- sapply(1:max(P), function(k) CNT[names(P[P == k])] %>% sum()) %>% 
         setNames(paste0("Mt", 1:max(P)))
    print(pr_mt)
    if(max(P) < 7) break  # încheie dacă s-au aplicat mai puțin de 7 culori
}
print(sapply(1:max(P), function(k) CNT[names(P[P == k])]))
sink()

Executând programul constituit "pe bucăți" mai sus, obținem în fișierul "gvcol.txt" (sau, la eventuale repetări ale execuției programului, "gvcol1.txt" etc.) un anumit număr de colorări (vreo 150 într-o execuție, peste vreo mie sau două mii, în alte execuții, cam totdeauna în câte o fracțiune de secundă), majoritatea cu 7, 8 sau 9 culori (profesori), de exemplu:

    Mt1 Mt2 Mt3 Mt4 Mt5 Mt6 Mt7 
     24  24  19  23  20  15   5 
    Mt1 Mt2 Mt3 Mt4 Mt5 Mt6 Mt7 Mt8 
     22  22  22  20  15  14  11   4 
    Mt1 Mt2 Mt3 Mt4 Mt5 Mt6 Mt7 Mt8 Mt9 
     21  20  24  21  16  14   5   4   5 

iar în final avem și o colorare cu 6 profesori:

    Mt1 Mt2 Mt3 Mt4 Mt5 Mt6 
     21  19  24  24  23  19 
[[1]]  Mt1
10G 11C 11B  7A 11D 
  2   5   5   4   5 
[[2]]  Mt2
 9A 10B 12E 10H  9D 
  4   4   5   2   4 
[[3]]  Mt3
12B 12F  5B  6B 12C 10E 
  5   2   4   4   5   4 
[[4]]  Mt4
 6A  5A  9C  8B  9E  9F 10D 
  4   4   4   4   2   2   4 
[[5]]  Mt5
 8A 11F  9G 10C 12D 12A 
  5   2   2   4   5   5 
[[6]]  Mt6
11E 10A 10F  9B 11A 
  4   4   2   4   5 

Numai la Mt2 și Mt6 lipsește câte o oră până la norma de 20 ore, dar le putem adăga câte una dintre cele 3 lecții "opționale" pe care le omisesem din setul Mt.

Prin funcția orar_prof() din [1]-Bis, găsim și orarele celor 6 profesori "Mt", de exemplu:

> or_mt$Mt1                  > or_mt$Mt5
       Lu  Ma  Mi  Jo  Vi             Lu  Ma  Mi  Jo  Vi
    1 10G   - 11D 11C   -          1 10C 11F 11F   -   -
    2 11C 11D  7A   - 11C          2  8A  9G 10C   -  8A
    3 11B  7A 11C 10G 11B          3 12D 12D  8A 12D 12A
    4  7A 11C 11B 11D   -          4 12D  8A 12A  9G 10C
    5   - 11B   - 11B 11D          5 12A 12A   - 12A   -
    6 11D   -   -  7A   -          6   - 10C   -  8A 12D
    7   -   -   -   -   -          7   -   -   -   -   -

De observat că 11D se poate schimba, pe locurile boldate în stânga și în dreapta, cu 11F plus 9G — încât Mt1 rămâne cu 20 ore, iar Mt5 capătă 24 de ore…

Noi am repetat execuția programului de 9 ori (în diverse reprize de lucru); într-un singur caz dintre acestea, durata execuției a fost de câteva secunde (înloc de o fracțiune de secundă) și a rezultat un număr foarte mare, vreo 3700, de colorări (majoritatea cu câte 7 sau 8 profesori, câteva cu 9 profesori); dar în toate, colorarea finală cu 6 profesori este "izomorfă" cu cea redată mai sus (contrar cu ce ne așteptam!): doi profesori cu câte 24 de ore, doi cu câte 19 ore, unul cu 21 și unul cu 23 de ore (iar încadrarea pe clase a acestora coincide cu cea redată mai sus). Aceasta înseamnă desigur, că repetarea execuției programului respectiv este inutilă.

Fiindcă păstrasem în Mt câmpul prof și acesta conține numele profesorilor din fișierele PDF inițiale (doar că fără spații, în urma operațiilor de la început asupra datelor din seturile CL și PR; însă numele reale nu interesează și le înlocuim prin "MT"), putem constata acum că încadrarea rezultată mai sus este acceptabilă, fiind foarte aproape de aceea originală:

> org <- table(Mt[c("prof", "cls>")]) %>% as.data.frame()
> levels(org$prof) <- paste0("MT", 1:6)  # nu interesează numele reale
> sapply(org %>% split(.$prof), function(P) sum(P$Freq))
> sapply(org %>% split(.$prof), function(P) 
                     P %>% filter(Freq > 0) %>% 
                     pull(cls) %>% as.character() %>% sort()
  )
MT1 MT2 MT3 MT4 MT5 MT6 
24  24  19  19  20  24 
    $MT1  "10E 12B 12C 12F 5B 6B"   # coincide (pe clase) cu Mt3
    $MT2  "10D 5A 6A 8B 9C 9E 9F"   # coincide (pe clase) cu Mt4
    $MT3  "10B 10H 12E 9A 9D"   # coincide (pe clase) cu Mt2
    $MT4  "10A 10F 11A 11E 9B"   # coincide (pe clase) cu Mt6
    $MT5  "10G 11B 11C 11F 7A 9G" 
    $MT6  "10C 11D 12A 12D 8A"

Încadrările pe clase ale profesorilor Mt3, Mt4, Mt2 și Mt6 (găsite mai sus prin colorarea grafului G), coincid respectiv cu cele existente în orarele originale pentru primii 4 profesori MT; iar dacă între Mt1 și Mt5 schimbăm clasele 11D, 11F și 9G (se poate verifica folosind cele două orare redate mai sus că acest schimb este posibil), atunci Mt1 și Mt5 vor căpăta aceleași încadrări ca MT5 și respectiv, MT6.