Permutare - o combinație de elemente din N elemente diferite combinate într-o anumită ordine. Schimbul de ordinul a elementelor importante în schimbul de date ar trebui să implice toate elementele N.
Sarcină. Gaseste toate permutări posibile ale numerelor de secvență 1, 2, 3.
Următoarele permutările:
Permutări fără repetiție
Numărul de permutări de elemente N este diferit N!. într-adevăr:
- oricare dintre elementele N (toate variantele N) pot fi plasate pe partea de sus,
- a doua poziție poate fi plasată oricare dintre (N-1) Restul elementelor (un total de realizare N · (N-1)),
- dacă vom continua secvența pentru toate paturile N, obținem: N · (N-1) · (N-2) ·. · 1. pentru un total de N! permutări.
Luați în considerare problema de a obține toate permutările numerelor 1. N (adică, secvența de lungime N), în care fiecare dintre numerele incluse exact 1 dată. Există o varietate de permutări primirii comenzii. Cu toate acestea, cel mai adesea problema este rezolvată permutări generatoare în ordine lexicografică (vezi. Exemplul de mai sus). Mai mult decât atât, toate permutările sunt sortate în primul rând de către primul număr, apoi al doilea, etc. în ordine crescătoare. Astfel, primul permutarea este 2. N. 1 și ultima - N N-1. 1.
Luați în considerare un algoritm pentru rezolvarea problemei. Având în vedere numerele de secventa initiale. Pentru fiecare dintre următoarele permutarea următoarele etape:
Astfel, vom obține o nouă secvență, care va fi considerată ca o referință în etapa următoare.
Implementarea C ++
#include
using namespace std;
void swap (int * a, int i, int j)
int s = a [i];
a [i] = a [j];
o [j] = s;
>
bool NextSet (int * a, int n)
int j = n - 2;
în timp ce (j! = -1 o [j]> = a [j + 1]) j--;
if (j == -1)
return false; // nu mai permutări
int k = n - 1;
în timp ce (a [j]> = a [k]) k--;
swap (a, j, k);
int l = j + 1, r = n - 1; // sortați restul secvenței
în timp ce (l
return true;
>
void Print (int * a, int n) // permutări de ieșire
int num static = 1; // numărul de permutări
cout.width (3); // numere de permutare câmp lățime de ieșire
cout <
int main ()
int n, * o;
cout <<"N = " ;
>> n cin;
a = new int [n];
pentru (int i = 0; i
Print (a, n);
în timp ce (NextSet (a, n))
Print (a, n);
cin.get (); cin.get ();
return 0;
>
Permutări cu repetiție
Ea merită o atenție specială generatoare de sarcină permutări de elemente N în cazul în care elementele secvenței poate fi repetată. Să presupunem că secvența inițială constă din elemente n1. n2. nk. în cazul în care elementul n1 se repetă din nou r1, n2 repetate ori, etc. R2 În acest caz, n1 + n2 +. + Nk = N. Dacă presupunem că toate n1 + n2 +. + elemente Nk permutări diferite cu repetiție, numai diferitele permutări varianta (n1 + n2 +. + Nk!). Cu toate acestea, printre aceste permutări nu sunt toate diferite. De fapt, toate elementele r1 n1 putem fi interschimbate unii cu alții, și de la această transpunere nu se schimbă. În același mod, putem rearanja elementele de n2. n3, și așa mai departe. d. Ca urmare, avem r1! opțiuni pentru aceeași permutare cu un aranjament diferit de elemente repetitive n1 de înregistrare. Astfel, orice permutare poate fi scris r1! · R2! ·. · Rk! moduri. În consecință, numărul diferitelor permutări cu repetiții ale aceluiași
algoritmul de generare a permutare poate fi utilizat pentru a genera permutări cu repetiție fără repetarea de mai sus. Introducem elementul care se repetă în matrice a. Mai jos este un cod de program pentru generarea de permutări cu repetari (doar schimba principal funcția de cod ()).
#include
using namespace std;
void swap (int * a, int i, int j)
int s = a [i];
a [i] = a [j];
o [j] = s;
>
bool NextSet (int * a, int n)
int j = n - 2;
în timp ce (j! = -1 o [j]> = a [j + 1]) j--;
if (j == -1)
return false; // nu mai permutări
int k = n - 1;
în timp ce (a [j]> = a [k]) k--;
swap (a, j, k);
int l = j + 1, r = n - 1; // sortați restul secvenței
în timp ce (l
return true;
>
void Print (int * a, int n) // permutări de ieșire
int num static = 1; // numărul de permutări
cout.width (3); // numere de permutare câmp lățime de ieșire
cout <
int main ()
int n, * o;
cout <<"N = " ;
>> n cin;
a = new int [n];
pentru (int i = 0; i
o [1] = 1; // element de repetare
Print (a, n);
în timp ce (NextSet (a, n))
Print (a, n);
cin.get (); cin.get ();
return 0;
>
Rezultatul algoritmului de mai sus:
