Алгоритм доказывания кучи для генерации перестановок

Question

Мне нужно доказать правильность алгоритма Кучи для генерации перестановок. Псевдокод для него следующим образом:

HeapPermute(n) 
//Implements Heap’s algorithm for generating permutations 
//Input: A positive integer n and a global array A[1..n] 
//Output: All permutations of elements of A 
if n = 1 
    write A 
else 
    for i ←1 to n do 
    HeapPermute(n − 1) 
    if n is odd 
     swap A[1] and A[n] 
    else swap A[i] and A[n] 

(взят из Введения в разработку и анализ алгоритмов Левитина)

Я знаю, что нужно использовать индукцию, чтобы доказать свою правоту, но я не точно, как это сделать. Я доказал математические уравнения, но не алгоритмы.

Я думал, доказательство будет выглядеть примерно так ...

1) For n = 1, heapPermute is obviously correct. {1} is printed. 
2) Assume heapPermute() outputs a set of n! permutations for a given n. Then 
?? 

Я просто не знаю, как идти о завершении шага индукции. Я даже на правильном пути здесь? Любая помощь будет принята с благодарностью.

Answer 1

1. Для n = 1, heapPermute, очевидно, правильный. {1} печатается.
2. Предположим, что heapPermute() выводит набор из n! перестановок для заданного n. Затем
3. ??

Теперь, с учетом первых двух предположений, показывают, что heapPermutate(n+1) возвращает все (п + 1)! перестановки.

Answer 2

Да, это звучит как хороший подход. Подумайте, как рекурсивно определить набор всех перестановок, т. Е. Как могут быть перестановки из {1..n} в терминах перестановок {1.. n-1}. Для этого напомним индуктивное доказательство наличия перестановок n!. Как проходит индуктивный шаг?

Answer 3

Рекурсивный подход - это, безусловно, путь. Учитывая ваши первые два шага, чтобы доказать, что heapPermutate(n+1) возвращает все перестановки $ (n + 1)! $, Вы можете объяснить, что каждый элемент присоединен к каждой перестановке остальных элементов.

Если вы хотите взглянуть на объяснение на примере, то this blog post предлагает один.