Комдинаторика за програмисти - Б

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

---