Găsind următoarea permutare. Formule combinatorice

O permutare este o combinație de elemente din N diferite elemente luate într-o anumită ordine. Într-o permutare, ordinea elementelor este importantă și toate elementele trebuie să fie implicate în permutare. N elemente.

Sarcină: Găsiți toate permutările posibile pentru succesiunea numerelor 1, 2, 3.
Există următoarele permutări:

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ări fără repetare

Numărul de permutări pentru N elemente diferite este N!. Într-adevăr:

oricare dintre N elemente (opțiuni totale N),
oricare din restul (N-1) elemente (opțiuni totale N (N-1)),
dacă continuăm această secvență pentru toți N locuri, obținem: N (N-1) (N-2) ... ... 1, asta e tot N! permutări.

Luați în considerare problema obținerii tuturor permutărilor numerelor 1…N(adică secvențe de lungime N), unde fiecare dintre numere apare exact o dată. Există multe opțiuni pentru ordinea în care sunt obținute permutările. Cu toate acestea, problema cel mai frecvent rezolvată este generarea de permutări în lexicografic comanda (vezi exemplul de mai sus). În acest caz, toate permutările sunt sortate mai întâi după primul număr, apoi după al doilea și așa mai departe. în ordine crescătoare. Deci prima permutare va fi 1 2 … N, și ultimul N N-1 … 1.

Luați în considerare un algoritm pentru rezolvarea problemei. Este dată șirul inițial de numere. Pentru a obține fiecare permutare ulterioară, trebuie să efectuați următorii pași:

Este necesar să scanați permutarea curentă de la dreapta la stânga și, în același timp, să vă asigurați că fiecare element următor al permutației (un element cu un număr mai mare) nu este mai mult decât cel anterior (un element cu un număr mai mic). De îndată ce acest raport este încălcat, este necesar să se oprească și să se marcheze numărul curent (poziția 1).
Din nou, uită-te la drumul parcurs de la dreapta la stânga până ajungem la primul număr, care este mai mare decât cel marcat în pasul anterior.
Schimbați două elemente primite.
Acum, în partea matricei, care este situată în dreapta poziției 1, trebuie să sortați toate numerele în ordine crescătoare. Deoarece înainte de asta toate erau deja scrise în ordine descrescătoare, este necesar să răsturnați pur și simplu această parte a subsecvenței.

Astfel, vom obține o nouă secvență, care va fi considerată ca fiind cea inițială în pasul următor.

Implementare în 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
folosind namespace std;

{
int s = a[i];
a[i] = a[j];
a[j] = s;
}
bool NextSet(int *a, int n)
{
int j = n - 2;
în timp ce (j != -1 && a[j] >= a) j--;
dacă (j == -1)
returnează fals; // nu mai există 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;
în timp ce (l swap(a, l++, r--);
returnează adevărat;
}
void Print(int *a, int n) // ieșire permutare
{
static int num = 1; // număr de permutare
lățimea cotului(3);
cout<< num++ << ": " ;
pentru (int i = 0; i< n; i++)
cout<< a[i] << " " ;
cout<< endl;
}
int main()
{
intn, *a;
cout<< "N = " ;
cin >> n;
a = nou int[n];
pentru (int i = 0; i< n; i++)
a[i] = i + 1;
Print(a, n);
în timp ce (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
returnează 0;
}

Rezultatul executiei

Permutări cu repetări

Problema generării permutărilor merită o atenție specială. N elemente dacă elementele secvenței pot fi repetate. Să presupunem că secvența originală este formată din elemente n 1 , n 2 ... n k, unde elementul n 1 se repetă r1 o singura data, n 2 se repetă r2 ori, etc. în care n 1 +n 2 +...+n k =N. Dacă numărăm totul n 1 +n 2 +...+n k elemente ale unei permutări cu diferite repetări, apoi un total de diferite variante de permutări ( n 1 +n 2 +...+n k)!. Cu toate acestea, printre aceste permutări, nu toate sunt diferite. Într-adevăr, totul r1 elemente n 1 ne putem rearanja unul cu celălalt, iar acest lucru nu schimbă permutarea. În același mod, putem rearanja elementele n 2, n 3 etc. Ca urmare, avem r1! variante de scriere a aceleiaşi permutaţii cu dispunerea diferită a elementelor repetate n 1. Astfel, orice permutare poate fi scrisă r 1 ! r 2 ! ... r k ! moduri. Prin urmare, numărul de permutări diferite cu repetări este

Pentru a genera permutări cu repetări, puteți utiliza algoritmul de generare a permutărilor fără repetări prezentat mai sus. Să introducem un element care se repetă în tabloul a. Mai jos este codul programului pentru generarea de permutări cu repetiții (a fost schimbat doar codul funcției 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
folosind namespace 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;
în timp ce (j != -1 && a[j] >= a) j--;
dacă (j == -1)
returnează fals; // nu mai există 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; // sortează restul secvenței
în timp ce (l swap(a, l++, r--);
returnează adevărat;
}
void Print(int *a, int n) // ieșire permutare
{
static int num = 1; // număr de permutare
lățimea cotului(3); // lățimea câmpului de ieșire al numărului de permutare
cout<< num++ << ": " ;
pentru (int i = 0; i< n; i++)
cout<< a[i] << " " ;
cout<< endl;
}
int main()
{
intn, *a;
cout<< "N = " ;
cin >> n;
a = nou int[n];
pentru (int i = 0; i< n; i++)
a[i] = i + 1;
a = 1; // element repetat
Print(a, n);
în timp ce (NextSet(a, n))
Print(a, n);
cin.get(); cin.get();
returnează 0;
}

Rezultatul algoritmului de mai sus este:

Scrierea unei permutări  ca produs al ciclurilor independente

facilitează găsirea ordinii permutării

Teorema 2. Ordin
permutări
(ordinea subgrupului ciclic
)egală cel mai mic multiplu comun(LCM) a lungimilor ciclurilor independente incluse în descompunerea lui .

Dovada. Imaginați-vă o permutare
ca produs al ciclurilor independente

. (7)

De când ciclurile
independente (acţionează pe seturi diferite
), iar dacă q este de ordinul unui subgrup ciclic,

Unde
.

Prin urmare, q este un multiplu comun al ordinelor ciclurilor  k care coincid cu lungimile lor .

Dacă q este cel mai mic număr pozitiv pentru care

,apoi

Teorema fundamentală a aritmeticii. Fiecare număr întreg pozitiv n care nu este egal cu unu poate fi scris ca produs al numerelor prime

. (9)

Această notație este unică în ordinea factorilor.

Înlocuind produsele numerelor prime care coincid din (9) cu puterile lor, obținem

Unde

O mulțime de numere prime

Exemplu. Orice două numere întregi m și n pot fi scrise ca produse ale acelorași numere prime

Exemplu. Determinați ordinea permutației
drăguț

Decizie. Să reprezentăm permutarea  ca un produs al ciclurilor independente, adică.

Lungimile ciclurilor independente
egal

Prin urmare, ordinea permutării considerate este egal cu 28.

Descompunerea unei permutări într-un produs al transpozițiilor.

Definiție. Un ciclu de lungime doi se numește transpunere. Orice transpunere are forma
și lasă toate personajele pe loc, cu excepția
.

Teorema. Fiecare permutare
poate fi reprezentat ca un produs al unei transpuneri.

Dovada. Teorema va fi demonstrată dacă putem reprezenta fiecare dintre ciclurile  k incluse în expansiunile permutării ca produse ale transpozițiilor:
.

Luați în considerare un ciclu arbitrar , De exemplu
și descompuneți-l într-un produs al transpozițiilor.

Algoritm de descompunere în buclă
în produsul transpozițiilor este prezentat în Figura 2.

Ciclu
transpuneri

Fig 2.– Descompunerea ciclului
într-un produs al transpunerilor.

După finalizarea tuturor operațiunilor în locul fiecărui element al ciclului următorul element a fost găsit, iar primul element a fost mutat pe ultimul loc. Astfel ciclul s-a dovedit a fi descompus într-un produs de transpoziții:

Desigur, această descompunere nu este unică. de exemplu

Un alt lucru este important - și în prima și în a doua descompunere există un număr egal de transpuneri - patru. În cazul în care un
, atunci numărul de transpuneri este
. Expandându-se în același mod fiecare ciclu
permutări în produsul transpoziției, obținem expansiunea întregii permutări într-un produs al transpunerilor.

Cometariu. Numărul de transpoziții într-un ciclu
poate mai mult de patru! Luați o transpunere arbitrară din descompunerea acestui ciclu, de exemplu,
. Apoi produsul
coincide cu permutarea identitară și cu ciclul
poate fi reprezentat ca

Este ușor de observat că în toate aceste cazuri numărul transpozițiilor este par și egal cu 4, 6, 8. Este clar că metoda care „prelungește” descompunerea nu modifică paritatea descompunerii inițiale.

Teorema. Fie  o permutare a , A

. (9)

o oarecare expansiune a lui  în produsul transpozițiilor.

Apoi numărul

(10)

se numește paritatea (semnătura sau semnul) permutației  și este complet determinată de , adică. nu depinde de modul în care permutarea  se descompune într-un produs al transpozițiilor. În plus, dacă
, apoi