Proving Heap's Algorithm for Generating Permutations

Question

I need to prove the correctness of Heap's algorithm for generating permutations. The pseudocode for it is as follows:

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]

(taken from Introduction to the Design and Analysis of Algorithms by Levitin)

I know I need to use induction to prove its correctness, but I'm not sure exactly how to go about doing so. I've proved mathematical equations but never algorithms.

I was thinking the proof would look something like this...

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 
??

I'm just not sure how to go about finishing the induction step. Am I even on the right track here? Any help would be greatly appreciated.

This paper from 1977 contains a nice proof: homepage.math.uiowa.edu/~goodman/22m150.dir/2007/… — le_m
– le_m, Commented Jun 18, 2016 at 0:56

Anton Shepelev · Accepted Answer · 2014-05-04 14:16:43Z

1

For n = 1, heapPermute is obviously correct. {1} is printed.

Assume heapPermute() outputs a set of n! permutations for a given n. Then

??

Now, given the first two assumptions, show that heapPermutate(n+1) returns all the (n+1)! permutations.

answered May 4, 2014 at 14:16

Anton Shepelev

1,05110 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Anton Shepelev Over a year ago

@IGNIS By the way, I accidently reinvented the algorithm myself but couldn't prove it. Neither did Heap provide a proof in his 1963 paper. Did you proive it?

Marcin Łoś · Accepted Answer · 2013-11-10 20:28:52Z

1

Yes, that sounds like a good approach. Think about how to recursively define a set of all permutations, i.e. how can be permutations of {1..n} be expressed in terms of permutations of {1.. n-1}. For this, recall the inductive proof that there are n! permutations. How does the inductive step proceed there?

answered Nov 10, 2013 at 20:28

Marcin Łoś

3,2761 gold badge21 silver badges21 bronze badges

Comments

mrrusof · Accepted Answer · 2016-06-18 00:43:17Z

0

A recursive approach is definitely the way to go. Given your first two steps, to prove that heapPermutate(n+1) returns all the $(n+1)!$ permutations, you may want to explain that each element is adjoined to each permutation of the rest of the elements.

If you would like to have a look at an explanation by example, this blog post provides one.

answered Jun 18, 2016 at 0:43

mrrusof

3622 silver badges8 bronze badges

Collectives™ on Stack Overflow

Proving Heap's Algorithm for Generating Permutations

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related