Heap's Algorithm

Heap's algorithm generates all possible permutations of n objects.

It generates each permutation from the previous one by interchanging a single pair of elements; the other n-2 elements are not disturbed

First set a counter i to 0. Now we perform the following steps repeatedly until i is equal to n.

We use the algorithm to generate the (n-1)! permutations of the first n-1 elements, adjoining the last element to each of these.

Thus we generate all of the permutations that end with the last element.

Then if n is odd, we switch the first element and the last one.

If n is even, we switch the i-th element with the last one.

Note that there's no difference between n even and n odd in the first iteration.

Now we add one to the counter i and repeat.

In each iteration, the algorithm will produce all of the permutations that end with the element that has just been moved to the "last" position.