mount_hours() din [1] etichetează prin coloana $ora lecţiile $prof|$cls repartizate anterior într-o aceeaşi zi, urmărind îndeplinirea unei singure condiţii (de aceea, orarul acelei zile se obţine foarte repede): fiecare profesor are zero, una sau cel mult două ferestre; dar există şi lecţii cuplate, marcate prin „profesori fictivi” – încât „orarul” returnat ascunde anumite suprapuneri: de exemplu, într-o aceeaşi oră a zilei, cuplul "p01p02" intră la o anumită clasă, iar "p01" (sau "p02") intră la o altă clasă.
Pentru a corecta suprapunerile ascunse existente, în [1] am procedat cel mai simplu, folosind aplicaţia interactivă /dayRecast.html – ceea ce este totuşi foarte incomod, dat fiind că avem de repetat pentru fiecare zi, nişte operaţii manuale sâcâitoare.
Iar fără corectarea prealabilă a suprapunerilor ascunse, nu putem folosi programul (tot din [1]) de reducere a ferestrelor – încât se cuvine să ne ocupăm de un program intermediar, prin care să automatizăm cumva, corectarea necesară; aici doar vom contura, un astfel de program.
# correct.R source("stmt_utils.R") # select_cupl(), orarByCls(), Z <- readRDS("orar_lst5_7.RDS") # orarele zilelor, cu suprapuneri ascunse load("messing.RDS") # Lx1, Lx2 (dependenţe între profesorii cuplaţi) X <- Z[["Lu"]] # orarul uneia dintre zile prof_day <- unique(X$prof) # profesorii şi profesorii fictivi, pe ziua X Lx1 <- select_cupl(Lx1, prof_day) # dependenţele existente în ziua X Lx2 <- select_cupl(Lx2, prof_day) nam1 <- names(Lx1) # profesorii care intră în cupluri ("p01", "p02", etc.) nam2 <- names(Lx2) # profesorii fictivi ("p01p02", etc.) dep1 <- unlist(map(seq_along(Lx1), function(i) c(nam1[i], Lx1[[i]]))) dep2 <- unlist(map(seq_along(Lx2), function(i) c(nam2[i], Lx2[[i]]))) dep <- unique(union(dep1, dep2)) prof_free <- setdiff(prof_day, dep) # profesorii neimplicaţi în cuplaje M <- as.matrix(orarByCls(X)) Cls <- M[, 1] M <- M[, 2:ncol(M)] row.names(M) <- Cls # M este "matricea orară" a claselor M[is.na(M)] <- '-' nrw <- nrow(M) ncl <- ncol(M) print.table(M) cls 1 2 3 4 5 6 7 10A p01p02 p36 p12 p14 p13 p21 p15 10B p32 p18 p09 p22 p05 p15 - 10C p38 p07 p05 p25 p35 p16 - 10D p31 p12 p16 p09 p21 p19 - 10E p34p07 p28 p46 p39 p03 p27 p04 10F p03 p06p33 p45 p11 p20 p35 - 11A p25 p01 p35 p40 p23 p20 - 11B p28 p01p02 p13 p05 p02 p12 - 11C p30 p31 p28 p17 p18 - - 11D p27 p10 p04 p02 p58 - - 11E p11p44 p26 p10 p03 p09 - - 11F p09 p06 p25 p23 p26 p14 - 12A p01 p30 p01p02 p36 p17 p04 - 12B p22 p29 p30 p16 p24 p17 - 12C p29 p23 p42 p18 p19 p07 - 12D p49 p22 p08 p15 p27 - - 12E p08p47 p08p25 p19 p21 p15 p08p11 - 12F p12 p20 p06 p04 p07 p26 - 5G p06 p46 p17 p56 p04 p45 - 6G p50 p42 p56 p08 p45 p24 - 7G p62 p24 p21 p32 p40 p33 - 8G p61 p14 p20 p13 p46 p56 p05 9A p36 p32 p02 p24 p14 p05 - 9B p11 p03 p31 p10 p16 p22 - 9C p06p33 p37 p11 p07 p10 p03 - 9D p18 p33 p26 p19 p29 p39 - 9E p34p09 p38 p03 p27 p39 p13 - 9F p37 p08 p23 p45 p33 p10 -
În "vrecast.R" din [1] (pentru reducerea ferestrelor) am folosit ”matricea orară” a profesorilor şi am introdus funcţia move_cls() pentru mutările-Kempe ale claselor; acum (pentru corectarea suprapunerilor ascunse) ni se pare preferabil să mutăm profesori, dintr-o oră în alta – încât plecăm de la matricea orară a claselor.
În orarul redat mai sus avem de exemplu, această „suprapunere ascunsă”: "p01" intră la prima oră la clasa 12A şi totodată, împreună cu "p02", la clasa 10A; pentru corectare, trebuie să mutăm într-o altă coloană, fie pe "p01", fie pe "p01p02".
Deocamdată (câtă vreme ignorăm ferestrele care pot apărea şi ne rezumăm la corecturi), alegem ca regulă (cu eventuale excepţii) să mutăm profesorii ("p01") şi nu profesorii fictivi ("p01p02"); procedura prin care vom muta un profesor dintr-o coloană în alta seamănă probabil cu move_cls() (trebuind bazată şi ea, pe ideea de recolorare a lui Kempe, evidenţiată anterior) şi amânăm specificarea ei.
Ceea ce ne propunem aici este să obţinem o listă (minimală, poate) de asemenea mutări şi să vedem cam cum s-o folosim pentru a lichida suprapunerile ascunse.
Pentru un profesor fictiv oarecare cup (de exemplu "p01p02"), fie lCR lista coloanelor lui M (matricea orară a profesorilor) în care apare acesta.
Putem obţine lista acestor coloane foarte simplu, dacă ţinem seama că în R un obiect matrix este în fond un vector atributat cu două dimensiuni – accesat în modul implicit, „pe coloane”; dacă idx este indexul unui element oarecare din vectorul respectiv şi o coloană are nrw elemente, atunci idx %/% nrw + 1L (unde '%/%' este operatorul de împărţire întreagă, "DIV") ne dă rangul coloanei care conţine acel element, iar idx %% nrw (unde '%%' este operatorul "MOD") ne dă rangul liniei elementului:
> cup <- "p01p02" > lCR <- map(which(M == cup), function(idx) + c(idx %/% nrw + 1L, idx %% nrw)) > lCR [[1]] [1] 1 1 # p01p02 apare în coloana 1, pe linia 1 [[2]] [1] 2 8 # p01p02 apare în coloana 2, pe linia 8 [[3]] [1] 3 13 # p01p02 apare în coloana 3, pe linia 13
Noi vom avea nevoie numai de coloane şi vom folosi map_int(), în loc de map().
Orele profesorilor indicaţi în Lx2[[cup]] nu au voie să se suprapună cu cele ale lui cup – deci dacă într-o coloană oarecare din lCR apare vreun profesor P din Lx2[[cup]], atunci avem de corectat această suprapunere, mutând P într-una sau alta dintre coloanele „libere” (neindicate în lCR); dar coloana în care mutăm P trebuie să nu conţină deja P şi deasemenea, să nu conţină vreunul dintre profesorii din lista Lx1[[P]] (altfel am crea alte suprapuneri) – în plus, trebuie să nu conţină '-' (care marchează încheierea orelor clasei pe ziua respectivă).
Urmând exact descrierea „logică” de mai sus, putem formula funcţia:
correct <- function(M) { for(cup in nam2) { lCR <- map_int(which(M == cup), function(idx) idx %/% nrw + 1L) cat(cup, lCR, "\n") for(c1 in lCR) { for(P in Lx2[[cup]]) { if(P %in% M[, c1]) { ll <- which(M[, c1] == P) for(k in setdiff(1:ncl, lCR)) { if(! (P %in% M[, k] | any(Lx1[[P]] %in% M[, k]))) { if(M[ll, k] != '-') cat(c1, k, P, "\n") } } } } } } }
Am preferat deocamdată să afişăm (prin cat()), obţinând o listă „brută” (pe ecran) şi nu chiar un obiect list() (pe care să-l exploatăm ulterior în program); vom putea astfel, să observăm uşor unele incompatibilităţi între „mutările” listate:
> correct(M) p01p02 1 2 3 p06p33 1 2 p08p11 6 p34p07 1 p34p09 1 1 4 p01 1 4 p06 p08p25 2 1 2 p34p09 1 2 p09 1 5 p01 1 5 p06 2 5 p08 1 3 p34p09 1 6 p09 1 6 p01 1 6 p06 p08p47 1 1 4 p34p09 1 2 p34p07 2 4 p01 2 4 p06 p11p44 1 1 5 p34p09 1 3 p34p07 2 5 p01 2 5 p06 1 2 p11 1 6 p34p09 1 4 p34p07 2 6 p01 2 6 p06 1 5 p11 1 5 p34p07 3 6 p02 2 3 p33 1 6 p34p07 2 4 p33 1 7 p34p07
p01p02 apare în coloanele 1, 2, 3 şi se suprapune cu p01 în coloanele 1, 2 şi cu p02 în coloana 3; să observăm că mutarea "1 4 p01" (se mută p01 din coloana 1 în coloana 4) este incompatibilă cu mutarea ulterioară "2 4 p01" (în coloana 4 ar apărea a doua oară, p01). Suprapunerea din coloana 1 se poate corecta în trei moduri (1 4, 1 5, sau 1 6 p01); alegând unul dintre acestea, pentru corectarea suprapunerii din coloana 2 (tot cu p01) rămân două variante; rezultă că pentru "p01p02" avem de ales între 6 variante de corectare (prin trei mutări) a suprapunerilor – de exemplu aceasta: 1 4 p01, 2 5 p01 şi 3 6 p02 – şi bineînţeles că am alege pe aceea care produce mai puţine „stricăciuni” (asupra poziţiei în coloane a celorlalţi profesori).
Analog, pentru a corecta suprapunerile din coloanele 1 şi 2 ale lui "p06p33", cu p06 sau cu p33 – avem 3×2×2=12 variante de câte trei mutări, de exemplu: "1 4 p06", "2 5 p06", urmat de mutarea "2 3 p33".
p34p07 se suprapune în coloana 1 cu p34p09 (şi am avea 5 posibilităţi de corectare) – dar să nu uităm că ne-am fixat din start regula de a muta profesori şi nu profesori-fictivi; deci abandonăm toate aceste 5 variante.
Pentru p34p09 avem 2×5=10 variante de corectare, de exemplu: "1 2 p09", urmat de mutarea lui "p34p07" într-una dintre coloanele 3..7 (mutare care este o excepţie de la regula menţionată).
Mai socotind şi cele două variante de la "p11p44", precum şi varianta de la "p08p25" – rezultă că în total, avem 6+12+10+2+1= 31 de variante de corectare a suprapunerilor ascunse din orarul iniţial considerat aici. Rămâne de văzut cum să reformulăm funcţia correct(), încât să obţinem un obiect list() conţinând exact aceste variante; apoi, cum să alegem una dintre aceste variante, utilizând pentru probarea fiecăreia o anumită funcţie care să asigure (analog cu move_cls()) mutarea unui profesor dintr-o coloană în alta.
vezi Cărţile mele (de programare)