Sumbultimi si partitii

Scopul lucrarii. Se prezinta notiunile legate de generarea tuturor submultilor unei multimi finite precum si modul in care se abordeaza problemele de combinatorica care se pot solutiona prin analizarea tuturor submultimilor unei multimi finite. De asemenea se analizeaza problemele legate de folosirea si generarea partitiilor la rezolvarea unor probleme de combinatorica care se preteaza la abordarea cu partitii.

Notiuni teoretice

2.1. Submultimile unei multimi

Fie multimea A cu n elemente. O submultime B a lui A este orice multime ale carei elemente apartin toate lui A. Submultimile B ale lui A care sunt distincte de A se numesc submultimi proprii ale lui A. Multimea vida, , este multimea care nu contine nici un element. Printre submultimile lui A este si multimea vida.

Numarul de submultimi ale unei multimi este 2ⁿ. De exemplu, daca avem multimea A = , submultimile lui A sunt

Submultimile multimii A pot fi considerate ca elementele unei noi multimi numita multimea partilor lui A, notata cu P(A). Printre elementele multimii P(A) se afla submultimile A, , daca a I A. Pentru multimea A = , P(A) = , }.

2.a. Algoritmul de generare iterativa a elementelor unei submultimi

Fiind data o multime A cu n elemente se pune problema determinarii celor 2ⁿ submultimi ale multimi A. Pentru reprezentarea unei submultimi se va folosi vectorul caracteristic. Deci trebuie sa se genereze toate combinatiile de succesiuni de 0 si 1 ce se pot forma pe n pozitii, unde n reprezinta cardinalul multimii date.

Pentru a obtine toate aceste conbinatii se genereaza de fapt toate componentele produsului cartezian A x A x A x x A, unde A=. Se va folosi un vector v=(v₁, v₂, , v_n), cu v_i=0 sau 1, pentru 1 i n. Initial toate componentele vectorului v sunt initializate la 0, adica v=(0, 0, , 0).Urmatorul vector generat va fi v=(0, 0, , 0, 1), apoi v=(0, 0, , 0, 1, 0), s.a.m.d. Ultimul element generat va fi v=(1, 1, , 1, 1, 1), dupa care procesul de generare se incheie.

Procedurile de initializare si generare sunt prezentate in continuare:

procedura INIT(v, n, ig) este

┌ pentru i=1, n, 1 repeta

│ v_i <- 0

└

ig <- 1

sfarsit

procedura GEN(v, n, ig) este

gasit <- 0

i <- n

┌ cat_timp (i>n) si (gasit=o) repeta

│ ┌ daca v_i=0 atunci

│ │ v_i <- 1

│ │ gasit <-- 1

│ │altfel

│ │ v_i <- 0

│ │ i <- i-1

│ └

└

┌ daca gasit=0 atunci

│ ig <- 0

└

sfarsit

Descriere prezentata mai sus genereaza toate submultimile dorite in ordine lexicografica (relatia de ordine se refera la reprezentarea lor prin vectorul caracteristic). Echivalentul binar al reprezentarii unei submultimi pe parcursul generarii variaza in intervalul 0, , 2ⁿ-1.

Pentru a evita cele doua conditi (i>0) si (gasit=0) in procedura GEN pentru aflarea urmatoarei combinatii, se poate folosi o cautare secventiala cu santinela. Santinela este asezata pe pozitia de indice 0 a vectorului v si are valoarea 0. In acest caz procedurile de initializare si generare au forma:

procedura INIT (n, v, ig) este

┌ pentru i=0, n, 1 repeta

│ v_i <- 0

└

ig <- 1

sfarsit

procedura GEN (n, v, ig) este

i <- n

┌ cat_timp v_i = 1 repeta

│ v_i <- 0

│ i <- i-1

└

┌ daca i = 0 atunci

│ ig <- 0

│ altfel

│ v_i <- 1

└

sfarsit

Exemplu rezolvat. Intr-o grupa se afla n de studenti dintre care nb baieti si restul fete. Sa se determine toate grupurile de studenti din aceasta grupa care contin fete sau baieti astfel incit numarul baietilor sa fie mai mare cu cel mult dif fata de numarul fetelor.

Reprezentarea unui grup se face prin intermediul vectorului caracteristic, iar selectia elementului dintr-un grup se face dupa urmatoarea conventie: baietii se identifica prin numere intre 1 si nb, iar fetele prin numere intre nb+1 si n. La baza algoritmului sta urmatoarea idee: se vor genera toate submultimile si se vor selecta acele grupuri care indeplinesc conditia impusa. In acest scop se vor cumula numarul de baieti, respectiv de fete din grup.

Procedurile de initializare si generare au fost prezentate anterior urmind sa se detalieze doar procedura de prelucrare.

procedura PREL(v, n, nb, dif) este

n1 <- 0

n2 <- 0

┌ pentru i=1, nb, 1 repeta

│ ┌ daca v_i=1 atunci

│ │ n1 <- n1+1

│ └

└

┌ pentru i=nb+1, n, 1 repeta

│ ┌ daca v_i=1 atunci

│ │ n2 <- n2+1

│ └

└

┌ pentru i=1, n, 1 repeta

│ ┌ daca v_i=1 atunci

│ │ scrie i

│ └

└

┌ daca (n1-n2>=0) si (n1>=n2+dif) atunci

│ scrie 'Este solutie'

│ altfel

│ scrie 'Nu este solutie'

└

sfarsit

Programul principal in pseudocod va arata astfel:

scrie 'Introduceti numarul de copii'

citeste n

scrie 'Introduceti numarul de baieti'

citeste nb

scrie 'Introduceti diferenta'

citeste dif

executa INIT(n, v, ig)

┌ cat_timp ig 0 repeta

│ executa PREL(v, n, nb, dif)

│ executa GEN(n, v, ig)

sfarsit

In programele ce urmeaza s-a implementat varianta cu santinela.

Pentru cazul particular, cind grupul are 4 copii, dintre care 2 baieti iar diferenta baieti-fete este 1 rezultatele vor apare astfel:

Introduceti numarul de copii: 4

Introduceti numarul de baieti: 2

Introduceti diferenta: 1

Nu este solutie

Nu este solutie

Nu este solutie

Este solutie

Nu este solutie

Nu este solutie

Nu este solutie

Este solutie

Nu este solutie

Nu este solutie

1 2 3 4 Nu este solutie

Rezolvarea problemei in Pascal se afla in Anexa A.L10.1 si in C in Anexa B.L10.1.

2.1.b. Algoritmul de generare recursiva a elementelor unei submultimi

Generarea recursiva a elementelior produsului cartezian are la baza metoda generala de programare backtracking.

Vom folosi acelasi vector v care contine cate un element al produsului cartezian. Procedura PREL(v,n ) va prelucra conform aplicatiei vectorul v.

Algoritmul de generare arata astfel:

procedura GEN_SUBM_REC (i) este

┌ pentru j=v(i-1)+1,n-m,1 repeta

│ v_i <- j

│ daca i< m atunci

│ executa GEN_SUBM_REC (i+1)

│ else

│ executa PREL(v,n)

└

sfarsit

unde : v este un vector de n componente iar m este cardinalitatea submultimi generate. Vectorul v se considera global pentru a nu incarca stiva la apelurile recursive.

Programului principal pentru rezolvarea aceleeasi probleme cara apeleaza procedura GEN_SUBM_REC() va arata astfel:

scrie 'Introduceti numarul de copii'

citeste n

scrie 'Introduceti numarul de baieti'

citeste nb

scrie 'Introduceti diferenta'

citeste dif

v(0)<-1

pentru k=1,n,1 repeta

executa GEN_SUBM_REC(1)

stop

2. 2. Generarea partitiilor unei multimi finite

Fiind data o multime finita A, se defineste ca fiind o partitie a sa, sirul de submultimi nevide si disjuncte, doua cite doua, numite si clase, pentru care are loc proprietatea:

A=A₁ U A₂ U .. U A_k si

A_i A_j = pentru 1 i, j n si i j.

De exemplu, pentru multimea se poate considera partitia , , .

O problema o constituie modul de reprezentare a unei partitii folosind posibilitatile oferite de limbajele de programare uzuale. Se prezinta mai multe modalitati de reprezentare, toate folosind un vector v cu n componente:

a) fiecare componenta a vectorului contine un reprezentant al clasei din care face parte elementul i, de obicei cel mai mic. Pentru exemplu anterior, vectorul este v = (1, 1, 3, 3, 3, 6);

b) fiecare componenta v_i a vectorului desemneaza numarul de clasa din care face parte elementul i, clasele fiind numerotate in ordine crescatoare dupa primul element, element care are cea mai mica valoare. Pentru exemplul considerat vectorul v este (1, 1, 2, 2, 2, 3);

c) vectorul v contine in ordine elementele claselor A₁, .. , A_k, elementele claselor fiind ordonate crescator, iar clasele fiind numerotate in ordine crescatoare a primului element al fiecarei clase. Pentru a se putea face mai usor distinctie intre partitii se reprezinta primul element cu semn schimbat. Pentru exemplul dat se considera vectorul v este (-1, 2, -3, 4, 5, -6);

d) analog cu reprezentarea de la punctul c) cu deosebirea ca toate elementele unei clase au acelasi semn, iar doua clase consecutive contin elemente cu semne contrare. Partitia considerata anterior conduce la vectorul v=(1, 2, -3, -4, -5, 6).

2.2.a. Algoritmul de generare iterativa a partitiilor unei multimi

Fie multimea si o partitie oarecare a sa A₁, A₂.. , A_k. Dintr-o astfel de partitie a multimii se pot obtine k+1 partitii ale multimii astfel:

A₁, , A_k,

A₁, , A_k U

A₁ U , .. , A_k .

Acest procedeu de generare sugereaza algoritmul de mai jos.

1. Se pleaca de la partitia , , si se genereaza pe rind toate partitiile pina se ajunge la partitia

2. Partitiile se genereaza pe rind una din alta astfel:

a) se determina cel mai mare element k care nu este in aceeasi clasa cu 1. Elementele care sunt mai mari ca acesta trebuie sa formeze clase distincte;

b) se determina clasa predecesoare clasei in care se afla k si se introduce in aceasta clasa.

In continuare se prezinta procedurile INIT si GEN care folosesc o reprezentare a partitiilor de tip a).

procedura INIT (v, n, ig) este

┌ pentru i=1, n repeta

│ v_i <- i

└

ig <- 1

sfarsit

procedura GEN (v, n, ig) este

k <- n

gasit <- 0

┌ cat_timp (k > 0) si (gasit = 0) repeta

│ ┌ daca v_k = 1 atunci

│ │ gasit <- 1

│ │ altfel

│ │ v_k <- k

│ │ k <- k-1

│ └

└

┌ daca gasit = 1 atunci

│ j <- 1

│ ┌ pentru i=2, k-1, 1 repeta

│ │ ┌ daca (v_i > j) si (v_i < v_k) atunci

│ │ │ j <- v_i

│ │ └

│ └

│ v_k <- j

│ altfel

│ ig <- 0

└

sfarsit

Atunci cind se solicita cautarea clasei precedente celei in care apare k trebuie sa se tina cont de faptul ca reprezentantul ei este mai mic decit k, precum si de faptul ca v₁ = 1.

Algoritmul descris anterior are dezavantajul de a fi consumator de timp atunci cind se realizeaza cautarea celui mai mare element k pentru care v_k diferit de 1. Ineficienta algoritmului deriva tocmai din faptul ca conditia de cautare este destul de complicata. O varianta mai eficienta o constituie cautarea cu santinela. In acest caz santinela trebuie asezata pe pozitia k=0, iar valoarea trebuie sa fie o valoare diferita de 1. Deci algorimul poate fi realizat si astfel:

procedura INIT (v, n, ig) este

┌ pentru i=0, n, 1 repeta

│ v_i <- i

└

ig <- 1

sfarsit

procedura GEN (v, n, ig) este

k <- n

┌ cat_timp v_k = 1 repeta

│ v_k <- k

│ k <- k-1

└

┌ daca k 0 atunci

│ j <- 1

│ ┌ pentru i=2, k-1, 1 repeta

│ │ ┌ daca (v_i > j) si (v_i < v_k) atunci

│ │ │ j <- v_i

│ │ └

│ └

│ v_k <- j

│ altfel

│ ig <- 0

└

sfarsit

Exemplu rezolvat. Se da un grup de copii format din fete si baieti. Sa se genereze toate posibilitatile de impartire a grupului in subgrupuri distincte si nevide de persoane astfel incit sa se imparta toate persoanele si in plus, intr-o clasa, numarul fetelor sa fie mai mare sau egal cu numarul baietilor.

Se considera ca grupul este format din n persoane. Pentru a facilita introducerea datelor, se considera persoanele ordonate asfel incit baietii au numere de ordine intre 1 si m, iar fetele intre m+1 si n. Procedurile de initializare si generare sunt identice cu cele prezentate in cazul general, singura procedura ce trebuie detaliata fiind cea de prelucrare.

procedura PREL (v, n, m) este

scrie 'Partitia: '

┌ pentru i=1, n, 1 repeta

│ fete(i) <- 0

│ baieti(i) <- 0

│ ┌ pentru j=i, n, 1 repeta

│ │ ┌ daca v_j = i atunci

│ │ │ scrie j

│ │ │ ┌ daca j m atunci

│ │ │ │ baieti(i) <- baieti(i)+1

│ │ │ │ altfel

│ │ │ │ fete(i) <- fete(i)+1

│ │ │ └

│ │ └

│ └

└

gasit <- 0

┌ pentru i=1, n, 1 repeta

│ ┌ daca v_i = 1 atunci

│ │ ┌ daca fete(i) < baieti(i) atunci

│ │ │ gasit <- 1

│ │ └

│ └

└

┌ daca gasit = 1 atunci

│ scrie 'Nu este solutie'

│ altfel

│ scrie 'Este solutie'

└

sfarsit

Programul principal in pseudocod va arata astfel:

scrie 'Introduceti numarul de copii'

citeste n

scrie 'Introduceti numarul de baieti'

citeste m

executa INIT(v, n, ig)

┌ cat_timp ig 0 repeta

│ executa PREL(v, n, m)

│ executa GEN(v, n, ig)

sfarsit

Pentru cazul particular cind grupul esre formar din 4 copii, iar numarul de baieti este 2 rezultatele se vor afisa astfel:

Introduceti numarul de copii: 4

Introduceti numarul de baieti: 2

Partitia Nu este solutie

Partitia Nu este solutie

Partitia Nu este solutie

Partitia Este solutie

Partitia Nu este solutie

Partitia Nu este solutie

Partitia Este solutie

Partitia Este solutie

Partitia Este solutie

Partitia Este solutie

In programele ce urmeaza s-a implementat varianta cu santinela.

2.2.b. Algoritmul de generare recursiva a partitiilor unei multimi

Vom folosi acelasi vector v care contine cate un partitiile multimii. Procedura PREL(v,n ) va prelucra conform aplicatiei vectorul v.

Algoritmul de generare arata astfel:

procedura partitiir( k, n) este:

daca k=n+1 atunci

executa PREL();

altfel

max=0;

pentru i=1,k-1,1 executa

daca max<v[i] atunci

max=v[i];

pentru i=1,max+1,1 repeta

v[k]=i;

partitiir(k+1,n);

sfarsit   

3. Probleme propuse

1. Se considera un grup de elevi de 10 si 12 ani. Sa se genereze toate posibilitatile de impartire a grupului in subgrupuri distincte si nevide de elevi astfel incit sa se imparta toate persoanele si in plus, intr-o clasa, numarul elevilor de 10 ani sa fie mai mare sau egal cu numarul elevilor de 12 ani.

2 Intr-o grupa se afla n elevi dintre care n10 elevi de 10 ani si restul elevi de 12 ani . Sa se determine toate grupurile de elevi din aceasta grupa care contin elevi de 10 ani sau elevi de 12 ani astfel incit numarul elevilor de 10 ani sa fie mai mare cu cel mult dif fata de numarul elevilor de 12 ani.

3. Intr-o gara se afla n calatori nb barbati si restul femei. Sa grupeze cei n calatori in vagoane astfel incat numarul barbatilor sa fie mai mare cu cel mult z fata de numarul femeilor.

4. Fie cel n masini dintr-o localitate folosite in taximetrie de n1 de culoare galbena si restul de culoare alba. Sa se afiseze toate posibilitatile de impartire a celor n masini in parcari distincte si nevide astfel incat toate masinile sa fie in parcari si in plus in fiecare parcare numarul masinilor de culoare galbena este mai mare sau egal cu cel al masinilor de culoare alba.

5. Intr-un aeroport se afla n calatori nb barbati si restul femei. Sa grupeze cei n calatori in avioane astfel incat numarul barbatilor sa fie mai mare cu cel mult z fata de numarul femeilor.

6. Intr-un port se afla n calatori nb barbati si restul femei. Sa grupeze cei n calatori in vapoare astfel incat numarul barbatilor sa fie mai mare cu cel mult z fata de numarul femeilor.

7. Intr-o statiune se afla n turisti nb barbati si restul femei. Sa grupeze cei n calatori in pensiuni astfel incat numarul barbatilor sa fie mai mare cu cel mult z fata de numarul femeilor.

8. La un concurs participa n persoane nb barbati si restul femei. Sa grupeze cele n persoane in grupuri astfel incat numarul barbatilor sa fie mai mare cu cel mult z fata de numarul femeilor.

9. Intr-o librarie se afla n rechizite carti si caiete dintre care nc carti si restul caiete. Sa se determine toate standurile de prezentare de rechizite din librarie care contin carti sau caiete astfel incit numarul caietelor din fiecare stand sa fie mai mare cu cel mult dif fata de numarul cartilor

10. Intr-o parcare se afla n masini camioane si tractoare dintre care nc camioane si restul tractoare. Sa se determine toate gruparile de prezentare de masini din parcare care contin camioane sau tractoare astfel incat numarul tractoarelor din fiecare grupsa fie mai mare cu cel mult dif fata de numarul camioanelor

11. Se considera o multime de n persoane, fiecare persoana avind printre celelalte n‑1 un anumit numar de cunoscuti. Vom presupune ca relatia de cunostinta definita pe multimea persoanelor este reflexiva. Sa se determine un grup de persoane din cele n de dimensiune maxima astfel incit oricare doua persoane din acest grup sa se cunoasca intre ele.

12. Problema submultimilor de suma data: Se considera n+1 numere pozitive a₁, a₂, , a_n si M. Sa se determine toate submultimile multimii cu suma elementelor egala cu M.

Anexa A

Anexa B

B.L10.1

Intr-o grupa se afla n de studenti dintre care nb baieti si restul fete. Sa se determine toate grupurile de studenti din aceasta grupa care contin fete sau baieti astfel incit numarul baietilor sa fie mai mare cu cel mult dif fata de numarul fetelor. (varianta iterativa)

#include <stdio.h>

# include <conio.h>

#define NMAX 25

int ig,v[NMAX],n;

void INIT()

void GEN_SUBM()

void PREL(int nb,int dif)

void main()

B.L10.2

2. Intr-o grupa se afla n de studenti dintre care nb baieti si restul fete. Sa se determine toate grupurile de studenti din aceasta grupa care contin fete sau baieti astfel incit numarul baietilor sa fie mai mare cu cel mult dif fata de numarul fetelor. (varianta recursiva)

#include <stdio.h>

#include <conio.h>

int n,k,v[10];

int nb,dif;

void prel(int , int);

void subm(int i);

void main()

void subm(int i)

}

void prel(int nb,int dif)

B.L10.3.

3. Se da un grup de copii format din fete si baieti. Sa se genereze toate posibilitatile de impartire a grupului in subgrupuri distincte si nevide de persoane astfel incit sa se imparta toate persoanele si in plus, intr-o clasa, numarul fetelor sa fie mai mare sau egal cu numarul baietilor. (varianta iterativa)

#include <stdio.h>   

#include <conio.h>

#define DIM 25

int ig,v[DIM],n;

void INIT(int n)

void GEN()

else

ig=0;

void PREL(int m)

printf('}');

}

}

gasit=0;

for(i=1;i<=n;i++)

if(v[i]==i && fete[i]<baieti[i])

if(gasit) printf('Nu este solutien');

else printf('Este solutien');

getch();

void main()

B.L10.4

Se da un grup de copii format din fete si baieti. Sa se genereze toate posibilitatile de impartire a grupului in subgrupuri distincte si nevide de persoane astfel incit sa se imparta toate persoanele si in plus, intr-o clasa, numarul fetelor sa fie mai mare sau egal cu numarul baietilor. (varianta recursiva)

#include <stdio.h>

#include <conio.h>

#define MAX 20

int v[MAX],n,m;

void PREL(void)

printf('nPartitia ');

max=1;

for(i=2;i<=n;i++)

if (max<v[i]) max=v[i];

for (i=1;i<=max;i++)

}

printf('}');

gasit=0;

for(i=1;i<=n;i++)

if(v[i]==i && fete[i]<baieti[i])

if(gasit) printf('Nu este solutien');

else printf('Este solutien');

getch();

void partitiir(int k, int n)

void main()