generációs permutációk
Permutáció - olyan elemek kombinációja, N különböző elemek kombinálhatók egy bizonyos sorrendben. A váltási a sorrendben a fontos elemei a csomópont kell vonni minden N elemet.
Feladat. Találd meg az összes lehetséges permutációk a sorszámok 1, 2, 3.
Az alábbi permutációk:
Permutációk ismétlések nélkül
Permutációinak számát N elemek eltérő N!. valóban:
- bármely N elemek (összes Változatok N) lehet helyezni a tetején,
- a második helyzetben lehet elhelyezni bármely, a fennmaradó (N-1) az elemek (összesen megvalósításban n · (N-1)),
- ha továbbra is a szekvenciát az összes N ágyak, kapjuk: N · (N-1) · (N-2) ·. · 1. összesen N! változatai.
Tekintsük a probléma egyre összes permutációját számok 1. N (azaz szekvencia hossza N), ahol minden egyes szám tartalmazza pontosan 1 alkalommal. Vannak különféle permutációk érdekében átvételét. Azonban legtöbbször a probléma megoldódik generáló permutáció lexikográfiai érdekében (lásd. A fenti példában). Sőt, az összes permutáció rendezése először az első számot, majd a második, stb növekvő sorrendben. Így az első permutáció 2. N. 1 és az utolsó - N N-1. 1.
Tekintsünk egy algoritmust a probléma megoldására. Mivel a kezdeti sorszámokat. Minden a következő permutációs következő lépéseket:
Így kapunk egy új sorozat, amelyet figyelembe kell venni, mint a referencia, a következő lépésben.
Végrehajtása C ++
#include
using namespace std;
void-swap (int * egy, int i, int j)
int s = a [i];
a [i] = a [j];
a [J] = s;
>
bool NextSet (int * a, int n)
int J = n - 2;
míg a (J! = -1 a [j]> = a [j + 1]) j--;
if (j == -1)
return false; // nincs több permutációk
int k = n - 1;
míg (a [j]> = a [K]) k--;
csere (a, j, k);
int L = j + 1, R = n - 1; // rendezni a többi szekvencia
míg a (l
return true;
>
void Print (int * a, int n) // kimeneti permutációk
static int num = 1; // száma permutációk
cout.width (3); // mezőszélesség kiadási permutációs számok
cout <
int main ()
int n, * a;
cout <<"N = " ;
cin >> N;
a = new int [n];
A (int i = 0; i
Nyomtatás (a, n);
míg a (NextSet (a, n))
Nyomtatás (a, n);
cin.get (); cin.get ();
vissza 0;
>
Permutációk ismétlés
Külön figyelmet érdemel feladat generáló permutációk N elemet, ha az elemek a sorrendben meg lehet ismételni. Tegyük fel, az eredeti szekvencia a következőket tartalmazza n1 elemek. n2. nk. ahol n1 elem ismétlődik újra r1, r2 n2 ismételt alkalommal, stb Ebben az esetben, n1 + n2 +. + Nk = N. Ha feltételezzük, hogy az összes n1 + n2 +. + Nk elemek különböző permutációk ismétlés, csak a különböző permutációk kiviteli alak (n1 + n2 +. + NK)!. Azonban ezek közül permutációk nem minden más. Tény, hogy az összes elemet r1 n1 mi lehet cserélni egymással, és ez az átültetés nem változik. Ugyanígy át lehet rendezni az elemeket n2. n3, és így tovább. d. Ennek eredményeként már r1! Felvételi lehetőség az azonos permutáció egy másik elrendezése ismétlődő elemeket n1. Így minden permutáció felírható r1! · R2! ·. · Rk! módon. Következésképpen a számos különböző permutációk ismétlésekkel azonos
permutációs algoritmussal lehet használni, hogy létrehoz a permutációk ismétlés nélkül ismétlés felett. Bemutatjuk az ismétlődő elem a tömbben a. Az alábbiakban egy programkódot generáló permutációk ismétlésekkel (csak változtatni a kódot funkció main ()).
#include
using namespace std;
void-swap (int * egy, int i, int j)
int s = a [i];
a [i] = a [j];
a [J] = s;
>
bool NextSet (int * a, int n)
int J = n - 2;
míg a (J! = -1 a [j]> = a [j + 1]) j--;
if (j == -1)
return false; // nincs több permutációk
int k = n - 1;
míg (a [j]> = a [K]) k--;
csere (a, j, k);
int L = j + 1, R = n - 1; // rendezni a többi szekvencia
míg a (l
return true;
>
void Print (int * a, int n) // kimeneti permutációk
static int num = 1; // száma permutációk
cout.width (3); // mezőszélesség kiadási permutációs számok
cout <
int main ()
int n, * a;
cout <<"N = " ;
cin >> N;
a = new int [n];
A (int i = 0; i
egy [1] = 1; // ismétlődő elemet
Nyomtatás (a, n);
míg a (NextSet (a, n))
Nyomtatás (a, n);
cin.get (); cin.get ();
vissza 0;
>
Az eredmény a fenti algoritmus:
