Tuplaje buchisite

Pentru "Fr" și "Gr" credeam că avem cuplaje / tuplaje obișnuite și pentru ele notasem "FG" în câmpul obj al setului ORR — ignorând complet numele de profesori adăugate (prin excepție față de celelalte discipline) în celulele Excel inițiale:

Văzând astfel de imagini pe o pagină sau alta, am zis automat (fără a mai corela cu alte pagini) că acea clasă este despărțită în două grupe, la care intră respectiv cei doi profesori notați (dar neobservați până aici) în celulă.

Descoperim acum că tuplajele existente sunt așa de întortocheate și chițibușărite, încât nu le-am putea reinventa fără a ține seama și de numele postate în celulele Excel din fișierele PDF originale (de pe care am reprodus figura de mai sus). În loc să inventăm profesorii necesari pentru disciplinele respective (ca în [1], pe baza unei colorări a grafului G) — plecăm acum de la cei introduși în fișierele PDF originale: sunt trei profesori pe "Franceză" Fr1, Fr2 și Fr3 și doi pe "Germană", Gr1 și Gr2.

Înființăm un program în care investigăm lecțiile respective din ORR, evidențiind și căutând să sistematizăm cuplajele și tuplajele existente pe cele două limbi:

#  tpl_fg.R
library(tidyverse)
ORR <- readRDS("orar-cl_5.RDS")  # 1016 x 5
Zile <- levels(ORR$zl)
FG <- ORR %>% filter(obj %in% c("Fr", "Gr", "FG")) %>% 
      arrange(zl,ora,cls) %>% as.data.frame()
> head(FG, 10)  # exemplificăm dintre cele 70 lecții listate
       cls zl ora obj prof
    1  12D Lu   1  FG      # cuplaj 'FG' pe 12D 
    2  11C Lu   2  FG      # tuplaj 'FG' pe 11C+11E
    3  11E Lu   2  FG     
    4  09B Lu   3  FG      # tuplaj 'FG' pe 9B+9E
    5  09E Lu   3  FG     
    6  08A Lu   4  Fr      # lecție individuală
    7  09A Lu   4  FG      # tuplaj 'FG' pe 9A+9C+9D
    8  09C Lu   4  FG     
    9  09D Lu   4  FG     
    10 05C Lu   5  Fr 

Pe liniile redate aici vedem imediat 3 tuplaje (două sau mai multe clase figurează pe același zl|ora la 'FG'); dacă nu ne mai uitam pe orarul PDF original, consideram probabil că 'FG' ar însemna doi profesori (din elevii a două sau trei clase se formează ad-hoc două noi clase, la care intră câte unul dintre cei doi).
De fapt, în tuplajul pe 11C+11E intră trei profesori: Fr1, Fr2 și Gr1 (se formează trei clase, cu elevii celor două, câte una pentru fiecare dintre cei trei profesori).
Iar în tuplajul 9A+9C+9D intră chiar patru profesori: Fr2, Fr3 și cei doi de 'Gr' — de unde rezultă că ora de Fr de pe linia 6 (cu același zl|ora ca a tuplajului respectiv) aparține lui Fr1 (de aceea, am inclus în subsetul FG și lecțiile individuale Fr și Gr: când o lecție individuală are același zl|ora ca și vreun tuplaj, putem decide uneori, căruia dintre cei 5 profesori, trebuie alocată).

Să listăm lecțiile din setul FG, asociind fiecărui obiect (Fr, Gr și 'FG') clasele la care apare acesta ("one-to-many"), eventual în aceeași zi și oră:

FGs <- FG %>% 
       split(list(.$obj, .$zl, .$ora)) %>%
       discard(function(K) nrow(K) == 0) %>%
       map_dfr(., function(K)
           data.frame(
               obj = K$obj[1],
               cls = paste(K$cls, collapse = " ")
           )) %>%
       arrange(obj, cls)
> slice_sample(FGs, n=5)  # redăm un mic eșantion, aleatoriu
      obj         cls
    1  Fr         07A  # există zl|ora în care numai 7A are Fr
    2  FG 09A 09C 09D
    3  Gr         06B
    4  Fr     07A 07B  # există zl|ora când și 7A și 7B fac Fr
    5  FG 09A 09C 09D

Când pentru Fr sau Gr, vedem mai multe clase pe o aceeași linie din FGs, deducem că acestea au neapărat, profesori diferiți (și vom putea reconstitui, măcar parțial, clasele din încadrarea fiecăruia).

Să desprindem din setul FGs cuplajele și tuplajele, selectând câte o singură linie de fiecare; luându-ne după PDF-ul original, adăugăm și profesorii corespunzători:

FGt <- FGs %>% filter(obj=="FG") %>% unique() %>%
       mutate(prof = "") %>% edit()  # edităm câmpul 'prof'
       obj         cls            prof
    1   FG 09A 09C 09D     Fr2 Fr3 Gr1
    3   FG     09B 09E     Fr1 Fr3 Gr1
    5   FG     10A 10D     Fr3 Gr1 Gr2
    7   FG 10B 10C 10E Fr1 Fr2 Fr3 Gr2
    9   FG 11A 11B 11D     Fr2 Fr3 Gr1
    11  FG     11C 11E     Fr1 Fr2 Gr1
    13  FG         11E         Fr2 Gr1
    14  FG     12A 12B     Fr1 Gr1 Gr2
    16  FG     12C 12E     Fr1 Fr3 Gr2
    18  FG         12D         Fr1 Gr1
    20  FG         12E         Fr1 Gr2

Obs. Dacă ulterior, într-o nouă sesiune de lucru, am încărca "tpl_fg.R", atunci se vor executa iarăși comenzile redate mai sus — însemnând că va trebui să înscriem din nou, câmpul prof; pentru a preveni aceasta, salvăm datele curente prin save(FG, FGs, FGt, file="FG_s_t.Rda") și înlocuim comenzile de mai sus cu load("FG_s_t.Rda").

Avem deci 3 cuplaje: Fr2Gr1 pe clasa 11E, Fr1Gr1 pe 12D și Fr1Gr2 pe 12E. Celelalte linii din FGt consemnează tuplaje de două sau trei clase și trei sau patru profesori.

Ca și în [1] (pentru "Des/Muz"), o să eliminăm tuplajele din ORR și o să constituim pentru ele un "orar parțial"; dar spre deosebire de [1], acum avem și tuplaje în care numărul de clase este mai mic decât cel de profesori (caz în care nu putem aloca clasele rând pe rând, câte unui profesor); dar… și spre deosebire de [2], ceea ce înseamnă că s-ar putea să fie necesare anumite adaptări ale funcțiilor prin care urmează să constituim noul orar (vizând repartizarea echilibrată pe zile și pe ore, apoi reducerea ferestrelor).

Constituim un "orar parțial" aleatoriu pentru tuplaje (fără a mai separa pe clase și profesori, ca în [1]):

tupl <- FGt %>% filter(grepl(" ", cls))  %>%   # exclude cuplajele
        select(cls, prof) %>%
        uncount(2) %>%  # sunt câte 2 ore/tuplaj
        mutate(zl = factor(rep_len(sample(Zile), nrow(.)),
               levels = Zile, ordered = TRUE)) %>%
        `rownames<-`(NULL)
saveRDS(tupl, "tuplaje_b.RDS")
               cls             prof zl               cls          prof zl
    1  09A 09C 09D      Fr2 Fr3 Gr1 Lu    9  11A 11B 11D   Fr2 Fr3 Gr1 Vi
    2  09A 09C 09D      Fr2 Fr3 Gr1 Mi    10 11A 11B 11D   Fr2 Fr3 Gr1 Jo
    3      09B 09E      Fr1 Fr3 Gr1 Ma    11     11C 11E   Fr1 Fr2 Gr1 Lu
    4      09B 09E      Fr1 Fr3 Gr1 Vi    12     11C 11E   Fr1 Fr2 Gr1 Mi
    5      10A 10D      Fr3 Gr1 Gr2 Jo    13     12A 12B   Fr1 Gr1 Gr2 Ma
    6      10A 10D      Fr3 Gr1 Gr2 Lu    14     12A 12B   Fr1 Gr1 Gr2 Vi
    7  10B 10C 10E  Fr1 Fr2 Fr3 Gr2 Mi    15     12C 12E   Fr1 Fr3 Gr2 Jo
    8  10B 10C 10E  Fr1 Fr2 Fr3 Gr2 Ma    16     12C 12E   Fr1 Fr3 Gr2 Lu

Cele două lecții tuplate pe clasele 9A+9C+9D s-ar desfășura în zilele Lu și Mi; lecțiile pe 12C+12E sunt alocate Lu și Jo ș.a.m.d.
Când vom avea de controlat numărul de ore/zi (pe clasă / profesor), probabil că nu va fi greu să individualizăm clasele și profesorii, din tuplajele astfel înregistrate.

Acum, eliminăm din FG lecțiile tuplate (acelea pentru care există cel puțin două linii cu același zl|ora):

lst_tpl <- FG %>% filter(obj=="FG") %>% split(list(.$zl, .$ora)) %>%
           discard(function(K) nrow(K) < 2)
sst <- data.frame()
for(i in 1:length(lst_tpl)) 
    sst <- rbind(sst, lst_tpl[[i]])
rownames(sst) <- NULL  # print(sst)
ORR <- anti_join(ORR, sst)

În ORR ne-au rămas cu "FG" pe câmpul obj, numai lecțiile cuplate ("pe grupe"); înscriem pe ele, profesorii corespunzători și în final, salvăm înapoi ORR:

cpl <- c("11E", "12D", "12E")  # clasele cuplajelor
pcp <- c("Fr2Gr1", "Fr1Gr1", "Fr1Gr2")  # profesorii corespunzători
for(i in 1:length(cpl)) {
    wh <- which(ORR$cls == cpl[i] & ORR$obj=="FG")
    ORR$prof[wh] <- pcp[i]
}
saveRDS(ORR, "orar-cl_5.RDS")  # 978 x 5

Rămâne să completăm încadrările cu lecțiile individuale pe 'Fr' și 'Gr'. Încărcăm FG (și avem grijă să transformăm 'obj' din factor, în character pentru a facilita comparațiile de valori) și tuplajele; căutăm liniile din FG pentru 'Gr' și pentru fiecare, depistăm tuplajele cu același zl|ora dacă există:

load("FG_s_t.Rda")
tupl <- readRDS("tuplaje_b.RDS")
FG <- FG %>% mutate(obj = as.character(obj))
GR <- FG %>% filter(obj == "Gr") %>% mutate(Obs = "") %>% arrange(cls) 
for(i in 1:nrow(GR)) {
    same <- FG %>% filter(zl == GR[i,2], ora == GR[i,3], 
                          cls != GR[i,1], obj != "Fr")
    if(nrow(same) == 0) next
    if(nrow(same) == 1) {
        GR[i, 6] <- if(same$obj == "Gr") "" else {
                case_when(same$cls == "11E" ~ "Fr2Gr1",
                          same$cls == "12D" ~ "Fr1Gr1",
                          same$cls == "12E" ~ "Fr1Gr2")
                }
    }
    else {
        wh <- which(tupl$cls == paste(same$cls, collapse=" "))
        GR[i, 6] <- tupl[wh[1], 2]
   }
} 
       cls zl ora obj prof         Obs
    1  05A Mi   5  Gr           Fr2Gr1
    2  05A Jo   1  Gr           Fr1Gr1
    3  06A Ma   6  Gr                 
    4  06A Vi   6  Gr      Fr1 Fr3 Gr2
    5  06B Ma   1  Gr                 
    6  06B Jo   6  Gr                 
    7  07C Lu   5  Gr           Fr1Gr2
    8  07C Vi   1  Gr                 
    9  07D Ma   5  Gr                 
    10 07D Jo   5  Gr      Fr1 Fr2 Gr1
    11 08C Ma   5  Gr                 
    12 08C Mi   6  Gr                 
    13 08D Ma   6  Gr                 
    14 08D Mi   6  Gr 

Pe tabelul constituit astfel vedem că 05A cade în același zl|ora cu o lecție a cuplajului Fr2Gr1 — deci 05A trebuie alocată celuilalt profesor, Gr2. Analog, 06A și 07C trebuie duse la Gr1, iar 07D la Gr2.
Fiindcă 08C și 08D au în același timp (Mi/6) lecție de 'Gr', ducem 08C la Gr1 și 08D la Gr2.
Fiindcă Gr2 apare în mai puține tuplaje decât Gr1, ducem clasa rămasă 06B la Gr2.

Înscriem în ORR încadrările stabilite astfel pentru Gr1 și Gr2:

ORR$prof[ORR$obj=="Gr" & ORR$cls %in% c("06A", "07C", "08C")] <- "Gr1"
ORR$prof[ORR$obj=="Gr" & ORR$prof==""] <- "Gr2"

Adaptând secvența de mai sus pentru 'Fr' în loc de 'Gr', stabilim și încadrările pentru Fr1, Fr2 și Fr3, le înscriem și pe acestea în ORR și salvăm înapoi în "orar-cl_5.RDS".

Inventarea profesorilor pentru lecțiile rămase

Să vedem ce lecții ne-au rămas fără profesori:

S <- ORR %>% filter(prof == "")
ts <- table(S$obj)
> ts[ts != 0]
     Di  Ec  EA  ES  En  Ff  In  IH  Is  Lg  Pg  Ph  Sa  SU  Sg  Sp  Th  TI 
     34   5   5  14 106   6  24   5  46   6   3   6   1   1   1   4  14  37

Ca și în [1], prin enframe.R am repartizat orele de En (pe 5 profesori, (22 22 22 20 20)); apoi, orele de Is+IH, (18 18 15).

Pentru In+Pg+TI am investigat direct datele din ORR, repartizând la profesori diferiți clase la care există lecții cu același zl|ora; ne-au rezultat 3 profesori "In1", "In2", "In3" cu câte 18 ore de In, Pg sau TI și un profesor "TI1" cu 10 ore de "TI".

Apoi, iarăși prin "enframe.R", am înscris profesorul "Ff1" cu 12 ore, pe Ff și Lg.

Pentru lecțiile de ES, "enframe.R" ne-a propus doi profesori, cu 12 și respectiv 2 ore; dar am decis să mai acceptăm și câte o excepție, ignorând cele două suprapuneri orare (oricum, vom elimina acuși câmpurile zl|ora); am înregistrat profesorul "ES1" cu 14 ore de ES ("Educatie Sociala"), o oră de SU ("Soc-uman") și una de Sg ("Sociologie"), ignorând existența în ORR a două suprapuneri de lecții.

    Di Ec EA Ph Sa Th 
    34  5  5  6  1 14

Fără să ne mai pese de eventualele suprapuneri pe zl|ora care ar exista în ORR, grupăm lecțiile de Ec ("Economie") și de EA ("Ed. Antreprenorială") la profesorul "Ec1":

> ORR$prof[ORR$obj %in% c("Ec", "EA")] <- "Ec1"

Analog, trecem lecțiile de Ph și Sa la profesorul "Ph1", iar pe cele de Th la "Th1".

Ne-au rămas numai dirigențiile "Di"; acestea trebuie repartizate câte una la fiecare clasă, unuia dintre profesorii acelei clase (dar astfel încât profesorul să fie diriginte la o singură clasă). Alegem diriginții dintre cei neimplicați în cuplaje / tuplaje și fără să ne mai pese de suprapunerile zl|ora care ar putea exista în ORR:

Prof <- ORR %>% filter(prof != "", !grepl("Fr|Gr|Ds|Mz", prof)) %>%
        pull(prof) %>% unique()
Cls <- ORR$cls %>% unique()
Cls <- Cls %>% setNames(Cls)  # vom asocia fiecărei clase câte un diriginte
for(K in names(Cls)) {
    PK <- ORR %>% filter(cls==K) %>% pull(prof) %>%
          unique()  # profesorii clasei
    repeat {
        P <- sample(Prof, 1)  # alege la întâmplare un profesor P
        if(P %in% PK) {  # dacă P are ore la clasa K
            Cls[K] <- P  # P va fi dirigintele clasei K
            Prof <- setdiff(Prof, P)  # P nu va fi diriginte la altă clasă
            break  # trece la altă clasă
        }
    }
}
ORR$prof[ORR$obj == "Di"] <- Cls  # înscrie diriginții claselor
> slice_sample(ORR %>% filter(obj=="Di"), n=4)  # un eșantion aleatoriu
      cls   zl    ora   obj   prof 
    1 05B   Mi    4     Di    Th1  
    2 06A   Vi    4     Di    Bi2  
    3 12D   Jo    3     Di    Mt4  
    4 08B   Ma    7     Di    Fi4  

Subliniem că s-ar putea ca dirigenția pusă în zl|ora la o clasă sau alta, să se suprapună în ORR, cu una dintre lecțiile propriu-zise ale dirigintelui respectiv — dar deja, fiindcă am înființat toți profesorii necesari (în general, fără suprapuneri de lecții în ORR), nu ne mai interesează câmpurile zl|ora|obj; urmează să repartizăm (echilibrat) lecțiile prof|cls, pe zile, apoi pe orele fiecărei zile și în final, să reducem numărul de ferestre apărute astfel în orarul repectiv.