Heap's algorithm

Heap's <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> generates all possible <a href="/facts/Permutation/JSw9ukmv">permutations</a> of n objects. It was first proposed by B. R. Heap in 1963. The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other n−2 elements are not disturbed. In a 1977 review of permutation-generating algorithms, <a href="/facts/Robert_Sedgewick_(computer_scientist)/f1lY2MFL">Robert Sedgewick</a> concluded that it was at that time the most effective algorithm for generating permutations by computer.
The <a href="/facts/Sequence/gV2S4uqp">sequence</a> of permutations of n objects generated by Heap's algorithm is the beginning of the sequence of permutations of n+1 objects. So there is one infinite sequence of permutations generated by Heap's algorithm (sequence A280318 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>).

Heap's algorithm open-in-new

Heap's algorithm