Algoritmi Combinatoriali

ALGORITMI COMBINATORIALI

In foarte multe aplicatii ale matematicii se cere determinarea numarului de elemente ale unor multimi, numarul submultimilor unei multimi satisfacand anumite proprietati sau numarul modalitatilor de dispunere a elementelor multimii intr-o ordine specificata:

Anumite probleme de numarare apar frecvent in aritmetica, geometrie, teoria numerelor, probabilitati, statistica.

In cursul dezvoltrii matematicii s-a conturat o noua ramura a acesteia, care se ocupa cu aspectele ridicate de operatia de numarare:combinatorica.

Permutarile unei multimi

Fie A={a1, a2, &, an} o multime finita cu n elemente.Multimea A se poate ordona in mai multe moduri.

Definitie

Se numeste permutare a multimii A oricare multime ordonata care se formeaza cu cele n elemente ale acesteia.

Numarul permutarilor unei multimi cu n elemente se noteaza Pn.

Convenim ca multimea vida se poate ordona intr-un singur mod si

P0=1.

Calculul numerelor Pn

Pentru o multime cu un element A1={a1} evident P1=1.

Fie A2={a1, a2} o multime cu doua elemente.Se pot forma doua multimi ordonate (a1,a2) si (a2,a1), deci P2=2.

Fie A3={a1, a2, a3}.Permutarile multimii A3 se pot obtine din permutarile multimii A2, prin completarea acestora cu elementul a3. Astfel, din (a1,a2) se obtin permutarile (a1, a2, a3);(a1, a3, a2) ;(a3, a2, a1) iar din (a2, a1) se obtin permutarile (a2, a1, a3);(a2, a3, a1);(a3, a2, a1). In concluzie, pentru fiecare permutare cu doua elemente corespund trei elemente si P3=3*P2=3*2=6.

Aceasta observatie permite sa stabilim relatia generala: Pn=nPn-1, ne1 (1)

Intr-adevar, fiecare permutare cu n-1 elemente (a1, a2,&an-1) poate fi completata adaugand elementul an in n moduri:

(a1, a2,&,an-1, an); (a1,a2,&,an-2,an,an-1); &; (an, a1,&,an-1).

Folosind relatia (1) se obtine:

Pn=n*Pn-1=n*(n-1)*Pn-2=&=n(n-1)(n-2)&3*3*1, deci:

Pn=1*2*3*&*(n-1)*n.

Se foloseste notatia: 1*2*3*&*(n-1)*n=n! care se citeste n factorial.

Sa se genereze permutarile unei multimi cu n elemente.

Program

#include<stdlib.h>

#include<conio.h>

#include<stdio.h>

int n,k,x[10],contor,m;

int gasit,pos;

int posibil(int k)

{

for(int i=1;i<=k-1;i++)

if(x[i]==x[k]) return(0);

return(1);

}

void afisare()

{ // m=coloane

contor++;

if (contor>24) {

contor=1;

m++;

if(m==3) {

m=0;

getch();

clrscr();

}

}

gotoxy(10+20*m,contor);

for(int i=1;i<=k;i++)

printf("%d ",x[i]);

printf("n");

}