Permutasiya
Permutasiya — təkrarsız yerdəyişmələr.
Tutaq ki, elementlərin sayı m olan
M
=
a
1
,
a
2
,
.
.
,
a
m
{\displaystyle M={a_{1},a_{2},..,a_{m}}}
çoxluğu verilmişdir. Onun elementlərindən uzunluğu m-ə bərabər olan təkrarsız yerləşdirmələr düzəldək. Deməli, belə yerləşdirmədə M çoxluğunun hər bir elementi bir dəfə iştirak edir. Məsən, m=4 olarsa, belə yerləşdirmələr
a
1
a
2
a
3
a
4
,
a
1
a
2
a
4
a
3
,
a
1
a
4
a
2
a
3
a
4
a
1
a
2
a
3
{\displaystyle {a_{1}}{a_{2}}{a_{3}}{a_{4}},{a_{1}}{a_{2}}{a_{4}}{a_{3}},{a_{1}}{a_{4}}{a_{2}}{a_{3}}{a_{4}}{a_{1}}{a_{2}}{a_{3}}}
a
2
a
1
a
3
a
4
,
a
2
a
1
a
4
a
3
,
a
2
a
4
a
1
a
3
,
a
4
a
2
a
1
a
3
{\displaystyle {a_{2}}{a_{1}}{a_{3}}{a_{4}},{a_{2}}{a_{1}}{a_{4}}{a_{3}},{a_{2}}{a_{4}}{a_{1}}{a_{3}},{a_{4}}{a_{2}}{a_{1}}{a_{3}}}
... bu qaydada yerləşdirməyi davam etsək onların sayı
4
!
=
24
{\displaystyle 4!=24}
olar
== Tərif ==
m elementdən uzunluğu m-ə bərabər olan təkrarsız yerləşdirmələr yerdəyişmə adlanır.
Tərifə görə belə yerdəyişmələrin sayı
A
m
m
{\displaystyle {A_{m}^{m}}}
olar.
Permutasiya nizamlaması
Alqoritmin işləmə prinsipi çox sadədir. Alqoritm müəyyən ədədlər massivinin Permutasiyalarını növbə ilə yoxlayır və sıralanmış vəziyyətin tapılması halında öz işini sona çatdırır.
Alqoritmi sadə olaraq aşağıdakı formada yazmaq olar:
Massiv sıralı olana qədər,
Permutasiyasın al.
== Nümunə ==
nizamlamaq istədiyimiz massiv aşağıdakı kimi olsun.
1285
Burda massivin permutasiyaları alınaraq, massiv sıralanana qədər davam etdirilir. Bu əməliyyatların sayı n! ilə hesablandığından burda sıralanmanın ən pis ehtimalı 4! = 24-dür.
2 6 8 1
2 8 6 1
2 6 8 1
8 6 2 1
2 6 8 1
2 6 1 8
2 1 6 8
1 2 6 8
Yuxarıdakı permutasiyalardan sonuncusu sıralanmış vəziyyətdədir və alqoritm bu vəziyyətə çatdıqda sonlanır.
Permutasiya sıralaması
Alqoritmin işləmə prinsipi çox sadədir. Alqoritm müəyyən ədədlər massivinin Permutasiyalarını növbə ilə yoxlayır və sıralanmış vəziyyətin tapılması halında öz işini sona çatdırır.
Alqoritmi sadə olaraq aşağıdakı formada yazmaq olar:
Massiv sıralı olana qədər,
Permutasiyasın al.
== Nümunə ==
nizamlamaq istədiyimiz massiv aşağıdakı kimi olsun.
1285
Burda massivin permutasiyaları alınaraq, massiv sıralanana qədər davam etdirilir. Bu əməliyyatların sayı n! ilə hesablandığından burda sıralanmanın ən pis ehtimalı 4! = 24-dür.
2 6 8 1
2 8 6 1
2 6 8 1
8 6 2 1
2 6 8 1
2 6 1 8
2 1 6 8
1 2 6 8
Yuxarıdakı permutasiyalardan sonuncusu sıralanmış vəziyyətdədir və alqoritm bu vəziyyətə çatdıqda sonlanır.