Algoritmi pentru generarea permutarilor
Permutarea unei
multimi A = este o aplicatie bijectiva f:A->A.
Din punct de vedere al combinatoricii sunt doua probleme: numaru de permutari
al multimii si care sunt permutarile multimii.
Vom raspunde la intrbarea " 16316q1610q ;care" si vom prezenta 4 metode.
metoda 1. generarea
permultarilor conform ordinii lexicografice crescatoare.
metoda 2. genrearea recursiva a
permutarilor
metoda 3. generarea prin
reprezentarea prin vectorii de inversiune
metoda 4. generarea pemrmutarilor
folsind metoda backtracking.
Daca se genereaza permutari ale unei multimi cu mai putin de 9 elemente timpul
de executie al programelor este relativ egal, diferentele fiind de milisecunde.
daca numarul elementelor multimii depaseste 10 elemente atunci diferentele de
timp de executie este de secunde.
Primul program:
# include <stdio.h>
# include <conio.h>
# include <time.h>
int a[50];
int n,nrl;
void permut( int k);
void permut( int k)
}
else
}
}
main (void)
");
printf("\n folosiind o rezolvare recursiva\n\n");
do
while (n<1 || n>10);
start = clock();
nrl 0;
printf "\n permutarile sunt:\n");
permut 1);
finish = clock();
printf "\n durata %ld",finish - start);
duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "\n durata este %2.6f seconds\n", duration );
printf "\n\n program terminat!!");
getch();
getch();
Al 2-lea Program
# include <stdio.h>
# include <conio.h>
# include <time.h>
int a[50],b[50];
int n;
void rec( int x);
void rec( int x)
for (i=1; i<=n; i++)
if (b[i]==0)
}
main (void)
");
printf("\n folosind o rezolvare recursiva\n\n");
do
while (n<1 || n>10);
start = clock();
printf "\n permutarile sunt:\n");
rec 1);
finish = clock();
printf "\n durata %ld",finish - start);
duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "\n durata este %2.6f seconds\n", duration );
printf "\n\n program terminat!!");
getch();
getch();
Pentru n=4 ambele programe afiseaza ca timp de executie 16 milisecunde (0,016secunde)
Pentru n=5, primul program afiseaza ca timp de executie 141 milisecunde (0,141secunde), iar al 2-lea program afiseaza 157 milisecunde(0,157secunde).
Pentru n=6, primul program afiseaza ca timp de executie 750 milisecunde (0,750secunde), iar al 2-lea program afiseaza 718 milisecunde(0,718secunde).
Pentru n=7, primul program afiseaza ca timp de executie 3937 milisecunde (3,937secunde), iar al 2-lea program afiseaza 4859 milisecunde(4,859 secunde).
|
