Generate All Permutations - Heap Algorithm

A common problem that shows up often is to generate all the possible permutations for a set of things. Here permutation is being used in the strict mathematical sense. For example, all the permutations of [ 1, 2, 3 ] are

1. [ 1, 2, 3 ]
2. [ 1, 3, 2 ]
3. [ 2, 1, 3 ]
4. [ 2, 3, 1 ]
5. [ 3, 1, 2 ]
6. [ 3, 2, 1 ]

Notice that the above results in 6 possibilities. This corresponds to 3 x 2 x 1 = 3! = 6. The "!" is mathematical notation for factorial. If you are interested in a general discussion about combinations and permutations and factorials, check out Combinations and Permutations by MathIsFun.Com. For those who want a strict definition of the problem we are going to work on permutations without repetition where we choose all the entries.

If you were in a hurry and the number of entities that had to consider were small and you weren't familiar w/ various algorithms, nested loops could be used to generate all the permutations. However, the nested loop approach does not scale because you don't want to change the code by adding / removing loops each time change the number of entities that have to consider.

Luckly, we can avoid nested loops by using the Heap algorithm. The original paper Permutations by Interchanges by B. R. Heap (\[Oxford Journals - The Computer Journal (1963) 6 (3): 293-298. doi: 10.1093/comjnl/6.3.293)\] can be freely obtained by clicking here. Later on, another article on the topic was Permutation Generation Methods by Robert Sedgewick - 1977 - ACM. Unfortunately, to obtain this article, you are going to have to pay for it. Luckly, Robert Sedgewick posted material on Heap's algorithm at Princeton. To obtain that material, click here.

The above "official" material can be supplemented by the following material found on the web

1. Stack Overflow: Algorithm to generate all possible permutations of a list?
2. Wikipedia: Heap's Algorithm