BitCell

Pentru ca am primit solicitari privind algoritmul de generare de combinari in ordine lexicografica,



probabil va intrebati la ce foloseste asta... va urma.

Explică puţin şi ce ai făcut. Din moment ce ţi s-a cerut să scrii despre un anume subiect, e clar că scopul topic-ului este unul educaţional şi nu demonstrativ. Ia fiecare linie de cod în parte şi explică ce face, care-i este rolul, cum se leagă de restul codului. Practic, ăsta e şi obiectivul (mini)tutorialelor.

^ Referitor la algoritmul care returneaza cite pozitii au in comun 2 vectori ordonati crescator:

Sa luam un exemplu

v1 = (1, 3, 7, 8, 9);
v2 = (1, 5, 7, 8);

Variabila i parcurge pozitiile lui v1, respectiv j pozitiile lui v2.
Initial i:=1; j:=1; adica prima pozitie din vectori.
Daca v1[i]=v2[j] atunci avem un element in comun, incrementam contorul de elemente comune, deasemenea, pe i si pe j.
Daca v1[i]>v2[j] avem in v1 un element mai mare, si pentru ca vectorii sunt ordonati crescator, incrementam j (adica o sa citim urmatorul element mai mare din v2)
Restul cred ca e intuitiv, si se poate intelege din cod.

p.s. Cineva mi-a cerut ca ii fac un program de loto cu 45 de numere, in loc de asta. Am considerat ca e mai bine sa public ce algoritmi am folosit, pentru ca fiecare sa isi faca ce doreste. Va urma si algoritmul folosit pentru scheme reduse.

---

L.E. (-- 27 Apr 2010, 13:42 --)

Copie email trimis (catre persoana care solicita ceva similar cu ceea ce deja am publicat):

Descrierea algoritmului folosit:
Se genereaza combinarile de n luate cite k, in ordine lexicografica. (orice student la informatica ar cam trebui sa stie ce inseamna)
Prentru fiecare, se verifica conditia de acoperire, simplificat, cite elemente are in comun cu variantele deja incluse in lista.
Daca nu are in comun 2,3,4 numere (cit vrei) cu ce e deja in lista, se adauga.
Asta e algoritmul „prima neacoperita” realizat de mine, si recunosc ca nu e cine stie ce avansat, doar asigura gradul de ortogonalitate a vectorilor (variantelor in cazul nostru).

La solicitarea unor utilizatori, explic mai in detaliu:

C(n,k) = n! / ( k! *(n-k)! );
n! = 1*2*3*..*n;
n! se citeste n factorial.

hai sa luam un exemlu: combinari de 3 luate cite 2:
1 2
1 3
2 3

combinari de 5 luate cite 3
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

Din ce am studiat eu: numarul de repetari al fiecarui element este C(n-1,k-1);
Pentru o schema redusa optima, toate variantele difera de celelalte pe k-a+1 pozitii, (a este la alegere), si numarul de repetari al fiecarui element este acelasi.