WorksMathematics
Heap-type permutation generation with a prescribed final arrangement
Abstract
Heap's algorithm generates all permutations of an array of n items, obtaining each one from its predecessor by a single swap. We determine the net permutation applied to the array by every complete recursive call: a transposition when the number of items is odd and at least three, and a cycle through all items when it is even. We show that the output of each call is a concatenation of right cosets of the symmetric group on one item fewer, and we prove a general formula: the order in which the items are parked at the last position may be chosen freely, every such order corresponds to exactly one valid schedule, and it determines the net permutation of the call. Two variants follow. In the cyclic variant a complete sweep over an even number of items rotates the array by one position. In the extremal variant, for even n, a sweep started from the identity ends in the lexicographically largest arrangement that any single-swap enumeration can leave; by a parity argument this is the reversal exactly when n is congruent to 2 modulo 4. The construction of the extremal variant is proved correct when n is divisible by 4 and verified by computer for all even n up to 10000.
Introduction
Motivation
Listing all permutations of objects is one of the oldest tasks in combinatorial computing. It underlies exhaustive search and brute-force optimisation, the testing of programs and hardware on all input orders, the verification of conjectures about small permutation groups, and the enumeration of orbits and of other structures indexed by permutations. For these uses the cost of producing each permutation matters, which has motivated minimal-change (Gray-code) methods, in which every permutation differs from its predecessor by a very small modification, so that per-permutation work is and the consumer can often update its own data incrementally instead of recomputing from scratch.1
ISSN subm. to DMTCS © by the authors by the author(s) Distributed under a Creative Commons Attribution 4.0 International License
Related work
Algorithms for permutation generation. The literature on generating permutations on computers goes back to the beginning of the electronic-computer era. The early account by Lehmer [13] of how to teach combinatorial generation to a computer, the generation by transpositions of Wells [26] and the procedure PERMUTE of Peck and Schrack [18] (ACM Algorithm 86) are among the first published methods. The method of Steinhaus, Johnson and Trotter, which produces each permutation from the previous one by an adjacent transposition, is described in Algorithm 115 of Trotter [25] and in the note of Johnson [8]; the name also recalls Steinhaus [24]. The method of Heap [5], the subject of this paper, uses a single swap of two arbitrary positions and a short recursive description. Subsequent work includes the algorithm of Langdon [12], the studies of permutation sequences by Ord-Smith [16, 17], the four algorithms of Ives [7], and the loopless algorithms of Ehrlich [3], which perform work in the worst case per permutation. Lexicographic enumeration, in which successive permutations are not close in the swap metric, is the basis of the “next permutation” functions of standard libraries (for example std::next_permutation in C++; see ISO/IEC [6]) and is treated in detail by Dijkstra [2] and Knuth [9]. The survey of Sedgewick [22] compares these and many other methods; it concluded that Heap’s method was, at the time, the most effective for computer generation of permutations. Textbook treatments are given by Nijenhuis and Wilf [15], Reingold et al. [19], Kreher and Stinson [11] and, most comprehensively, by Knuth [9].
Gray codes and Cayley graphs. A minimal-change listing of permutations is a Hamiltonian path in a Cayley graph of the symmetric group whose generators are the allowed “small changes”. Heap’s algorithm is such a path for the generating set of all transpositions. Kompel’makher and Liskovets [10] showed that a set of transpositions whose graph is a tree (for instance a star, i.e. the transpositions ) already yields a Hamiltonian path, and the Cayley graph of the star transpositions is the star graph studied as an interconnection network by Akers and Krishnamurthy [1]. Comprehensive surveys of the area, which also cover many other combinatorial objects, are due to Savage [21] and Mütze [14].
Correctness proofs and the final arrangement. Heap’s algorithm is usually justified by checking small cases or by an informal inductive argument; such arguments are available, for instance, in expository online material such as the Wikipedia article [27], and some of this material also notes properties of the array left by a complete run (the Wikipedia proof, for example, speaks of rotations of the array). To our knowledge, however, a treatment in terms of the net permutation of every recursive call, valid for both parities and expressed with the group structure, is not available in the literature we examined, although we make no claim to have searched exhaustively. Such a treatment is more than a matter of taste: when an enumeration is embedded in a larger computation (nested loops over several groups, repeated sweeps, restoring a data structure after a sweep), the final arrangement and its algebraic description are what the surrounding code needs.
Contributions
A self-contained primer on permutation notation (Section 2): two-line (“matrix”) notation; one-line notation (the bottom row only, which is how arrays are stored); cycle notation and its canonical form, with the rules and several examples; how to multiply and invert permutations in each notation; and how a swap of two array positions acts on them.
A proof by induction, in cycle notation, of the net permutation of every recursive call and of the structure of the output (Theorem 6).
A general net formula (Theorem 18): parking the items at the last position in an arbitrary order determines a unique valid schedule, and the net permutation is . All previous results are special cases.
Two new variants (§ 6.2 and § 7): a cyclic variant whose net permutation for even is , and a lexicographically extremal variant for even that ends in the lexicographically largest arrangement attainable by any single-swap enumeration, together with a parity bound showing which arrangement that is (reversal exactly when ).
A computational verification of all claims that are not proved (§ 9): exhaustive runs of the variants for small , and a check of the construction of the extremal variant for all even . The verification program and a C implementation of the three variants are publicly available [20].
We do not claim that the idea of reordering the swaps of Heap’s algorithm is new; what is new, to our knowledge, is the group-theoretic description of the whole family of Heap-type schedules and the use of it to prescribe the final arrangement.
Organisation
Section 2 is the notation primer. Section 3 defines the algorithm and the admissible schedules, Section 4 states the results for them and Section 5 proves them. Section 6 proves the general net formula, and Section 7 uses it to construct the extremal variant. Section 8 gives worked examples, Section 9 describes the computational verification, and Section 10 concludes.
Permutation notation
Let and let be the set of bijections ; . For we regard by letting a permutation of fix . We use two running examples in .
Two-line (matrix) notation
A permutation is written as a matrix with two rows: the top row lists and the bottom row lists the corresponding images.
The first matrix means , , , , . Each column is an arrow , so the columns may be permuted freely without changing the permutation; for instance
One-line notation (bottom row only)
Dropping the top row leaves the one-line notation :
This is exactly how an array of the numbers is stored in a program: a[i] = . We use square brackets for one-line notation to distinguish it from cycle notation.
Cycle notation
Start at and follow until you return to ; this gives one cycle. Repeat from the smallest element not yet used. For above: gives , and gives , so
Conventions: a cycle is read cyclically, ; cycles of length (fixed points) are omitted, and the identity is written ; disjoint cycles commute; to find , locate in its cycle and take the next entry (cyclically), or itself if does not occur. A cycle of length is an -cycle, a -cycle is a transposition. An -cycle is a product of transpositions, so its sign is ; the sign is multiplicative.
Canonical cycle notation
The cycle notation of Section 2.3 is not unique: every cycle can be rotated, and the cycles can be listed in any order. For instance can be written , , or . A canonical form fixes these choices, so that every permutation has exactly one representation; it makes permutations comparable by inspection, and it is the form in which the net permutations of this paper are tabulated. We use the following rules.
(C1) Rotate every cycle so that it begins with its smallest element.
(C2) List the cycles in increasing order of their first (smallest) elements.
(C3) Omit cycles of length (fixed points); the identity is written . (If a “complete” form is wanted, the fixed points are written as -cycles in their places according to (C2).)
The representation is unique because the smallest element of a cycle is unique and the cycles are disjoint, so their smallest elements are distinct and (C2) determines their order. The procedure of Section 2.3 (start from the smallest element not yet used, follow images until the cycle closes) produces (C1)–(C3) automatically. To test whether a written product of disjoint cycles is canonical, check that every cycle starts with its minimum and that these minima increase from left to right.
Examples.
has the canonical form ; the three other writings above violate (C1) or (C2). For the canonical form is .
The products computed in Section 2.5 are canonical as written: and . Note that is canonical (it starts with its minimum ) although it is not increasing.
The net permutation of classic Heap on items is , canonical as written. The expression of Theorem 6 is a cycle that ends with ; its canonical form is obtained by rotating it to start with 1.
The net permutation of the extremal variant (§ 7) for is in canonical form, while is the same permutation written non-canonically.
Other conventions. “Canonical cycle notation” is not used in the same sense by all authors, so the convention should always be stated. The fundamental transformation of Foata [4] [see also 23 §1.3] writes every cycle starting with its largest element and lists the cycles in increasing order of their largest elements; erasing the parentheses then gives a one-line permutation. Other authors keep the smallest element first but list the cycles in decreasing order of these elements. For above, the three conventions give
and the corresponding one-line words after erasing parentheses are and for the last two. To pass from our form to the largest-first form, rotate each cycle to start with its maximum and sort the cycles by their first entries. Our convention is the natural one for algorithms that discover cycles by scanning and for results stated, like ours, with a distinguished point (the point 1, or the point ).
Multiplication (composition)
We compose right to left: , i.e. acts first. (Some books compose left to right; with our convention products read like function composition.) Products are associative but not commutative. For our running example:
We show how each is obtained in each notation.
One-line notation. Use the entries of as indices into : . Here , , , , , giving . (In C: c[i] = s[t[i]].)
Two-line notation. Stack three rows: , then (the bottom row of ), then , obtained by looking up the middle entry in the top row of and reading what is below it. The product is the first and last rows:
Equivalently, reorder the columns of so that its top row equals the bottom row of and glue.
Cycle notation. Trace every point through the factors, from the rightmost factor to the leftmost. For : the point 1 goes in , in , and 5 is untouched by ; so . Next, in , in , 2 is untouched by ; so . Then , so , which closes the cycle . The points 3 and 4 return to themselves ( and ).
Inversion
The inverse undoes ; .
Two-line: swap the two rows, then sort the columns by the new top row. For : the swapped matrix has columns , , , , ; sorted, .
One-line: for every write at index , i.e. (in C:
inv[s[i]] = i). For : 1 goes to index 3, 2 to index 5, 3 to index 1, 4 to index 2, 5 to index 4, giving .Cycle: write every cycle backwards: .
Check: , and computed by the one-line rule gives the same array.
| Two-line | One-line | Cycles | |
| Product ( first) | stack over (rows , , ), keep first and last rows | c[i]=s[t[i]] | trace each point right to left |
| Inverse | swap rows, re-sort columns | inv[s[i]]=i | write each cycle backwards |
| Left product | swap the values in the bottom row | swap the values | see § 2.7 |
| Right product | swap the bottom entries of columns and (top row unchanged) | swap the entries at positions | see § 2.7 |
Table 1. How to multiply and invert in each notation.
Multiplying by a transposition
Because Heap’s algorithm only ever swaps two positions, products with a transposition are the important case. In one-line notation:
(left product) swaps the values and , wherever they occur: .
(right product) swaps the entries at positions and : .
Indeed changes the values, whereas reads at swapped indices. In cycle notation, multiplying by a transposition either splits a cycle (if and lie in the same cycle) or merges two cycles (if they lie in different cycles).
Permutations acting on arrays; states
An array has positions . A permutation acts on arrays by moving the item at position to position : the new array satisfies . Performing first and second has total effect . Exchanging the items at positions and is the action of the transposition , which is its own inverse.
Lemma 1 (Arrays are inverses). Applying to the identity array produces the array
that is, the one-line notation of .
Proof: The new array satisfies for all , that is, .
At any moment of an algorithm that starts from an array and only moves items, the current array is obtained from by a unique permutation , which we call the state (relative to ). The initial state is . Swapping positions and replaces the state by (a left product). If is the identity array, the current array is ; consistently, swapping the entries at positions of gives by § 2.7.
| step | swap | array | state (cycles) | state (one-line) | |
| 0 | — | — | |||
| 1 | |||||
| 2 | |||||
| 3 | |||||
| 4 | |||||
| 5 |
Table 2. The six arrays produced by Heap’s algorithm for and the corresponding states. Each new state is the previous one multiplied on the left by the swap. In one-line notation this swaps two values of the state, and equivalently two entries of the array. The last state is , the net permutation of Heap.
Example (Table 2). Going from step 1 to step 2: the state is multiplied on the left by . In cycle notation, : , , , so the product is . In one-line notation, the state has its values 1 and 3 exchanged, giving . On the array, the entries at positions 1 and 3 of are exchanged, giving .
Heap’s algorithm and its variants
The algorithm
Positions are numbered from 1. The procedure permutes the first positions of a global array :
if : output and return;
call ;
for : swap the items at positions and , then call .
The numbers form the schedule; the call on an array of length is the whole algorithm. In classic Heap’s algorithm
Between two consecutive outputs exactly one swap is performed: after an output the recursion returns to the first loop that still has rounds left, performs that round’s swap, and the next output follows without any further swap, because every call begins with a call to and so on down to . We will prove that all outputs are distinct, so the algorithm performs swaps.
Admissible schedules
Write and for even .
Definition 2 (Admissible schedule) A schedule is admissible if
(A1) for all , for every odd ;
(A2) for every even , the sequence defined by
is a permutation of .
Condition (A2) says that is obtained from some permutation by applying the transposition at the odd indices; so there are exactly admissible choices of for each even .
Definition 3 (Cyclic variant) The cyclic variant uses the odd- rule of the classic algorithm and, for even , the schedule
that is, , and otherwise; . Thus it performs the swaps : the first and last partners of the classic schedule are interchanged.
Lemma 4. The classic and the cyclic schedules are admissible. For even the classic schedule has and the cyclic one has ; for both have .
Proof. (A1) is built in. Classic: for odd , and for even ; since swaps only and (both odd), . Cyclic: , , and for the remaining indices (for odd with because fixes , for even by definition), so .
Net permutation and output states
Fix an admissible schedule. Start on an array and let denote the state relative to (§ 2.8); the swaps only involve positions , so , and they do not depend on the contents of the array.
Definition 5. The net permutation is the state at the end of a complete call . The output states are the states at which the successive outputs occur (so ).
Since the effect of a call does not depend on the contents, a call started in state (relative to some earlier array) ends in state and its outputs occur at the states .
Results
Theorem 6 (Structure of Heap-type algorithms). Let be an admissible schedule. For every :
(i) Net permutation. ; for odd , ; for even ,
a -cycle.
(ii) Output. The output states are pairwise distinct, hence a listing of all of ; consecutive output states differ by a transposition ( is a transposition); and the last one is .
(iii) Block structure. For the output of consists of consecutive blocks, the -th () being the right coset listed in the order of , where is the state at the start of the block. During block the item that started at position stays at position , where
and are a permutation of .
Corollary 7 (Classic Heap’s algorithm). ; for odd ; and for even
Corollary 8 (Cyclic variant). For the cyclic variant, for odd and for even . Consequently, for even a complete call HEAP rotates the array by one position to the right: .
Corollary 9 (Every -cycle occurs). Let be even. The map is a bijection from the admissible choices of onto the set of all -cycles of .
Proposition 10 (Parity obstruction). Let . In any procedure that outputs all permutations with consecutive outputs related by a single swap, the last state is an odd permutation. In particular it is never a -cycle for odd (a -cycle has sign ). For even the net permutation of HEAP is always odd, and the -cycles are odd.
Proofs
Three lemmas on products
Lemma 11 (Conjugation). For and a transposition : .
Proof. Let and . If , then and ; if similarly . If , then and the left-hand side fixes .
Lemma 12 (Star product). Let , let be distinct points. Then
the cycle .
Proof. Induction on . For both sides equal . Let and assume the claim for ; we prove it for points . By the induction hypothesis applied to ,
Apply first and then . The point goes to , which fixes. A point with goes to , which fixes since . The point goes to and then to . The point is fixed by and then goes to . So , as claimed. □
Lemma 13 (Inserting a point into a cycle). Let , let be a -cycle on (fixing ) and . Then is a -cycle, namely . In particular .
Proof. Compute on each point (apply first): ; ; and for . Starting from we get ; from then on, as long as the current point is neither nor , the map simply applies , so we continue . Since is a -cycle, the points are exactly the elements of , and . So the orbit of contains all points and is a single -cycle. □
Unwinding the recursion
Lemma 14 (Unwinding). Let , , and for . Define and for . Then in a call started in state :
(a) the -st of the calls to (“block ”) starts in state , its outputs occur at the states , and it ends in state ;
(b) , and
(c) during block the item at position is the one that started at position .
Proof. (a) Block 0 starts in state . A block that starts in state ends in state by the remark at the end of § 3; then the swap is performed and the next block starts in . The statement about the output states is the same remark. (b) is immediate from the recursion; is the state at the end of block , namely . (c) Every state in block has the form with , so fixes . The item now at position is the item with , i.e. , i.e. . □
Lemma 15 (Gluing). Let and suppose (ii) of Theorem 6 holds for . If (from Lemma 14) are pairwise distinct, then (ii) holds for and the output of is the concatenation of the blocks of (iii).
Proof. Distinctness. By Lemma 14(a), block consists of the states , which are pairwise distinct because the are. If is in block then . As the are distinct, no state lies in two blocks. So there are distinct output states, i.e. all of .
Consecutive states. Inside block , consecutive states and have quotient , a transposition by hypothesis. Between blocks and , the last state of block $m is (hypothesis (ii): the last state is ), and the first state of block is , so the quotient is the transposition .
Last state. The last output of HEAP() is the last output of its last block, at state by (2).
Proof of Theorem 6
We prove (i), (ii), (iii) together by induction on . The case is trivial: HEAP(1) outputs once, at the identity, so , (ii) holds, and (iii) is empty. Let and assume the theorem for .
Case odd,
Then is even and is a -cycle on , because is a permutation of (for this reads ). By (A1) all swaps equal , so for all .
Proof of (i). By (2), . By Lemma 13, , hence and
Proof of (iii). Here , so and with . We have , and otherwise. We claim for $1\le m\le k-1$. For this is . If with , then (as has order and does not fix , we have for e_{m+1}=\psi(e_m)=C^{-1}(e_m)=C^{-(m+1)}(1)$. The points , , are the distinct elements of (the orbit of under the -cycle ), and ; so are pairwise distinct.
Proof of (ii). Apply Lemma 15.
Case even,
By the induction hypothesis (i), equals if (since ) and equals if (since is odd and ). In both cases : is an involution, , and . Write , and . By Lemma 11,
Proof of (i). The word in (2) is : it has letters and letters , alternating, beginning and ending with . Since is odd, the indices alternate odd, even, , odd. Cut the word into consecutive pieces: for every odd , and the single letter for every even :
By (2), the piece belonging to is the transposition with for odd and for even ; this is exactly the sequence of (A2), a permutation of . Thus
Apply Lemma 12 with , and (so , ): the product equals , as claimed. Proof of (iii). Since all letters are involutions, by Lemma 14(b) (reverse the order of the factors and invert each). Cut this word as before into , , : if is even we get with ; if is odd we get with a last piece (there is no closing ). Here as in (2). Now if is even and if is odd. Each with moves only and , and by (A2), so fixes . Hence for , and . These are pairwise distinct.
Proof of (ii). Apply Lemma 15.
Proofs of the corollaries and of Proposition 10
Proof of Corollaries 7 and 8: By Lemma 4 both schedules are admissible, so Theorem 6(i) applies. Classic, even : , so , which after rotating to start at 1 is . Cyclic: , so . This permutation sends position to for and to 1; the item at position moves to and the item at position moves to position 1, which is the rotation claimed. For both give .
Proof of Corollary 9: By Theorem 6(i), . A -cycle of can be written in exactly one way as a sequence that ends with (read the cycle cyclically starting just after ), so the permutations correspond bijectively to the -cycles. The map given by for odd and for even is a bijection (as is an involution) onto the admissible choices of .
Proof of Proposition 10: The last state is a product of transpositions, one for each of the swaps (consecutive outputs differ by one swap and the last output occurs after the last swap). Each transposition has sign and is multiplicative, so the sign is because is even for . A -cycle has sign , which is for odd .
Remark 16 The proof shows where the odd/even dichotomy comes from. For odd the same swap is used in every round and the argument collapses to a power of a single -cycle : a -cycle has order , so the swaps telescope to . For even the inner net permutation is an involution, and conjugating by it turns the rounds into a product of star transpositions, which Lemma 12 evaluates as a single -cycle. The choice of the schedule affects only the order of the points in that cycle.
A general net formula: parking orders
Section 3 restricted the schedules by the admissibility conditions (A1) and (A2). In this section we drop all restrictions and describe every schedule at one level by the order in which items are “parked” at the last position. The result (Theorem 18) contains Theorem 6 as a special case and is the tool used in Section 7.
Setting
Fix and a permutation (so ); in applications , but nothing below uses this. Let be a schedule for level (each ), , and define as in Lemma 14
Thus and is the item (identified by its starting position) parked at position during block . We call valid for if are pairwise distinct. By the proof of Lemma 15 this is exactly the condition that the blocks lie in different right cosets of ; if and the schedules below level are valid, then is valid for if and only if HEAP outputs every permutation of exactly once. (If two parked items coincide, fixes and two blocks lie in the same coset, so outputs repeat.)
Lemma 17 (Path product). For pairwise distinct points :
Proof. Induction on ; is trivial. Write the product for as with by hypothesis, and apply first. Then ; ( fixes ); and for . So .
Theorem 18 (General net formula). Let , and let be any schedule for level .
(a) for all , and .
(b) If is valid for , then and
(c) The map is a bijection from the schedules valid for onto the orderings of . In particular there are exactly valid schedules.
(d) Consequently the possible net permutations of level are exactly the elements with a -cycle of , and a target is the net permutation of some valid schedule if and only if is a -cycle.
Proof. (a) Since and , we get , i.e. with . Because and we have , hence (recall ). By Lemma 11, , so
Again by Lemma 11, and since and , we have , so and . Induction from gives the stated product.
(b) If are distinct, Lemma 17 turns the product into the cycle , and .
(c) Injectivity: by (a), is determined by and , which in turn is determined by . Surjectivity: given an ordering of , define and recursively. Suppose the parked items of the first blocks are the prescribed ones; then , because and , so (as fixes and permutes ), and by the computation in (a) the item parked in block is . Hence the schedule exists, and its parked items are the prescribed, pairwise distinct ones.
(d) By (b) and (c), the nets are with , and as runs over all orderings, runs over all -cycles of (a -cycle has a unique cyclic representation starting at ). So for a -cycle if and only if is a -cycle. □
Corollary 19 (Counting). There are exactly valid Heap-type schedule families for items, i.e. choices of one valid schedule at each level .
Proof. By Theorem 18(c) there are valid schedules at level for each possible lower net , independently of ; multiply over . □
The cyclic variant in terms of parking orders
Corollary 20 (Parking orders of the classic and the cyclic variant). (i) For even , is an involution fixing , so and . The classic variant parks , the cyclic variant parks (increasing order).
(ii) For odd , the classic schedule parks (proof of Theorem 6(iii)). If the levels below are cyclic, and so (decreasing order), and indeed .
Hence the cyclic variant is the Heap-type algorithm that parks the items in increasing order at even levels and in decreasing order at odd levels.
Proof. (i) is Theorem 6(i),(iii) rewritten (the parking orders are , Lemma 4). (ii) The first claim is in the proof of Theorem 6; for and . For the product, let , i.e. , for , and . Since has order , Theorem 18(b) gives . Now , , and for , . So . □
A variant with lexicographically extremal final arrangement
The cyclic variant of Corollary 8 ends in a rotation of the array. It is natural to ask for an enumeration whose final arrangement, started from , is the lexicographically largest one, so that a complete sweep lists the arrangements “from the smallest to the largest”. We first show which arrangements are possible at all, then give a construction for even .
Which final arrangements are possible
Recall (Lemma 1) that if the state at the end is then the final array is , a permutation of the same sign as .
Proposition 21 (Lexicographically largest attainable arrangement). Let . For every procedure that lists all arrangements of an -array, starting from , with consecutive arrangements differing by one swap, the final array is an odd permutation. The lexicographically largest odd permutation is
Proof. By Proposition 10 the final state is odd, hence so is the final array. The reversal is a product of disjoint transpositions , so it is odd if and only if is odd, i.e. ; then it is the lexicographically largest permutation of all and in particular the largest odd one. Otherwise the reversal is even; the permutation that immediately precedes it in lexicographic order is obtained by exchanging its last two entries, i.e. , which has the opposite sign and is therefore odd, hence is the largest odd permutation. □
Thus for even the true reversal can be the final arrangement only when ; for (e.g. ) the best possible is . By Theorem 6 no admissible schedule can reach the reversal for , since the nets of admissible schedules are -cycles while the reversal is a product of disjoint transpositions; the construction below therefore uses a level that is not admissible. For even write for the target state: is the reversal if and
The construction
**Definition 22 (Extremal variant, even use the cyclic schedule. Level (odd) parks the items in the order
Level parks the items in the order given by the -cycle
provided this permutation is an -cycle. For the variant is the cyclic (= classic) one. The schedules and are obtained from these orders by Theorem 18(a): .
Thus the extremal variant coincides with the cyclic variant except at the two topmost levels, and level is defined by one explicit product of permutations; there is no need to search.
Theorem 23 (Extremal variant). Let be even.
(a) If is an -cycle, then the extremal variant lists all permutations with one swap between consecutive arrangements and its final array, started from , is : the lexicographically largest arrangement that any single-swap enumeration can leave (Proposition 21).
(b) is an -cycle whenever .
(c) is an -cycle for every even with (verified by computer, including ).
Proof of (a): By Corollary 8 and Theorem 6, levels are valid and . By Theorem 18(c) every parking order at level is valid for , so by Lemma 15 levels up to are valid. If is an -cycle, Theorem 18(d) gives a valid schedule at level with net , and Lemma 15 shows that Heap enumerates with one swap between consecutive arrangements. The final state is and by Lemma 1 the final array is .
Lemma 24 (Net of level for (mod 4)). Let , (mod 4), and let levels be cyclic and level use the order . Then
Proof: With , (of order ) and , Theorem 18(b) gives . Now for and , and for , , . Hence for ; ; ; . The odd points form one cycle, and another.
Proof of (b): For we have and , so is a 4-cycle. Let . Write , of length , and , of length . Since , and , so . The permutation moves only odd points: for odd , , . With the explicit above, is therefore given by
(For odd in the range, is even and fixed by ; for even , is odd and subtracts 4; for , .) Put and, for suitable ,
Then ; for (as ); for (as ); ; for (as ); for ; and . Hence the orbit of 1 is
It consists of points, and they are pairwise distinct: modulo 4 the points are (the values ), the points are (the values ), the points are (the values ) and the points are (the values ). So the orbit is all of and is an -cycle.
The case . Here the same reduction applies with a different explicit : for one finds (and we have verified by computer for ) that
with all other points fixed, a cycle of length , so that is again an explicit permutation (as modulo the cycle length). We did not find a closed-form description of its orbit comparable to the one in the proof of (b), because the orbit has several phases whose shape depends on . Part (c) was verified by computing and checking that the cycle through has length , for all even from 6 to 10000; exhaustive runs confirm the end-to-end behaviour for , and the final array for (§ 9).
Examples and remarks
Table 4 lists the schedules of the two top levels for and the resulting nets; the corresponding runs enumerate all permutations and end in the final arrays shown (checked exhaustively; for these are 3 628 800 arrangements).
Remark 25 1. No simpler rule found. We searched for a pair of simple parking orders (rotations of the increasing or decreasing order, and orders consisting of an increasing run followed by a decreasing run, or vice versa) at levels and that would give a -cycle for every ; for there is none, and the order at level in the construction has no obvious closed form. The rule above is simple in the sense that only two levels differ from the cyclic variant, level has an explicit order, and level is defined by one product of permutations, computable in time.
Per-level optimality fails. The tempting rule “every level ends in its own lexicographically largest attainable arrangement” is not realisable: the required cycle fails to be a -cycle for every even from 8 to 40 (while it succeeds for all odd and for ). The levels below the top must therefore be chosen to make the top level work, as in Definition 22.
Odd . For odd the same construction (cyclic below) succeeds only for and fails for $7\leq n\leq 31; we do not provide the variant for odd . Whether other choices at lower levels make the largest attainable arrangement reachable for odd is not investigated here.
Worked examples for
Table 5 lists the 24 arrays produced for by both variants, grouped in the four blocks of Theorem 6(iii) (each block is a run of HEAP(3) on the first three positions). The first block is identical. Between blocks the swap is for the classic schedule ( with giving ) and for the cyclic one (, ). The item parked at position 4 is the last entry of each array in a block; it is for the classic variant and for the cyclic one, as predicted by . The final arrays and are the entries for in Table 3.
| classic net | final array | cyclic net | final array | |
| 2 | same | same | ||
| 3 | same | same | ||
| 4 | ||||
| 5 | same | same | ||
| 6 | ||||
| 7 | same | same | ||
| 8 |
Table 3. Net permutations (Corollaries 7 and 8) and the array obtained when a complete call HEAP is run on . By Lemma 1 the final array is the one-line notation of . These entries were also confirmed by running the algorithm.
| block | classic variant (swap before block) | cyclic variant (swap before block) |
| 0 | — 1234 2134 3124 1324 2314 3214 | — 1234 2134 3124 1324 2314 3214 |
| 1 | 4213 2413 1423 4123 2143 1243 | 3241 2341 4321 3421 2431 4231 |
| 2 | 1342 3142 4132 1432 3412 4312 | 4132 1432 3412 4312 1342 3142 |
| 3 | 4321 3421 2431 4231 3241 2341 | 2143 1243 4213 2413 1423 4123 |
Table 5. All 24 arrays for (digits written without brackets).
Computational verification
All results of this paper are proved except part (c) of Theorem 23, the formula for stated for (mod 4) in § 7, and the negative statements of the final remark of that section. These were checked by computer, and so were the tables and the proved statements for small . We used two programs that were written independently from the definitions of this paper.
The first is a short Python program [20] that represents permutations as arrays and composes them as in § 2.5. It runs HEAP() directly on states, performing for each swap the left product of § 2.8, and checks the following.
For the classic and the cyclic variant and , all output states are distinct, consecutive states differ by a transposition, and the last state is the net permutation of Corollaries 7 and 8; this confirms Table 3.
For the extremal variant and , with the schedules obtained from the parking orders of Definition 22 by Theorem 18(a), the same properties hold and the last state is . The schedules, parking orders and net permutations of Table 4 are reproduced.
| level : order and schedule | level : order and schedule | net (canonical) | final array | |
| 4 | ; | ; | ||
| 6 | ; | ; | ||
| 8 | ; | ; | ||
| 10 | ; | ; |
Table 4. Schedules of the two topmost levels of the extremal variant (positions swapped with the last position in rounds ; levels are cyclic). For the final array is , with net .
For , a search over all schedule families finds exactly the valid ones of Corollary 19.
For every even with , the permutation of Definition 22 is an -cycle (Theorem 23(c)); for (mod 4) in this range, agrees with Lemma 24; and for (mod 4) with , agrees with the formula of § 7. Here is computed by Theorem 18(b) and the power by repeated squaring, so that each costs operations.
The statements on per-level optimality and on odd in the final remark of § 7.
The whole check takes about forty seconds on one processor core. The second program is the C library PERMGEN [20], which implements the three variants as an iterator that reports one swap per call. It builds the schedule of the extremal variant from Definition 22 and Theorem 18(a), and it computes the net permutation of a sweep from the schedule tables rather than from the closed forms. Its test driver checks, for every variant and every admissible , that all arrangements are distinct, that consecutive arrangements differ in exactly two positions, and that the final array, the net permutation and its sign agree with Corollaries 7 and 8 and Proposition 21; for and it checks the number of arrangements and the final array.
Conclusion
Using cycle notation we determined the net permutation of every recursive call of Heap’s algorithm, proved by induction that the output is a concatenation of right cosets of in with consecutive arrangements related by one transposition, and proved a general net formula in which the parking order may be chosen freely. The formula explains the odd/even dichotomy of the classic algorithm, yields the cyclic variant (net permutation for even ) and a variant for even whose final arrangement is the lexicographically largest attainable one, which a parity argument identifies as the reversal exactly when . The statements that are not proved were verified by computer.
Limitations and open questions.
The correctness of the extremal variant is proved for and verified by computer for all even ; a proof for (the orbit structure of ) is open.
We found no closed formula for the parking order at the top level and no variant for odd with the cyclic variant below it; whether other lower levels make the largest attainable arrangement reachable for odd is open.
A complete description of all schedules, beyond the choices per level of Theorem 18, in terms of their effect on later levels is left for future work.
AI Disclosure: We used Claude (Anthropic), interactively, to assist with the research, the software and the manuscript. It proposed and drafted candidate proofs by induction in cycle notation for the net-permutation results, the general parking-order formula and the parity bound (§ 4 to § 6); it helped to formulate the extremal schedule construction and to explore it computationally (§ 7); it wrote the C library and the Python program used for the computational verification (§ 9); it helped to draft, revise and typeset the text. The tool materially affected § 2 to § 9. The author specified the research questions and the variants to be studied, reviewed the proofs, the code and the results, checked the proofs against the computational results, and verified the correctness and originality of all content including references.
References
- [1]Sheldon B. Akers and Balakrishnan Krishnamurthy. A group-theoretic model for symmetric interconnection networks. IEEE Transactions on Computers, 38(4):555–566, 1989.DOI
- [2]Edsger W. Dijkstra. A Discipline of Programming. Prentice-Hall, 1976.
- [3]Gideon Ehrlich. Loopless algorithms for generating permutations, combinations, and other combinatorial configurations. Journal of the ACM, 20(3):500–513, 1973.DOI
- [4]Dominique Foata. On the Netto inversion number of a sequence. Proceedings of the American Mathematical Society, 19:236–240, 1968.DOI
- [5]B. R. Heap. Permutations by interchanges. The Computer Journal, 6(3):293–294, 1963.DOI
- [6]ISO/IEC. ISO/IEC 14882: Programming languages — C++. International Organization for Standardization, 2020.
- [7]F. M. Ives. Permutation enumeration: four new permutation algorithms. Communications of the ACM, 19(2):68–72, 1976.DOI
- [8]Selmer M. Johnson. Generation of permutations by adjacent transposition. Mathematics of Computation, 17:282–285, 1963.DOI
- [9]Donald E. Knuth. The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1. Addison–Wesley, 2011.
- [10]V. L. Kompel’makher and V. A. Liskovets. Sequential generation of arrangements by means of a basis of transpositions. Kibernetika (Kiev), 1975(3):17–21, 1975.
- [11]Donald L. Kreher and Douglas R. Stinson. Combinatorial Algorithms: Generation, Enumeration, and Search. CRC Press, 1999.
- [12]Glen G. Langdon, Jr. An algorithm for generating permutations. Communications of the ACM, 10(5):298–299, 1967.DOI
- [13]D. H. Lehmer. Teaching combinatorial tricks to a computer. In Combinatorial Analysis, volume 10 of Proceedings of Symposia in Applied Mathematics, pages 179–193. American Mathematical Society, 1960.DOI
- [14]Torsten Mütze. Combinatorial Gray codes — an updated survey. Electronic Journal of Combinatorics, 30(3):#DS26, 2023.arxiv.org/abs/2202.01280
- [15]Albert Nijenhuis and Herbert S. Wilf. Combinatorial Algorithms for Computers and Calculators. Academic Press, 2nd edition, 1978.
- [16]R. J. Ord-Smith. Generation of permutation sequences: Part 1. The Computer Journal, 13(2):152–155, 1970.
- [17]R. J. Ord-Smith. Generation of permutation sequences: Part 2. The Computer Journal, 14(2):136–139, 1971.
- [18]J. E. L. Peck and G. F. Schrack. Algorithm 86: Permute. Communications of the ACM, 5(4):208, 1962.DOI
- [19]Edward M. Reingold, Jurg Nievergelt, and Narsingh Deo. Combinatorial Algorithms: Theory and Practice. Prentice-Hall, 1977.
- [20]Luís M. S. Russo. Heap-Permutations: Heap-type permutation generation with a prescribed final arrangement. Software, version v1.0.0, Zenodo, 2026. URL https://doi.org/10.5281/zenodo.24311260.
- [21]Carla Savage. A survey of combinatorial Gray codes. SIAM Review, 39(4):605–629, 1997.DOI
- [22]Robert Sedgewick. Permutation generation methods. ACM Computing Surveys, 9(2):137–164, 1977.DOI
- [23]Richard P. Stanley. Enumerative Combinatorics, Vol. 1. Cambridge University Press, 2nd edition, 2012.
- [24]Hugo Steinhaus. One Hundred Problems in Elementary Mathematics. Basic Books, New York, 1964.
- [25]H. F. Trotter. Algorithm 115: Perm. Communications of the ACM, 5(8):434–435, 1962.DOI
- [26]Mark B. Wells. Generation of permutations by transposition. Mathematics of Computation, 15:192–195, 1961.DOI
- [27]Wikipedia contributors. Heap’s algorithm. https://en.wikipedia.org/wiki/Heap%27s_algorithm, 2026. Accessed 28 October 2026.