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

Chestiunea cuplajelor existente în orarul şcolar (V)

limbajul R | orar şcolar
2021 nov

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.

Lista brută a mutărilor corectoare

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)

docerpro | Prev | Next