Generarea combinarilor

Generarea combinarilor

Fie o multime oarecare de n elemente care poate fi pusa intr-o corespondenta biunivoca cu multimea A=. Ne propunem sa determinam toate m-combinarile (m£n) ale multimii A (submultimi de m elemente ale multimii A). Vom rezolva problema, nerecursiv, pornind de la m-combinarea V=(1,2,,m) determinand succesiv toate m-combinarile ordonate lexicografic crescator.

Fie V=(v₁,v₂,,v_m) o m-combinare oarecare, atunci m-combinarea urmatoare in ordine lexicografica crescatoare se obtine astfel:

a)      se determina cel mai mare indice i satisfacand relatiile:

v_i<n-m+i,    v_i+1=n-m+i+1,, v_m-1=n-1, v_m=n. (1)

b)      se trece la vectorul urmator:

(v₁, , v_i-1,v_i+1,v_i+2, , v_i+n-i+1);

c)      daca nu exista un astfel de indice i (care sa satisfaca relatiile (1)) inseamna ca vectorul V contine ultima m-combinare si anume: (n-m+1,n-m+2, ,n).

Dam in continuare o functie C care genereaza o m-combinare cu n elemente avand ca parametru cod o variabila booleana care pentru valoarea 0 genereaza prima m-combinare iar pentru valoarea 1 genereaza urmatoarea m-combinare. Functia comb reintoarce valoarea 1 daca s-a generat o m-combinare oarecare si valoarea 0 daca s-a generat ultima m-combinare (in acest caz cod are valoarea 0). Se va folosi un vector global v in care se genereaza m-combinarile.

#define dim 50

#include <stdio.h>

int v[dim+1], n, m;

// functia generatoare a m-combinarilor

int comb(cod)

int cod;

i=m+1;

do // cautarea indicelui i pentru satisfacerea relatiilor (1)

while (v[i] >= n‑m+i);

if (i)

else return (0);

void main(void)

getche();