Pronalaženje sljedeće permutacije. Kombinatorske formule

Permutacija je kombinacija elemenata iz N različiti elementi uzeti određenim redoslijedom. U permutaciji je važan redoslijed elemenata i svi elementi moraju biti uključeni u permutaciju. N elementi.

Zadatak: Pronađite sve moguće permutacije za niz brojeva 1, 2, 3.
Postoje sljedeće permutacije:

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

Permutacije bez ponavljanja

Broj permutacija za N različitih elemenata je N!. stvarno:

bilo koji od N elementi (ukupne opcije N),
bilo koji od preostalih (N-1) elementi (ukupne opcije N (N-1)),
ako nastavimo ovaj niz za sve N mjesta, dobijamo: N (N-1) (N-2) ... ... 1, to je sve N! permutacije.

Razmotrimo problem dobijanja svih permutacija brojeva 1…N(odnosno nizovi dužine N), pri čemu se svaki od brojeva pojavljuje tačno 1 put. Postoji mnogo opcija za redosled kojim se permutacije dobijaju. Međutim, najčešće rješavani problem je generiranje permutacija u leksikografski red (vidi primjer iznad). U ovom slučaju, sve se permutacije prvo sortiraju po prvom broju, zatim po drugom itd. u rastućem redosledu. Dakle, prva permutacija će biti 1 2 … N, i posljednji N N-1 … 1.

Razmotrite algoritam za rješavanje problema. Dat je početni niz brojeva. Da biste dobili svaku narednu permutaciju, morate izvršiti sljedeće korake:

Potrebno je skenirati trenutnu permutaciju s desna na lijevo i istovremeno se uvjeriti da svaki sljedeći element permutacije (element s većim brojem) nije veći od prethodnog (element s manjim brojem). Čim se ovaj odnos naruši, potrebno je zaustaviti se i označiti trenutni broj (pozicija 1).
Opet, pogledajte put koji se kretao s desna na lijevo dok ne dođemo do prvog broja, koji je veći od onog označenog u prethodnom koraku.
Zamijenite dva primljena elementa.
Sada u dijelu niza, koji se nalazi desno od pozicije 1, trebate sortirati sve brojeve u rastućem redoslijedu. Budući da su prije toga svi već bili napisani u opadajućem redoslijedu, potrebno je jednostavno okrenuti ovaj dio podniza.

Tako ćemo dobiti novi niz, koji će se u sljedećem koraku smatrati početnim.

Implementacija u C++

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

#include
korištenje imenskog prostora std;

{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int *a, int n)
{
int j = n - 2;
dok (j != -1 && a[j] >= a) j--;
ako (j == -1)
return false; // nema više permutacija
int k = n - 1;
dok (a[j] >= a[k]) k--;
swap(a, j, k);
int l = j + 1, r = n - 1;
dok (l swap(a, l++, r--);
return true;
}
void Ispis(int *a, int n) // permutacija izlaza
{
statički int broj = 1; // broj permutacije
širina kuta (3);
cout<< num++ << ": " ;
za (int i = 0; i< n; i++)
cout<< a[i] << " " ;
cout<< endl;
}
int main()
{
intn, *a;
cout<< "N = " ;
cin >> n;
a = novi int[n];
za (int i = 0; i< n; i++)
a[i] = i + 1;
Print(a, n);
dok (Sljedeći skup(a, n))
Print(a, n);
cin.get(); cin.get();
return 0;
}

Rezultat izvršenja

Permutacije s ponavljanjima

Problem generisanja permutacija zaslužuje posebnu pažnju. N elemente ako se elementi niza mogu ponoviti. Pretpostavimo da se originalni niz sastoji od elemenata n 1 , n 2 ... n k, gdje je element n 1 ponavlja r1 jednom, n 2 ponavlja r2 vremena itd. Gde n 1 +n 2 +...+n k =N. Ako sve računamo n 1 +n 2 +...+n k elementi permutacije s različitim ponavljanjima, zatim ukupno različite varijante permutacija ( n 1 +n 2 +...+n k)!. Međutim, među ovim permutacijama nisu sve različite. Zaista, sve r1 elementi n 1 možemo preurediti jedni s drugima, a to ne mijenja permutaciju. Na isti način možemo preurediti elemente n 2, n 3 itd. Kao rezultat, imamo r1! varijante pisanja iste permutacije sa različitim rasporedom ponavljajućih elemenata n 1. Dakle, bilo koja permutacija se može napisati r 1!r 2!... r k! načine. Dakle, broj različitih permutacija s ponavljanjima je

Za generiranje permutacija s ponavljanjima, možete koristiti algoritam za generiranje permutacija bez ponavljanja koji je gore dat. Hajde da uvedemo element koji se ponavlja u niz a. Ispod je programski kod za generiranje permutacija s ponavljanjima (promijenjen je samo kod funkcije main().

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

#include
korištenje imenskog prostora 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;
dok (j != -1 && a[j] >= a) j--;
ako (j == -1)
return false; // nema više permutacija
int k = n - 1;
dok (a[j] >= a[k]) k--;
swap(a, j, k);
int l = j + 1, r = n - 1; // sortiraj ostatak niza
dok (l swap(a, l++, r--);
return true;
}
void Ispis(int *a, int n) // permutacija izlaza
{
statički int broj = 1; // broj permutacije
širina kuta (3); // širina izlaznog polja broja permutacije
cout<< num++ << ": " ;
za (int i = 0; i< n; i++)
cout<< a[i] << " " ;
cout<< endl;
}
int main()
{
intn, *a;
cout<< "N = " ;
cin >> n;
a = novi int[n];
za (int i = 0; i< n; i++)
a[i] = i + 1;
a = 1; // ponovljeni element
Print(a, n);
dok (Sljedeći skup(a, n))
Print(a, n);
cin.get(); cin.get();
return 0;
}

Izlaz gornjeg algoritma je:

Zapisivanje permutacije  kao produkta nezavisnih ciklusa

olakšava pronalaženje reda permutacije

Teorema 2. Red
permutacije
(red cikličke podgrupe
)jednaki najmanji zajednički višekratnik(LCM) dužina nezavisnih ciklusa uključenih u dekompoziciju .

Dokaz. Zamislite permutaciju
kao proizvod nezavisnih ciklusa

. (7)

Od ciklusa
nezavisni (djeluju na različitim skupovima
), i ako je q red cikličke podgrupe,

gdje
.

Dakle, q je zajednički višekratnik redova ciklusa  k koji se poklapaju sa njihovim dužinama .

Ako je q najmanji pozitivan broj za koji

,onda

Osnovna teorema aritmetike. Svaki pozitivan cijeli broj n koji nije jednak jedinici može se napisati kao proizvod prostih brojeva

. (9)

Ova notacija je jedinstvena do reda faktora.

Zamjenom proizvoda podudarnih prostih brojeva u (9) njihovim potencijama, dobivamo

gdje

Puno prostih brojeva

Primjer. Bilo koja dva cijela broja m i n mogu se napisati kao proizvodi istih prostih brojeva

Primjer. Odredite redosled permutacije
vrsta

Rješenje. Predstavimo permutaciju  kao proizvod nezavisnih ciklusa, tj.

Dužine nezavisnih ciklusa
jednaka

Dakle, redoslijed razmatrane permutacije jednako 28.

Dekompozicija permutacije u proizvod transpozicija.

Definicija. Ciklus dužine dva naziva se transpozicija. Svaka transpozicija ima oblik
i ostavlja sve znakove na mjestu osim za
.

Teorema. Svaka permutacija
može se predstaviti kao proizvod transpozicije.

Dokaz. Teorema će biti dokazana ako možemo predstaviti svaki od ciklusa  k uključenih u ekspanzije permutacije kao produkte transpozicije:
.

Razmotrimo proizvoljan ciklus , na primjer
i razložiti ga u proizvod transpozicije.

Algoritam dekompozicije petlje
u proizvod transpozicija prikazan je na slici 2.

Ciklus
transpozicije

Slika 2.– Razlaganje ciklusa
u proizvod transpozicije.

Nakon završetka svih operacija na mjestu svakog elementa ciklusa sledeći element je pronađen, a prvi element se pomerio na poslednje mesto. Tako ciklus pokazalo se da je razloženo u proizvod transpozicija:

Naravno, ova dekompozicija nije jedinstvena. Na primjer

Još jedna stvar je važna - i u prvom i u drugom proširenju je jednak broj transpozicija - četiri. Ako a
, tada je broj transpozicija
. Širenje na isti način svaki ciklus
permutacije u proizvod transpozicije, dobijamo ekspanziju cijele permutacije u proizvod transpozicije.

Komentar. Broj transpozicija u ciklusu
možda više od četiri! Uzmite proizvoljnu transpoziciju iz dekompozicije ovog ciklusa, na primjer,
. Zatim proizvod
poklapa se sa permutacijom identiteta i ciklusom
može se predstaviti kao

Lako je vidjeti da je u svim ovim slučajevima broj transpozicija paran i jednak 4, 6, 8. Jasno je da metoda koja „produžuje“ dekompoziciju ne mijenja paritet originalne dekompozicije.

Teorema. Neka je  permutacija od , a

. (9)

neko proširenje  u proizvodu transpozicija.

Zatim broj

(10)

naziva se paritet (signatura ili znak) permutacije  i potpuno je određen sa , tj. ne zavisi od toga kako se permutacija  razlaže u proizvod transpozicija. Osim toga, ako
, onda