A következő permutáció megkeresése. Kombinatorikai képletek

A permutáció a következő elemek kombinációja N különböző elemek meghatározott sorrendben. A permutációnál fontos az elemek sorrendje, és minden elemnek részt kell vennie a permutációban. N elemeket.

Feladat: Keresse meg az 1, 2, 3 számsorozat összes lehetséges permutációját!
A következő permutációk léteznek:

1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1

Permutációk ismétlés nélkül

A permutációk száma N különböző elemre N!. Igazán:

bármelyik N elemek (összes lehetőség N),
a maradék bármelyike (N-1) elemek (összes lehetőség N (N-1)),
ha folytatjuk ezt a sorozatot mindenkinek N helyeken kapjuk: N (N-1) (N-2) ... ... 1, ez minden N! permutációk.

Tekintsük a számok összes permutációjának megszerzésének problémáját 1…N(vagyis hosszúságú sorozatok N), ahol minden szám pontosan 1-szer fordul elő. Számos lehetőség van a permutációk beszerzésének sorrendjére. A leggyakrabban megoldott probléma azonban a permutációk generálása in lexikográfiai sorrendben (lásd a fenti példát). Ebben az esetben az összes permutáció először az első szám, majd a második és így tovább. növekvő sorrendben. Tehát az első permutáció az lesz 1 2 … N, és az utolsó N N-1 … 1.

Tekintsünk egy algoritmust a probléma megoldására. Adott a kezdeti számsor. Minden további permutáció eléréséhez a következő lépéseket kell végrehajtania:

Az aktuális permutációt jobbról balra kell pásztázni, és egyúttal meg kell győződni arról, hogy a permutáció minden következő eleme (nagyobb számú elem) nem több, mint az előző (kisebb számú elem). Amint ez az arány megsérül, meg kell állni és meg kell jelölni az aktuális számot (1. pozíció).
Ismét nézzük meg a jobbról balra megtett utat, amíg el nem érjük az első számot, amely nagyobb, mint az előző lépésben jelölt.
Cserélje fel két fogadott elemet.
Most a tömb azon részében, amely az 1. pozíciótól jobbra található, az összes számot növekvő sorrendbe kell rendeznie. Mivel azelőtt mindegyiket már csökkenő sorrendben írták, egyszerűen meg kell fordítani a részsorozat ezen részét.

Így egy új sorozatot kapunk, amelyet a következő lépésben kezdeti sorozatnak tekintünk.

Megvalósítás C++ nyelven

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#beleértve
névtér használata std;

{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int *a, int n)
{
int j = n-2;
while (j != -1 && a[j] >= a) j--;
ha (j == -1)
return false; // nincs több permutáció
int k = n-1;
míg (a[j] >= a[k]) k--;
csere(a, j, k);
int l = j + 1, r = n - 1;
míg (l csere(a, l++, r--);
return true;
}
void Print(int *a, int n) // kimeneti permutáció
{
statikus int szám = 1; // permutációs szám
kivágás szélessége (3);
cout<< num++ << ": " ;
for (int i = 0; i< n; i++)
cout<< a[i] << " " ;
cout<< endl;
}
int main()
{
intn, *a;
cout<< "N = " ;
cin >> n;
a = új int[n];
for (int i = 0; i< n; i++)
a[i] = i + 1;
Print(a, n);
while (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
visszatérés 0;
}

A végrehajtás eredménye

Permutációk ismétlésekkel

Külön figyelmet érdemel a permutációk generálásának problémája. N elemeket, ha a sorozat elemei megismételhetők. Tegyük fel, hogy az eredeti sorozat elemekből áll n 1 , n 2 ... n k, ahol az elem n 1 ismétli r1 egyszer, n 2 ismétli r2 idők stb. Ahol n 1 +n 2 +...+n k =N. Ha mindent beleszámolunk n 1 +n 2 +...+n k egy permutáció elemei különböző ismétlődésekkel, majd a permutációk összesen különböző változatai ( n 1 +n 2 +...+n k)!. E permutációk között azonban nem mindegyik különbözik egymástól. Valóban, mindent r1 elemeket n 1átrendezhetjük egymással, és ez nem változtat a permutáción. Ugyanígy átrendezhetjük az elemeket n 2, n 3 stb. Ennek eredményeként megvan r1! ugyanazon permutáció írásának változatai az ismétlődő elemek eltérő elrendezésével n 1. Így bármilyen permutáció írható r 1 ! r 2 ! ... r k ! módokon. Ezért a különböző permutációk száma ismétlésekkel az

Az ismétlésekkel járó permutációk generálásához használhatja a fent megadott, ismétlés nélküli permutációkat generáló algoritmust. Vezessünk be egy ismétlődő elemet az a tömbbe. Alább található a programkód az ismétlésekkel járó permutációk generálásához (csak a main() függvény kódja módosult).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#beleértve
névtér használata std;
void swap(int *a, 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;
while (j != -1 && a[j] >= a) j--;
ha (j == -1)
return false; // nincs több permutáció
int k = n-1;
míg (a[j] >= a[k]) k--;
csere(a, j, k);
int l = j + 1, r = n - 1; // rendezi a sorozat többi részét
míg (l csere(a, l++, r--);
return true;
}
void Print(int *a, int n) // kimeneti permutáció
{
statikus int szám = 1; // permutációs szám
kivágás szélessége (3); // a permutációs szám kimeneti mezőjének szélessége
cout<< num++ << ": " ;
for (int i = 0; i< n; i++)
cout<< a[i] << " " ;
cout<< endl;
}
int main()
{
intn, *a;
cout<< "N = " ;
cin >> n;
a = új int[n];
for (int i = 0; i< n; i++)
a[i] = i + 1;
a = 1; // ismétlődő elem
Print(a, n);
while (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
visszatérés 0;
}

A fenti algoritmus kimenete:

Egy  permutáció felírása független ciklusok szorzataként

megkönnyíti a permutáció sorrendjének megtalálását

2. tétel. Rendelés
permutációk
(ciklikus alcsoport sorrendje
)egyenlő legkisebb közös többszörös(LCM) a  dekompozíciójában szereplő független ciklusok hosszának.

Bizonyíték. Képzelj el egy permutációt
független ciklusok szorzataként

. (7)

A ciklusok óta
függetlenek (különböző halmazokon hatnak
), és ha q egy ciklikus alcsoport sorrendje,

ahol
.

Ezért q a hosszukkal egybeeső  k ciklusok rendjének közös többszöröse .

Ha q az a legkisebb pozitív szám, amelyre

,azután

Az aritmetika alaptétele. Minden n pozitív egész szám, amely nem egyenlő eggyel, felírható prímszámok szorzataként

. (9)

Ez a jelölés a tényezők sorrendjéig egyedi.

Ha a (9)-ben egybeeső prímszámok szorzatait hatványukra cseréljük, azt kapjuk

ahol

Sok prímszám

Példa. Bármely két m és n egész szám felírható azonos prímszámok szorzataként

Példa. Határozza meg a permutáció sorrendjét!
kedves

Megoldás. Ábrázoljuk a  permutációt független ciklusok szorzataként, azaz.

Független ciklusok hossza
egyenlő

Ezért a figyelembe vett permutáció sorrendje egyenlő 28.

Egy permutáció lebontása transzpozíciók szorzatává.

Meghatározás. A kettő hosszúságú ciklust transzpozíciónak nevezzük. Minden átültetésnek megvan a formája
és minden karaktert a helyén hagy, kivéve a
.

Tétel. Minden permutáció
átültetés szorzataként ábrázolható.

Bizonyíték. A tétel akkor bizonyítandó, ha a permutáció kiterjesztésében szereplő  k ciklusok mindegyikét transzpozíciók szorzataként tudjuk ábrázolni:
.

Vegyünk egy tetszőleges ciklust , például
és bontja le transzpozíciók szorzatára.

Hurokbontási algoritmus
transzpozíciók szorzatába a 2. ábrán látható.

Ciklus
átültetések

2. ábra.– Ciklusbontás
transzpozíciók termékévé.

Az összes művelet befejezése után a ciklus egyes elemei helyett a következő elem megtalálható, és az első elem az utolsó helyre került. Így a ciklus kiderült, hogy az átültetések szorzatára bomlik:

Ez a bomlás természetesen nem egyedi. Például

Egy másik dolog fontos - és az első és a második bővítésben egyenlő számú transzpozíció van - négy. Ha
, akkor az átültetések száma az
. Minden ciklusban azonos módon bővül
permutációk a transzpozíció szorzatába a teljes permutáció kiterjesztését kapjuk transzpozíciók termékévé.

Megjegyzés. Transzpozíciók száma egy ciklusban
talán több mint négy! Vegyünk egy tetszőleges transzpozíciót ennek a ciklusnak a dekompozíciójából, például
. Aztán a termék
egybeesik az azonosság-permutációval és a ciklussal
ként ábrázolható

Könnyen belátható, hogy ezekben az esetekben a transzpozíciók száma páros, és egyenlő 4, 6, 8. Nyilvánvaló, hogy a dekompozíciót "meghosszabbító" módszer nem változtatja meg az eredeti dekompozíció paritását.

Tétel. Legyen  a permutációja , de

. (9)

a  bizonyos mértékű kiterjesztése az átültetések szorzatában.

Aztán a szám

(10)

a  permutáció paritásának (aláírásának vagy előjelének) nevezzük, és teljes mértékben  határozza meg, azaz. nem függ attól, hogy a  permutációt hogyan bontják fel transzpozíciók szorzatára. Ezen kívül, ha
, azután