Комдинатор за програмисти - В. Липски

4. ако i 1), или цикъл [1 2. ... ... m] ако m е четно.

Доказателството се извършва чрез индукция на m, както обикновено се прави при доказване на коректността на рекурсивните алгоритми. Лесно е да се провери директно, че условията W 1 и W 2 са изпълнени. Да предположим, че m ≥ 3. Нека докажем удовлетворяемостта на W m, като приемем истинността на W m - 1. Разделяме доказателството на две части в зависимост от това дали m е четно или нечетно.

Случай 1, m е нечетен. По силата на индуктивното предположение, изпълнението на P ERM (m - 1) в ред 14 води всеки път до промяна в стойностите на P [1],. ... ..., P [m - 1] по време на цикъла [1 2. ... ... m - 1]. Така че транспонирането P [m]: =: P [m - 1] в ред 15 избира различни елементи в P [m] всеки път. Ако в началото P [i] = a i, 1 ≤ i ≤ m, тогава елементите a m, a m− 2 се поставят в P [m] на свой ред,

1.4. Генериране на пермутации

Брой изпълнени итерации на цикъла 13

a m - 3 a m - 3 a m - 3

a m - 4 a m - 4 a m - 4 a m - 4

a m− 2 a m− 1 a m− 2

a m− 1 a m− 3 a m− 2 a m− 3

a m− 1 a m− 2 a m− 1

a m− 2 a m− 1 a m− 3 a m− 2

a m− 3 a m− 2 a m− 1 a m− 1

Таблица 1.1: Промяна на стойностите на променливи P [1],. ... ..., P [m] по време на изпълнение на процедурата P ERM (m) за четен m

a m− 3,. ... ..., a 1, a m - 1. Следователно, P ERM (m) генерира всички пермутации на елементи от P [1],. ... ..., P [m].

Имайте предвид, че изместването P [1],. ... ..., P [m - 1] по време на цикъла [1 2. ... ... m - 1] и след това извършването на транспонирането P [m]: =: P [m - 1] е еквивалентно на изместването P [1],. ... ..., P [m] по цикъла [1 2. ... ... m - 3 m - 2 m m - 1] дължина m. Ако транспонирането по линия 15 се извършва за всеки i ≤ m, тогава цикъл 13 ще накара всички елементи да се върнат в първоначалните си позиции. Всъщност

последното транспониране за i = n не се извършва. Следователно ϕ m = [m, m - 1].

Алгоритъм 1.11 има едно свойство, което може да бъде полезно в някои приложения. Представете си, че търсим пермутация, която отговаря на определени условия. В такава ситуация, ако за някои m стойностите на P [m + 1],. ... ..., P [n] не отговарят на необходимите ограничения, тогава няма нужда да се обаждате на P ERM (m) и да преминавате през всички m! пермутации на елементи P [1],. ... ..., P [m]. Можем да пропуснем тези пермутации, като извършим пермутация на елементите P [1],. ... ..., P [m], означено с ϕ m. Обърнете внимание, че пермутациите ϕ m в нашия случай имат много проста форма.

Последният алгоритъм за генериране на пермутации, който представяме тук, изгражда последователност, в която разликата между две последователни пермутации е още по-малка: всяка следваща се формира от предишната, използвайки единично транспониране на съседни елементи. Това