Excel – Problemă cu combinații unice [UPDATED 23.01 H15:44)


Pentru fanii de Excel am primit de la un alt pasionat o problemă deosebit de faină și utilă multora din noi.

Cerințele problemei:

Se dă o echipă formată dintr-un număr finit de membri: A, B, C, D, E, F, G, H etc.

Fiecare dintre ei, lucrează la un anumit task (activitate) (t1, t2, t3 etc). Una și aceeași persoană poate lucra în același timp la unul sau mai multe task-uri (activități).

Structura unui task: NumeTask, Responsabil, Reviewer. Responsabilii sunt introduși manual, Reviewerii se alocă aleator de aplicație.

Constraints:

a) Fiecare dintre ei, poate face echipă cu oricare dintre ceilalți, dar doar pe un singur task (i.e. dacă A lucrează la taskurile t1 si t2, la t1 poate avea un anumit partener: E dar la t2 obligatoriu un alt partener: B);

b) Să nu existe parteneri încrucișați (i.e. interzis situația asta: A lucrează la t1 cu partenerul C, iar C lucreaza la t8 cu partenerul A);

c) Distribuirea fiecăruia ca partener trebuie facută în mod echilibrat;

d) fără VBA (doar cu funcții Excel).

Se cere:

O atribuire în mod aleatoriu, a acestor parteneri. (cu un F9 sa se faca refresh)

Indicii:

F9 se folosește când modul de calculare a foii de calcul este setat pe manual (Formulas, Calculation Options, Manual)

O combinație incorectă:

Duplicate

O combinație corectă:

DuplicateOk

Nu sunt constrângeri de istoric pe alocarea curentă de task-uri.

Puteți alege o altă combinație sau structură a tabelelor. Ceea ce v-am prezentat eu este doar un exemplu.

[UPDATE DUPA ORA 22/20.01.2015]

Așadar, după cum am promis revin cu o serie de soluții.

Soluția lui Cătălin L.

Cătălin este de profesie Virus Analyst la BitDefender și unul dintre cei mai buni studenți ai mei de la masterul Administrarea Afacerilor. A primit 10 la seminar pentru rezolvarea aproape de 80% a problemei.

Mesajul său este:

”Am rezolvat problema, zic eu, folosind Numbers de la Apple, ca nu am la indemana un Excel. Am folosit cateva campuri precalculate ca sa nu scriu o formula prea mare.”

Fișierul său este la adresa: https://onedrive.live.com/view.aspx?resid=6EC38785F56DAE91!360575&ithint=file%2cxlsx&app=Excel&authkey=!AHsr4EX9wWnob7c

sau http://1drv.ms/1uNFoww

Sau accesați direct folderul: https://onedrive.live.com/?cid=6EC38785F56DAE91&id=6EC38785F56DAE91%212853 și deschideți/descărcați fișierul: Combinații unice Catalin L.xlsx

Soluția nu este finală pentru că are destul de multe constante (Hard-Code) pentru a putea fi acceptată.

Soluția mea

Soluția propusă de mine se bazează pe puțin mai multă matematică. În prima fază ID-urile Reviewer-ilor se alocă automat prin funcția =RANDBETWEEN(1;$J$1) în care J1 este maximul ID-urilor din tabela persoane care au un nume în dreptul lor: =COUNTIFS(tblPersons[ID];”<>0″;tblPersons[Name];”<>”)

Normal că acest maxim din J1 nu funcționează corect pentru că dacă ștergem un nume intermediar, numărul rezultat prin acel COUNTIFS nu mai este concludent. Făcând o analogie la tabelele din bazele de date, orice înregistrare vidă nu mai are un ID alocat, așa că structura tabelului tblPersons nu este normalizat din punct de vedere atomic.

Trecem peste această scăpare și continuăm.

Problema concretă constă în a determina unicitatea unui tuplu:

A-B = B-A

În acest context am preferat să utilizez ID-uri numerice în loc de nume concrete sau ID-uri de tip litere.

Ca să pot determina unicitatea tuplului a trebuit să iau în considerare faptul că două numere de diferite mărimi pot da același rezultat: 4+10 = 12+2 ceea ce m-ar fi încurcat în a determina unicitatea unui tuplu.

Soluția găsită de mine a fost folosirea funcției SINH() în reprezentarea numerelor în loc de numerele pur și simplu. SINH() returnează sinusul hiperbolic al unui număr. Ăăă știu, e complicat modul în care am ajuns eu la acea formulă, dar se pare că e cea mai sigură metodă de a determina un număr suficient de diversificat pentru a putea să obții sume diferite din două numere reale destul de apropiate.

Pe coloana F mai este pus și un IF de control pentru cazul în care se alocă în mod aleatoriu un număr asemănător Responsabilului.

Pe Coloana G am folosit o combinație de funcții MATCH() cu IF() și ROW()  care îmi determină dacă acel număr obținut prin însumarea SINH()-urilor de ID-uri este unic în lista de rezultate (coloana F) sau nu.

Restul este apă de ploaie: formatare condițională la nivel de celulă și apoi la nivel de linie.

Fișierul poate fi vizualizat aici: http://1drv.ms/1uoLZP8 sau: https://onedrive.live.com/redir?resid=6EC38785F56DAE91!360578&authkey=!AHsr4EX9wWnob7c&ithint=file%2cxlsx sau din folderul: https://onedrive.live.com/?cid=6EC38785F56DAE91&id=6EC38785F56DAE91%212853

Verdictul

Nimeni nu a obținut sticla de vin, așa că ”potul” se multiplică cu 5: 4 sticle de vin real livrate la adresa fizică a celui care rezolvă problema! Una mi-o păstrez mie! :))

Să ne întoarcem la cerințele de business și să analizăm ce nu este bine în soluția mea:

1. Matematic vorbind când ai un număr mic de angajați, combinațiile unice pentru task-uri este limitat. Exemplu: dacă ai 2 angajați poți crea doar un singur task unic: A responsabil – B reviewer. Sau invers.

Dacă ai trei angajați poți crea trei task-uri unice: A-B, B-C, A-C sau combinații unice ale lor.

Chiar și la mai mulți angajați și mai multe task-uri, funcția de randomizare dă de mai multe ori ”rateuri” referindu-ne aici la faptul că trebuie să apeși de mai multe ori tasta F9 (Calculate Now) pentru a obține rezultate unice.

Poate pentru mulți nu este o problemă, dar cerința este cerință.

Indicația mea este de a compara ID-ul Reviewer-ului cu ID-ul responsabilului ca să eliminăm acele SameID și cu rezultatele anterioar obținute mai sus. Ceea ce nu am descoperit încă este cum determini care sunt rezultatele de mai sus. O posibilă soluție este eliminarea ranzomizării.

2. A doua cerință: Distribuirea fiecăruia ca partener trebuie facută în mod echilibrat;

Asta înseamnă că dacă un angajat a primit deja un task, ar trebui să alocăm altora care nu au primit deja, și care nu au același ID cu cel al resposabilului. Numărul de review-uri alocate este specificat în tabelul de Angajați sub forma unui countif din tabelul de task-uri.

Aici nu am nici o idee, dar mai investigăm. :)

[/UPDATE]

[UPDATE 21.01.2015 H22:00]

Așa cum am promis revin cu update-ul zilei la această problemă a combinațiilor unice. Personal nu am reușit să mai ”sap” după soluții pentru problemele din Verdictul anterior dar am primit o soluție surprinzător de frumoasă de la un fost coleg de muncă.

Ciprian S. propune o soluție cu o funcție de tip Array care rezolvă cu o uninicitate a combinațiilor foarte mare problema duplicatelor din problema 1 a verdictului. Rămâne deschisă problema 2 – Distribuirea echilibrată a reviewer-ilor pe task-urile deschise.

De-a dreptul spectaculos în soluția lui Ciprian este modul în care a tratat condiția de unicitate. Eu vă prezentasem acea formulă ”sefe”: SINH(). El a găsit o metodă mult mai simplă și anume concatenarea între cel mai mic număr dintre ID-ul Responsabilului pe task și ID-ul responsabilului pentru Review. Din punctul meu de vedere, faptul că știam puțină matematică prezentând o funcție de mare nișă pălește în fața simplității geniale de a alipi minimul și maximul unui număr pentru determinarea duplicității unei combinații.

Chiar dacă în schimbul de mailuri Ciprian mi-a adus aminte de o perioadă din mileniul trecut când lucram ca tehnoredactor la PIM, la el a ajuns problema prin intermediul unei puternice comunități de Office din România: http://www.itlearning.ro/forum/viewtopic.php?f=99&t=7353. În prezent Ciprian este economist la o companie din Iași.

Dar cum rigoarea academică nu lasă o soluție să treacă fără a o întoarce pe toate părțile am găsit relativ repede o excepție în funcționarea corectă a validării unicității combinațiilor. Priviți cu atenție imaginea: În cazul perechilor 1-1111 și 11-111 avem o duplicitate la metoda alipirii.

image

Și dacă am trecut la teste, am descoperit că nici SINH()-ul nu este suficient de bun pentru numere mari pentru că ultimul număr care poate fi interpretat în Excel de SINH() este 709!

Soluția ar fi să lucrăm cu materialul clientului: adică alocarea reviewer-ilor să se facă numai din lista de angajați disponibili fără randomizare, iar formula lui Ciprian pare cea mai corectă până acum pentru această situație:

=IFERROR(SMALL(IF(Nom[Index]<>[@[Cod_R]];IF((COUNTIF($D$1:D1;Nom[Index]&[@[Cod_R]])+COUNTIF($D$1:D1;[@[Cod_R]]&Nom[Index]))=0;Nom[Index]));RANDBETWEEN(1;$F$1-1-COUNTIF(B$1:C1;[@[Cod_R]])));””)

Fișierul Excel cu soluția lui Ciprian îl puteți accesa aici: https://onedrive.live.com/view.aspx?cid=6EC38785F56DAE91&resid=6EC38785F56DAE91%21360595&app=Excel sau în folderul:  https://onedrive.live.com/?cid=6EC38785F56DAE91&id=6EC38785F56DAE91%212853 cu numele: Combinații unice – Ciprian S.xlsx

Inițiatorul, cel care a născocit problema este bucuros de soluția lui Ciprian dar mai trebuie rezolvată problema alocării egale a reviewirilor din lista și cu speranța că nu vor exista situații de exepție genul: 1-1111.

Personal voi încerca să îmbunătățesc soluția mea, cu gandul la faptul că uneori tabelele relaționale sunt mult mai utile pentru asta. :) Ar fi util să întrebăm ceva specialiști în SQL cum ar trata subiectul? :)

[/UPDATE]

[UPDATE 23.01.2012 H15]

Se pare că în final avem o rezolvare acceptabilă a problemei oferită de Marius M. ca o continuare a soluției inițiale a lui Ciprian S.

Ciprian a pus mai multe update-uri pe site-ul http://www.itlearning.ro/forum/viewtopic.php?f=99&t=7353 dar se pare că Marius a găsit optimul de alocare a ID-urilor cu cea mai mică rată de dubluri, plus că reușește să facă alocarea echilibrată a reviewer-ilor în listă.

Soluția propusă de Marius M. poate fi consultată la adresa: https://onedrive.live.com/edit.aspx?cid=6EC38785F56DAE91&resid=6EC38785F56DAE91%21361092&app=Excel

sau în folderul  https://onedrive.live.com/?cid=6EC38785F56DAE91&id=6EC38785F56DAE91%212853 cu numele: Combinații unice – Marius M.xlsx

Un preview cu modulul testat al aplicației inițiate de Ciprian S și continuate de Marius M.

Solutie_Marius

Mesajul complet a lui Marius care explică modul de rezolvare:

”V-am atasat solutia pe combinatii, am continuat pe solutia oferita de Ciprian, (care e foarte faina, si de la care am invatat foarte multe, nu stiam ca pot face asa ceva cu referinte structurate), dar am adaugat verificarea duplicatelor fara nici o concatenare, si fara sinus, ci cum v-am scris pe blog, cu COUNTIFS, o verificare pe randurile anterioare. Ciprian a mai propus o rezolvare cu concatenare, dar are limite, solutia asta cu COUNTIFS nu are nici o limita, si nici o exceptie.

Cel mai usor vedeti in coloana E (Status).

Apoi am propus si o incercare de distribuirie echilibrata, anume verific count-urile id-urilor atribuite pana la randul curent, si iau in considerare pentru asignare doar id-urile care au fost asignate cel mai putin. De exemplu, pana la randul curent toate id-urile au fost asignate, dar majoriatea de mai multe ori, iar doua id-uri cate o data fiecare, le iau in considerare pentru asignare cu randbetween doar pe cele 2.

Dand de mai multe ori F9, am observat ca uneori ramane un singur id cu cele mai putine asignari, dar daca il asigneaza se incalca conditia de unicitate, si atunci imi da eroare.

Vreau sa va multumesc pentru problema.”

Marius este absolvent al specializării de Informatică Economică și actualmente lucrează la http://www.hartehanks.com/

Mulțumim Marius! 

[/UPDATE]

Problema rămâne deschisă. Dacă peste timp vor mai apărea cititori ai acestui articol care vor avea soluții îmbunătățite nu ezitați să mă contactați. Chiar ar fi interesante analogii cu bazele de date sau de ce nu cu VBA. :)

În cazul în care mai aveți probleme faine de Excel și pe care ați dori să le spuneți unor dezbateri / soluții publice aștept cu interes provocările dumneavoastre.

 

29 de gânduri despre „Excel – Problemă cu combinații unice [UPDATED 23.01 H15:44)”

  1. „Se dă o echipă formată dintr-un număr de membrii fără a exista un număr finit: A, B, C, D, E, F, G, H etc.”

    Ce Dumnezeu facem bloguri, rezolvam probleme dar nu stim sa scriem romaneste… acel „membrii” ar trebui sa fie doar MEMBRI adica doar un singur i la sfarsit.
    Poate e bine sa invatati limba romana si abia apoi sa faceti bloguri….

    Apreciază

    1. Mulțumesc pentru atenționare. În legătură cu fondul problemei aveți alte comentarii? Aștept cu interes soluția dumneavoastră. :)

      Apreciază

      1. Scuze, nu am vrut sa fie o critica dura acea atentionare dar constat cu multa mahnire, ca multi oameni posteaza pe bloguri sau aiurea, si sunt total agramati, dar isi dau totusi cu parerea – nu este cazul acestui site – cand, de bun simt?? ar trebui sa nu posteze.
        „Cred” varianta cu TYPO numai ca acolo nu apar dezacorduri, deh si eu sunt IT-ist.
        Am remarcat fina „ironie-intepatura” si am sa ma gandesc la o solutie a problemei puse.

        Apreciază

  2. Soluția sau soluțiile vor fi prezentate după ora 22:00. ”Anonimizat” ca de obicei. :)

    Apreciază

  3. Deja mi-e frica de Profesorul! Sper sa nu citeasca ceva si pe blogul meu! Am mari probleme cu virgulele!

    Apreciază

    1. Diana, dl. Profesor are dreptate. Membrii cu 2 de i este incorect. Noi cei din IT o punem pe seama typo-mistake si trecem mai departe.
      In fapt greseala este una de finete iar textul nu este destinat publicării academice. In concluzie dumnealui a fost cam exigent in a descalifica întreg articolul sau situl.
      Nu mi-au plăcut niciodată profesorii care nu pun 5. :)

      Apreciat de 2 persoane

      1. „In fapt greseala este una de finete iar textul nu este destinat publicării academice.”
        Chiar si asa daca este in spatiul public ar trebui sa fie corect scris. Nu putem scrie orice si oricum si nu ma refer la esenta lucrului scris.
        „In concluzie dumnealui a fost cam exigent in a descalifica întreg articolul sau situl.”
        Imi pare rau daca asa s-a inteles. Eu nu am vrut sa descalific nici articolul si nici situl.

        Apreciază

  4. Intrebare: Care este relatia intre nr. task-uri si nr. angajati? Avem un numar finit de angajati, dar cate task-uri, mai multe sau mai putine decat numarul de angajati? Responsabil-Reviewer este perechea angajat A-B?

    Apreciază

    1. Diana, nu știm nici numărul de angajați, nici numărul de task-uri. Pot fi mulți sau puțini. Matematic vorbind, cu cât avem mai puțini angajați cu atât avem mai puține combinații unice. Unicitatea numărului de task-uri o putem determina cu un combinări de numărul de angajați luați câte doi.
      Orice angajat poate fi și responsabil și reviewer numai că dacă A este Responsabil și B este reviewer pentru task-ul 1, nu poate exista un alt task n care să conțină tuplul A-B sau B-A.
      Până acum am primit o soluție foarte interesantă cu formule foarte simple.
      Mai aștept! :)

      Apreciază

      1. Intr-adevar, problema este una clasica, de generare a combinarilor de n luate cate 2. Raspund provocarii cu intarziere dar, n-am avut timp sa reflectez la problema propusa. Nu sunt adepta utilizarii functiilor de tip Random („daca un eveniment se poate intampla, atunci sigur se intampla” zic eu, parafrazand una din legile lui Murphy) mai ales ca sunt matematician (asta, ca sa stii ca nu din acest motiv am intrebat despre numarul de angajati si task-uri ci, am vrut sa stiu daca intereseaza numarul de task-uri sau le generam pe toate. Poate, era necesar un numar, sa zicem, de 6 task-uri din 300 posibile si, atunci, problema se schimba). Din punctul meu de vedere, problema necesita VBA (pentru obtinerea unor structuri repetitive, de tipul clasicului FOR). Daca va este de folos, am scris codul de generare a combinarilor de n angajati luati cate 2 (a tuturor task-urilor) si, in acest moment, se indeplineste si cerinta de unicitate a perechilor (combinarile exclud permutarile) si cea de alocare ecilibrata (fiecare angajat este alocat de n-1 ori). In cazul in care sunt si alte „constrangeri” se pot adauga de la acest punct de plecare. Fisierul:
        https://drive.google.com/file/d/0B_7KnZg5YkyWM0dsN25ydkM5VGc/view?usp=sharing
        Daca nu este OK ti-l trimit pe email.
        Numai bine,
        Diana

        Apreciază

  5. Sper sa puneti si raspunsul, ca mi-am batut toata ziua capul.
    Diana, numarul maxim de taskuri cred ca e combinari de numar de angajati luate cate 2.

    Apreciază

    1. Marius, sigur ca publicam. E grea problema dar nu imposibilă. ;) Eu am rezolvat cu ID-uri.

      Apreciază

  6. Da, la prima parte mi-a iesit, cu COUNTIFS.

    =IF(OR(COUNTIFS(tblTasks[[#Headers],[RespID]]:tblTasks[[#This Row],[RespID]],tblTasks[[#This Row],[RespID]],tblTasks[[#Headers],[RevID]]:tblTasks[[#This Row],[RevID]],tblTasks[[#This Row],[RevID]])>1,COUNTIFS(tblTasks[[#Headers],[RespID]]:tblTasks[[#This Row],[RespID]],tblTasks[[#This Row],[RevID]],tblTasks[[#Headers],[RevID]]:tblTasks[[#This Row],[RevID]],tblTasks[[#This Row],[RespID]])>0),”Duplicate”,”OK”)

    sau echivalentul fata tabela:
    =IF(OR(COUNTIFS($B$2:B3,B3,$D$2:D3,D3)>1,COUNTIFS($B$2:B3,D3,$D$2:D3,B3)>0),”Duplicate”,”OK”)

    Cu ce mi-am batut capul e cum sa faci in asa fel incat la oricare F9 sa nu apara duplicate. Si singura modatlitate care-mi vine in minte e sa iei valorile de PersonID, si sa le tot excluzi dintr-un array, pe care apoi sa-l folosesti in functie de valoare Respid, doar ca fara sa faci functii in vba nu prea stiu cum ar putea fi in excel.

    Mi-a iesit si sa nu dea sameid cand se aloca RevID, daca id-urile sunt consecutive.

    =IF(tblTasks[[#This Row],[RespID]] = 1,RANDBETWEEN(2,$L$1),IF(tblTasks[[#This Row],[RespID]] = $J$1,RANDBETWEEN(1,$J$1-1),CHOOSE(RANDBETWEEN(1,2),RANDBETWEEN(1,tblTasks[[#This Row],[RespID]]-1),RANDBETWEEN(tblTasks[[#This Row],[RespID]]+1,$J$1))))

    Apreciază

      1. :) Nu va mai sunt student de mult. V-am vazut problema pe fb, si aveam o zi linistita la munca.

        Apreciază

  7. Stiu Marius ca nu mai esti student. Problema se adreseaza in special nestudentilor. :) Tocmai de aceea este si un premiu pus la ”bătaie”. :)

    Apreciază

    1. Am vazut firul. :) Da solutia lui Ciprian pare a fi cea mai bună până acum. :) Mi-a plăcut în special faza că a înlocuit acel SINH() cu ceva mult mai simplu… la care eu nu mersem cu gândul. Revin cu soluția lui după ora 22. Pentru cei interesați pot vedea soluția pe ITLearning.ro. ;)

      Apreciază

  9. @Profesorul: Mulțumim frumos pentru comentarii, criticile constructive și aprecieri. Personal fac multe greșeli din cauză că mă grăbesc să scriu repede pentru a nu pierde idea din minte. Dar faza cu membrii, într-adevăr nu o știam, chiar dacă am luat-o cu copy/paste dintr-un mail. :)
    Problema expusă în acest articol se pare că dă bătăi de cap… iar când soluția nu iese din prima, mulți renunță prea rapid la a găsi o soluție sau o explicație la un NU se poate. :)
    PS. Ironia este scutul meu, iar zâmbetul mi-e lancea, pentru că zâmbind obții mai mult! :)

    Apreciază

  10. Referitor la asigurarea unicității: corectă observația: se corectează prin înlocuirea formulei din coloana ajut cu: TEXT(MIN(act[@[Cod_R]:[Cod_S]]),”000″)&TEXT(MAX(act[@[Cod_R]:[Cod_S]]),”000″), iar a formulei matriceale din Cod_S cu:
    {=IFERROR(SMALL(IF((Nom[Index][@[Cod_R]])*((COUNTIF($D$1:D1,TEXT(Nom[Index],”000″)&TEXT([@[Cod_R]],”000″))+COUNTIF($D$1:D1,TEXT([@[Cod_R]],”000″)&TEXT(Nom[Index],”000″)))=0)*((COUNTIF([Cod_R],Nom[Index])+COUNTIF(C$1:C1,Nom[Index]))<$I$4),Nom[Index]),RANDBETWEEN(1,$I$1-1-(COUNTIF([Cod_R],[@[Cod_R]])+COUNTIF(C$1:C1,[@[Cod_R]])))),"")} (OBS. am presupus N<1000, la N=999 avem 498.501 combinații posibile!)

    Referitor la distribuția echilibrată: dacă N – nr oameni, T număr de taskuri, atunci x=2T/N este numărul mediu de taskuri. Definim p = roundup(x*toleranța,0) numărul maxim acceptabil de taskuri pentru un om, și introducem aceasta in matricea de selecție pentru small. În acest mod ne-am asigurat că un om nu e selectat exccesiv de mult. În privința celor neselectați, momentan nu am o soluție să-l conving pe randbetween() sa favorizeze un numar sau altul din intervalul de selectie. mai in glumă, mai în serios se rezolva cu F9, până se obține o soluție rezonabilă.

    Referitor la intervalele de lucru: pentru un N dat, există N(N-1)/2 posibilități de combinare. Deci trebuie avut grijă cu N-ul dat. Pe de altă parte fiind formule matriceale ce implică și countifuri, dacă lungimea tabelelor cu taskuri și oameni crește, timpul crește exponențial.

    În cod se poate parcurge un algoritm de mai multe ori optimizând diferite rezultate. În Excel (cu excepția situațiilor în care deliberat se alege calculul recursiv) rezultatul se obține la prima strigare. E normal să nu poți obține eficiența dintr-un cod dedicat problemei, dar pentru un crochiu își face treaba excelent!.

    Apreciază

  12. Pingback: Transformare numere in litere in Excel si SharePoint | Valy Greavu's Live Blog

Comentariile nu închise.

Blog la WordPress.com.

SUS ↑