Lektsiya№ 3-4, замествайки
Определение. Всеки един картографиране определен първи п положителни числа се нарича podstanovkoyn-та степен. и, разбира се, всяка пермутация на A може да бъде записана от две пермутации подписан един над друг
След αi тук определен брой, в която А е заместен с броя на завъртанията аз. I = 1, 2, ..., п.
Ние напише един под друг два пермутации на п символи от приема на двете линии, получени в скоби; например, п = 5:
Ние казваме, че броят на 3 пристъпи към номер 5, броят на 5 се превръща в 2, номер 1 става 3, броят 4 в 4 комбинация (или остава на място), и накрая, броят 2 отива 1. Така, две пермутации записани по всеки друг във формата (2) определя картографиране един към един от първите пет естествени числа себе си, т.е.. е. на карта, че всеки от природни числата 1, 2, 3, 4, 5 асоциирани с един от същите естествени числа и различни номера се отнасят към различни форми.
Ясно е, че картографирането на първите си пет естествени числа, които взехме с помощта на (2) едно към едно, може да бъде получена от написването една под друга, а някои от другата двойка пермутации на петте герои. Тези данни са получени от (2) чрез множество транспониране (пермутация) колони; Това са, например,
Във всички тези записи 3 става 5, 5 2 и така нататък. Г.
Замяна на А има много различни видове документи (1). По този начин, (2) и (3) са различни записи на същия заместване степента 5.
В каноничен формата на заместване
По-специално, всеки пермутация на п-та степен А може да се съхранява в канонична форма
т. е. с естествено място в най-горния ред от числа. С такова високо запис заместване на различни пермутации, изправени пред най-долния ред.
Пример за заместване на п-та степен е пермутация за самоличност
,
в които на място са всички знаци.
Забележка. Трябва да се отбележи, че горните и долните редове в записа (1) маска играят различни роли и да ги пренарежда, ние, най-общо казано, ние получаваме друга смяна.
Циклична пермутация структура
Тя се нарича дължина цикъл м.
За цикъла въведе специална нотация:
Цикълът на (2 3 4 1) работи, както следва:
Loops, които не съдържат общи елементи, наречени независими (не се припокриват).
Теорема. Всяка пермутация може да се разложи в продукт на независими цикли. Това разлагане е уникална до циклите на поръчката.
подготовка алгоритъм цикъл:
1.Berem заместване вид, в който първите елемент се придвижва.
2. Получаване на запис елемент на първия елемент и да намерят пътя си под въздействието на замествания.
3. След като изображението съвпада с елемент, който започва с изграждането на цикъла, в близост цикъл.
4. След това се спираме и да е елемент, а не част от вече определените цикли и да започне строителството на нов цикъл.
продукт на независими цикли.
От тогава ние получаваме цикъл (135). Верига 2 → 4 → 2 дава транспониране (24). Само 6 → → 8 6 дава транспониране (68). 7 остава на мястото си.