Permutari, aranjamente

Permutari, aranjamente

Scopul lucrarii. Insusirea notiunile teoretice si practice legate de modul in care se abordeaza problemele care pot fi solutionate folosind:

permutarile de n elemente,

aranjamentele de n elemente luate cite m.

Notiuni teoretice

2.1. Generarea permutarilor

Fie o multime finita A cu n elemente. Aceasta multime se poate ordona in mai multe moduri. Se obtin astfel multimi ordonate care se deosebesc intre ele numai prin ordinea elementelor. Fiecare din multimile ordonate care se formeaza cu cele n elemente ale multimii A se numeste permutare a acestei multimi. In literatura de specialitate exista foarte multi algoritmi pentru generarea permutarilor.

2.1.a. Algoritmul iterativ.

Se prezinta o modalitate de generare a permutarilor in ordine lexicografica. Se pleaca de la permutarea identica p=(1, 2, , n), care este cea mai mica permutare in ordine lexicografica. Sa presupunem ca la un moment dat avem construita o permutare p=(p₁, p₂, , p_n). Se pune problema generarii unei noi permutari p'=(p₁', p₂', , p_n') care sa fie succesoarea in ordine lexicografica a acestei permutari. Se procedeaza dupa cum urmeaza:

a) Se determina cel mai mare indice i pentru care avem p_i < p_i+1 si p_i+1 > p_i+2 > p_i+3 >.> p_n. In aceste conditii este evident ca pentru a se obtine permutarea p' trebuie sa se modifice elementele de pe pozitiile p_i, p_i+1, , p_n. Modificarea acestei secvente este prezentata mai jos.

b) Deoarece p' urmeaza imediat dupa p in ordine lexicografica rezulta ca p_i trebuie inlocuit cu un element mai mare decit el. Acest element trebuie sa fie in secventa (p_i+1,.., p_n) si il notam cu p_k. El este de fapt cel mai mic element din multimea , care este mai mare decit p_i. Se schimba elementele p_i si p_k intre ele. Dupa aceasta prelucrare vectorul initial are forma:

(p₁, p₂, , p_i-1, p_k, p_i+1, .., p_k-1, p_i, p_k+1, , p_n)

In acest ultim caz ultimile n-1 elemente sunt in ordine descrescatoare. Pentru a obtine permutarea p' aceste ultime elemente se aseaza in asa fel incit sa fie ordonate crescator.

Ultima permutare generata de algoritm este p=(n, n-1, , 1).

Procedurile de initializare si generare sunt prezentate mai jos:

procedura INIT(v, n, ig) este

┌ pentru i=1, n, 1 repeta

│ v_i <- i

└

ig <- 1

sfarsit

procedura GEN(v, n, ig) este

i <- n

┌ cat_timp (i>0) si (v_i > v_i+1) repeta

│ i <- i-1

└

┌ daca i>0 atunci

│ k <- n

│ ┌ cat_timp v_i > v_k repeta

│ │ k <- k+1

│ └

│ x <- v_i

│ v_i <- v_k]

│ v_k <- x

│ m <- [(n-i)/2]

│ ┌ pentru j=1, m, 1 repeta

│ │ x <- v_i+j

│ │ v_i+j <- v_n+1-j

│ │ v_n+1-j <- x

│ └

│ altfel

│ ig <- 0

└

sfarsit

Daca se doreste folosirea pentru cautare a unei metode cu santinela, aceasta trebuie asezata pe pozitia 0 si sa aiba valoarea 0. Varianta cu santinela conduce la urmatoarele proceduri:

procedura INIT (n, v, ig) este

┌ pentru i=0, n, 1 repeta

│ v_i <- i

└

ig <- 1

sfarsit

procedura GEN (n, v, ig) este

i <- n-1

┌ cat_timp v_i > v_i+1 repeta

│ i <- i-1

└

┌ daca i = 0 atunci

│ ig <- 0

│ altfel

│ k <- n

│ ┌ cat_timp v_i > v_k repeta

│ │ k <- k-1

│ └

│ x <- v_i

│ v_i <- v_k

│ v_k <- x

│ m <- [(n-i)/2]

│ ┌ pentru j=1, m, 1 repeta

│ │ x <- v_i+j

│ │ v_i+j <- v_n+1-j

│ │ v_n+1-j <- x

│ └

└

sfarsit

Exemplu rezolvat. Sa se genereze toate posibilitatile de aranjare pe o tabla de sah de N x N a N turnuri astfel incit doua turnuri sa nu se poata lua si sa nu apara in colturile tablei de sah.

Este evident ca pe o coloana sau pe o linie nu poate sa apara decit un singur turn. Consideram ca o astfel de pozitie se poate reprezenta printr-o configuratie de forma (l₁, l₂, , l_n) unde l_i este linia pe care se afla turnul de pe coloana i. In acest caz vectorul (l₁, l₂, , l_n) reprezinta o permutare de n elemente deoarece l_i ¹ l_j oricare ar fi i, j din multimea . Ca atare se vor genera toate cele n! permutari si se vor retine acele permutari care respecta restrictiile impuse, adica cele care nu satisfac conditia l₁=n sau l₁=1 sau l_n=n sau l_n=1.

In aceste conditii procedura de prelucrare arata astfel:

procedura PREL(v, n) este

┌ pentru i=1, n, 1 repeta

│ scrie v(i)

┌ daca (v₁ ¹ 1) si (v_n ¹ 1) si (v₁ ¹ n) si (v_n ¹ n)atunci

scrie 'Este solutie'

│ altfel

scrie 'Nu este solutie'

sfarsit

Programul principal in pseudocod va arata astfel:

scrie 'Introduceti dimensiunea tablei'

citeste n

executa INIT(n, v, ig)

┌ cat_timp ig¹0 repeta

│ executa PREL(v, n)

│ executa GEN(n, v, ig)

sfarsit

Pentru cazul particular cind dimensiunea tablei este 4 rezultatele vor fi afisate astfel:

Introduceti dimensiunea tablei: 4

Nu este solutie

Nu este solutie

Nu este solutie

Nu este solutie

Nu este solutie

Nu este solutie

Nu este solutie

Este solutie

Nu este solutie

Nu este solutie

In programele ce urmeaza s-a implementat varianta cu santine­la.

2.1.a. Algoritmul recursiv.

Generarea recursiva a permutarilor are la baza metoda generala de programare backtracking.

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

Algoritmul de generare arata astfel:

procedura permut( k) este

daca k=n+1 atunci

executa PREL();

altfel

v[k]=k;

pentru i=1,k,1 repeta

c=v[i];

v[i]=v[k];

v[k]=c;

executa permut(k+1);

c=v[i];

v[i]=v[k];

v[k]=c;

sfarsit   

2.2. Generarea aranjamentelor

Fie o multime finita A cu n elemente. Daca exista m £ n atunci se pot forma multimi ordonate cu cite m elemente fiecare, in care intra numai elemente ale multiimi A.

Multimile ordonate care se formeaza cu elementele unei submultimi oarecare a unei multimi finite A, se numesc submultimi ordonate ale lui A sau aranjamente. Daca A este o multime cu n elemente atunci submultimile ordonate ale lui A avind fiecare cite m elemente, 0 £ m £ n se numesc aranjamente de n elemente luate cite m.

Numarul acestor grupe este A_n^m. Doua aranjamente de n elemente luate cite m se deosebesc prin natura elementelor sau prin ordinea lor.

2.2.a. Algoritmul iterativ.

O modalitate de generare a tuturor gruparilor de m elemente din n elemente, elementele diferind intre ele fie prin natura lor, fie prin pozitia pe care o au in grupa, are la baza algoritmul de generare a permutarilor si a combinarilor.

executa INITCOMB(c, n, m, ig1)

┌ cat_timp ig1¹0 repeta

│ executa INITPERM(p, m, ig2)

│ ┌ cat_timp ig2¹0 repeta

│ │ ┌ pentru i=1, m, 1 repeta

│ │ │ a[i] <- c[p[i]]

│ │ executa PRELARANJ(a, m, n)

│ │ executa GENPERM(p, m, ig2)

│ executa GENCOMB(c, n, m, ig1)

sfarsit

Descrierea prezentata anterior este ineficienta deoarece execu­tia programului corespunzator acestui algoritm dureaza mult si este necesara cunoasterea algoritmilor pentru generarea combinarilor si permutarilor.

Deci, este necesar gasirea unei metoda de generare mai performanta. O asemenea metoda se prezinta in continuare si se bazeaza pe generarea aranjamentelor in ordine lexico­grafica printr-un procedeu iterativ. Se pleaca de la multimea (vectorul) a=(1, 2, , m). Fie un aranjament oare­care a=(a₁, a₂, , a_m). Pentru a se genera succesorul acestuia in ordine lexicografica se procedeaza astfel:

Se determina indicele i pentru care a_i poate fi marit (cel mai mare indice). Un element a_i nu poate fi marit daca valorile care sunt mai mari decit el respectiv a_i+1, a_i+2, , n nu sunt disponibile, adica apar pe alte pozitii in aranjament. Pentru a se determina usor elementele disponibile se introduce un vector DISP cu n elemente, astfel incit DISP(i) este 1 daca elemntul i apare in aranjamentul curent si 0 in caz contrar.

Se observa ca in momentul determinarii indicelui este necesar ca elementul curent care se doreste a fi marit trebuie sa se faca disponibil. Dupa ce acest element a fost gasit, acesta si elementele urmatoare se inlocuiesc cu cele mai mici numere disponibile. In cazul in care s-a ajuns la vectorul (n-m+1, , n-1, n) procesul de generare al aranjamentelor se opreste.

De exemplu, pentru n=5 si m=3 si a=(2 4 1) avem DISP=(0,0,1,0,1), iar succesorii sai sunt in ordine (2 4 1), (2 4 3), (2 4 5), (3 1 2), (3 1 4), s.a.m.d.

Procedurile de initializare si generare sunt prezentate mai jos:

procedura INIT(v, n, m, ig) este

┌ pentru i=1, m, 1 repeta

│ v_i <- 1

│ disp(i) <- 0

└

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

│ disp(i) <- 1

└

ig <- 0

sfarsit

procedura GEN(v, n, m, ig, disp) este

i <- m

gasit <- 0

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

│ disp(v_i) <- 1

│ j <- v_i+1

│ ┌ cat_timp (j£n) si (gasit=0) repeta

│ │ ┌ daca disp(j)=1 atunci

│ │ │ v_i <- j

│ │ │ disp[j] <- 0

│ │ │ k <- 0

│ │ │ ┌ pentru l=i+1, m, 1 repeta

│ │ │ │ ┌ repeta

│ │ │ │ │ k <- k+1

│ │ │ │ └ pana disp(k)=1

│ │ │ │ v_l <- k

│ │ │ │ disp(k) <- 0

│ │ │ └

│ │ │ gasit <- 1

│ │ │altfel

│ │ │ j <- j+1

│ │ └

│ └

│ i <- i-1

└

┌ daca gasit=0 atunci

│ ig <- 0

└

sfarsit

Exemplu rezolvat. Intr-o urna se afla n bile care sunt numerotate cu valori intre 1 si n. Care sunt posibilitatile de extragere a m bile astfel incit suma lor sa fie 'suma', daca conteaza si ordinea lor de extragere?

Deoarece conteaza si ordinea de aparitie trebuie generate toate aranjamentele de n luate cite m. Dupa ce au fost generate aceste elemente se retin ca solutie doar acelea pentru care suma este 'suma'. Procedurile de initializare si generare sunt identice cu cele descrise anterior iar procedura de prelu­crare este:

procedura PREL(v, n, m, suma) este

s <- 0

┌ pentru i=1, m, 1 repeta

│ s <- s+v_i

└

┌ pentru i=1, m, 1 repeta

│ scrie v_i

└

┌ daca s=suma atunci

│ scrie 'Este solutie'

│ altfel

│ scrie 'Nu este solutie'

└

sfarsit

Programul principal in pseudocod va arata astfel:

scrie 'Introduceti numarul total de bile'

citeste n

scrie 'Introduceti numarul de bile de extras'

citeste m

scrie 'Introduceti suma'

citeste suma

executa INIT(v, n, m, ig)

┌ cat_timp ig¹0 repeta

│ executa PREL(v, n, m, suma)

│ executa GEN(v, n, m, ig, disp)

sfarsit

Pentru cazul particular, cind numarul total de bile    este 5, iar numarul de bile de extras este 3 rezultatele vor fi afisate astfel:

Introduceti numarul total de bile: 5

Introduceti numarul de bile de extras: 3

Introduceti suma: 6

1 2 3 Este solutie

1 2 4 Nu este solutie

1 2 5 Nu este solutie

1 3 2 Este solutie

5 4 3 Nu este solutie

2.2.a. Algoritmul recursiv.

Generarea recursiva a aramjamentelor are la baza metoda generala de programare backtracking.

Vom folosi acelasi vector v care contine cate un element al aranjamentelor. Procedura PREL(suma ) va prelucra conform aplicatiei vectorul v.

Algoritmul de generare arata astfel:

procedura aranj ( k, p) este

daca p=k+1) atunci

executa PREL(suma);

altfel

daca p=1 atunci

│ pentru i=1,n,1 repeta

│ │ v[p]=i;

│ │ executa aranj(k,p+1)

│ └

│altfel

│ max=v[1];

│ pentru i=2,p-1,1 repeta

│ │ daca v[i]>max atunci

│ │ │ max=v[i]

│ │

│ └

│ pentru i=max+1,n,1 repeta

│ │ v[p]=i;

│ │ pentru j=1,p,1 repeta

│ │ │ m=v[p];

│ │ │ v[p]=v[j];

│ │ │ v[j]=m;

│ │ │ executa aranj(k,p+1);

│ │ │ m=v[p];

│ │ v[p]=v[j];

│ │ v[j]=m;

sfarsit

void aranj(int k, int p)

else

}

3. Probleme propuse

1 Se considera un grup de n dominouri, fiecare diferit de celelalte (pe fiecare este inscrisa o pereche unica de numere de la 1 la 6). Dominourile se considera orientate, adica nu pot fi pozitionate decit in orientarea stinga-dreapta si nu rotit cu 180 grade. Sa se determine toate lanturile corecte de m dominouri. Un lant corect este acela in care numarul inscris pe partea dreapta a dominoului i este egal cu cel inscris pe partea stinga a domi­noului i+1, pentru orice i de la 1 la n-1 (n, m, precum si pere­chile de numere de pe fiecare domino se introduc de utilizator).

2. Fie G un grup de n atenuatoare electronice, fiecare diferit de celelalte (fiecare atenuator este caracterizat de o pereche unica de impedanta intrare-impedanta iesire; gama impedantelor este: 10, 20, 50, 100, 200, 500 ohmi). Atenuatoarele se considera orientate, adica nu pot fi pozitionate decit in orientarea in­trare-iesire si nu rotit cu 180 grade. Sa se determine toate lanturile corecte de m atenuatoare. Un lant corect este acela in care impedanta de iesire a atenuatorului i este egala cu impedanta de intrare a atenuatorului i+1, pentru orice i de la 1 la m-1 (n, m, precum si perechile de impedante ale fiecarui atenua­tor se introduc de utilizator).

3. Se considera un grup de n amplificatoare electronice, fiecare diferit de celelalte (fiecare este caracterizat de o pereche unica impedanta intrare-impedanta iesire; gama impedantelor este: 10, 20, 50, 100, 200, 500 ohmi). Amplificatoarele se considera orientate, adica nu pot fi pozitionate decit in orientarea in­trare iesire si nu rotit cu 180 grade. Sa se determine toate lanturile corecte de m amplificatoare. Un lant corect este acela in care impedanta de iesire a amplificatorului i este egala cu impedanta de intrare a amplificatorului i+1, pentru orice i de la 1 la m-1 (n, m, precum si perechile de impedante ale fiecarui amplificator se introduc de utilizator).

4. Se considera o bara de metal de lungime L, din care se taie bucati de lungimi l1, l2, , ln. Sa se afiseze toate posibili­tatile de a taia m bucati identice sau diferite din bara. (L, l1, l2, , ln si m se introduc de utilizator)

5. Se da un balot de stofa de lungime L, din care se taie bucati de lungimi l1, l2, , ln. Sa se afiseze toate posibili­tatile de a taia m bucati identice sau diferite din balot. (L, l1, l2, , ln si m se introduc de utilizator)

Se considera o secventa de n numere naturale distincte. Se cere sa se scrie un program de generare a tuturor permutarilor celor n numere.

Se considera o secventa de n numere naturale, distincte.

a.Sa se scrie un program care genereaza toate aranjamentele cu repetitie luate cite m ale celor n numere.

b.Realizati un program care tipareste toate aranjamentele luate cite m ale celor n numere.

8. Care sint posibilitatile de aranjare a 2*n persoane de inaltimi diferite in 2 linii de cite n persoane, astfel incit aranjarea in cadrul fiecarei linii sa se faca in ordinea crescatoare a inaltimii, de la stinga la dreapta, si in plus fiecare persoana din prima linie sa fie mai inalta decit persoana vecina din cea de‑a doua linie?

9. O fabrica de jucarii confectioneaza inele pe care sint dispuse cite m bile rosii si n bile albastre. Cite jucarii diferite se pot obtine (doua jucarii se considera identice daca se pot obtine una din alta prin deplasarea bilelor pe inel sau prin rasturnare) ?

10.Fie n perechi de litere (2 cite 2 identice). Sa se genereze toate modurile in care pot fi aranjate aceste litere in cuvinte de lungime 2n, astfel incit 2 litere identice sa nu fie alaturate.

11. Un joc popular, jucat de n persoane, alterneaza jocul in hora (cerc) cu ruperea periodica a horei si apoi refacerea ei aleatoare. Sa se determine toate horele distincte pe care le pot forma cei n dansatori.

12. La o intrunire trebuie sa vorbeasca 5 persoane, simbolizate A, B, C, D, E. Determinati si afisati toate listele de inscriere la cuvint in care A urmeaza sa vorbeasca inaintea lui B.

13. Se considera un grup de m baieti de inaltimi diferite si un grup de n fete de inaltimi diferite. Sa se genereze toate posibilitatile in care fiecare baiat din grupul de baieti isi poate alege cite o fata din grupul de fete astfel incit pentru orice doi baieti A si B dintre care A este mai inalt decit B, fata aleasa de baiatul A sa fie strict mai inalta decit fata aleasa de baiatul B.

14. Intr‑o discoteca se afla m baieti si n fete. Sa se genereze toate posibilitatile in care baietii pot invita fetele la dans astfel incit sa nu existe conflicte( sa nu invite doi baieti aceeasi fata) si fiecare baiat sa danseze( n>=m ).

15. O caravana formata din n camile calatoreste prin desert, in sir indian. Pentru a sparge monotonia zilelor lungi de drum, beduinul se hotaraste sa schimbe asezarea camilelor, astfel incit fiecare camila sa nu mai vada in fata ei aceeasi camila de pina atunci. Care sint posibilitatile sale?

16. Un grup de m sportivi de greutati diferite servesc masa la o cantina ce are la dispozitie n meniuri, fiecare meniu avind un numar de calorii diferit de celelalte. Sa se genereze toate posibilitatile de alegere a meniurilor de catre sportivi astfel incit un sportiv mai gras decit un altul sa manince un meniu cu cel putin la fel de multe calorii ca al acestuia.

17. Intr‑o clinica pentru slabire sint internate m persoane obeze. La cantina clinicii sint disponibile n meniuri. Se stie ca persoanele au greutati diferite si oricare doua meniuri nu au acelasi numar de calorii. Sa se genereze toate posibilitatile in care persoanele isi pot alege meniurile, stiind ca daca o persoana este mai grasa decit alta trebuie sa manince strict mai putin decit aceasta( n>=m ).

ANEXE

B.L11. 3. Perm

Sa se genereze toate posibilitatile de aranjare pe o tabla de sah de N x N a N turnuri astfel incit doua turnuri sa nu se poata lua si sa nu apara in colturile tablei de sah. (Varianta iterativa)

#include <stdio.h>

#include <conio.h>

#define MAX 25

int n,v[MAX],ig;

void INIT(int n)

void PREL()

void GEN()

}

void main()

B. L11.4 PERM REC

Sa se genereze toate posibilitatile de aranjare pe o tabla de sah de N x N a N turnuri astfel incit doua turnuri sa nu se poata lua si sa nu apara in colturile tablei de sah. (varianta recursiva)

#include <stdio.h>

#include <conio.h>

#define MAX 25

int n,v[MAX];

void PREL()

void permut(int k)

}

void main()

B.L11. 5 ARAN

Intr-o urna se afla n bile care sunt numerotate cu valori intre 1 si n. Care sunt posibilitatile de extragere a m bile astfel incit suma lor sa fie 'suma', daca conteaza si ordinea lor de extragere? (varianta iterativa)

void INIT(int m, int n)

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

disp[i]=1;

ig=1;

void PREL(int suma)

void GEN()

gasit=1;

}

else

j++;

i--;

if(!gasit)

ig=0;

void main()

B.L11.6 ARAN REC

Intr-o urna se afla n bile care sunt numerotate cu valori intre 1 si n. Care sunt posibilitatile de extragere a m bile astfel incit suma lor sa fie 'suma', daca conteaza si ordinea lor de extragere? (varianta recursiva)

#include <stdio.h>

#include <conio.h>

int v[20],n,k,suma;

void PREL(int suma)

void aranj(int k, int p)

else

}

void main()