betaFeedback

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 nn 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 O(1)O(1) 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 O(1)O(1) 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 (1 i)(1\ i)) 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

  1. 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.

  1. A proof by induction, in cycle notation, of the net permutation of every recursive call and of the structure of the output (Theorem 6).

  1. A general net formula (Theorem 18): parking the items at the last position in an arbitrary order e1,…,ek−1e_1,\ldots,e_{k-1} determines a unique valid schedule, and the net permutation is πk−1k(k e1 ⋯ ek−1)\pi_{k-1}^{k}(k\ e_1\ \cdots\ e_{k-1}). All previous results are special cases.

  1. Two new variants (§ 6.2 and § 7): a cyclic variant whose net permutation for even kk is (1 2 ⋯ k)(1\ 2\ \cdots\ k), and a lexicographically extremal variant for even nn 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 n≡2(mod4)n \equiv2 \pmod{4}).

  1. A computational verification of all claims that are not proved (§ 9): exhaustive runs of the variants for small nn, and a check of the construction of the extremal variant for all even n≤10000n \le10000. 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 [n]={1,…,n}[n] = \{1,\ldots,n\} and let SnS_n be the set of bijections σ:[n]→[n]\sigma: [n] \to[n]; ∣Sn∣=n!|S_n| = n!. For k≤nk \le n we regard Sk⊆SnS_k \subseteq S_n by letting a permutation of [k][k] fix k+1,…,nk+1,\ldots,n. We use two running examples in S5S_5.

Two-line (matrix) notation

A permutation is written as a matrix with two rows: the top row lists 1,2,…,n1,2,\ldots,n and the bottom row lists the corresponding images.

σ=(1234535124),τ=(1234523154)\sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 2 & 4 \end{pmatrix}, \qquad \tau= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4 \end{pmatrix}

The first matrix means σ(1)=3\sigma(1)=3, σ(2)=5\sigma(2)=5, σ(3)=1\sigma(3)=1, σ(4)=2\sigma(4)=2, σ(5)=4\sigma(5)=4. Each column is an arrow x↦σ(x)x \mapsto\sigma(x), so the columns may be permuted freely without changing the permutation; for instance

σ=(2514354321)\sigma= \begin{pmatrix} 2 & 5 & 1 & 4 & 3 \\ 5 & 4 & 3 & 2 & 1 \end{pmatrix}

One-line notation (bottom row only)

Dropping the top row leaves the one-line notation [σ(1) σ(2) ⋯ σ(n)][\sigma(1)\ \sigma(2)\ \cdots\ \sigma(n)]:

σ=[3 5 1 2 4],τ=[2 3 1 5 4].\sigma=[3\ 5\ 1\ 2\ 4],\qquad\tau=[2\ 3\ 1\ 5\ 4].

This is exactly how an array of the numbers 1,…,n1,\ldots,n is stored in a program: a[i] = σ(i)\sigma(i). We use square brackets for one-line notation to distinguish it from cycle notation.

Cycle notation

Start at 11 and follow x↦σ(x)x\mapsto\sigma(x) until you return to 11; this gives one cycle. Repeat from the smallest element not yet used. For σ\sigma above: 1↦3↦11\mapsto3\mapsto1 gives (1 3)(1\ 3), and 2↦5↦4↦22\mapsto5\mapsto4\mapsto2 gives (2 5 4)(2\ 5\ 4), so

σ=(1 3)(2 5 4),τ=(1 2 3)(4 5).\sigma=(1\ 3)(2\ 5\ 4),\qquad\tau=(1\ 2\ 3)(4\ 5).

Conventions: a cycle is read cyclically, (a1 a2 ⋯ am)=(a2 ⋯ am a1)(a_1\ a_2\ \cdots\ a_m)=(a_2\ \cdots\ a_m\ a_1); cycles of length 11 (fixed points) are omitted, and the identity is written id⁡\operatorname{id}; disjoint cycles commute; to find σ(x)\sigma(x), locate xx in its cycle and take the next entry (cyclically), or xx itself if xx does not occur. A cycle of length mm is an mm-cycle, a 22-cycle is a transposition. An mm-cycle is a product of m−1m-1 transpositions, so its sign is (−1)m−1(-1)^{m-1}; the sign sgn⁡\operatorname{sgn} 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 σ=[3 5 1 2 4]\sigma=[3\ 5\ 1\ 2\ 4] can be written (1 3)(2 5 4)(1\ 3)(2\ 5\ 4), (3 1)(2 5 4)(3\ 1)(2\ 5\ 4), (2 5 4)(1 3)(2\ 5\ 4)(1\ 3) or (5 4 2)(3 1)(5\ 4\ 2)(3\ 1). 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 11 (fixed points); the identity is written id⁡\operatorname{id}. (If a “complete” form is wanted, the fixed points are written as 11-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.

  • σ=[3 5 1 2 4]\sigma=[3\ 5\ 1\ 2\ 4] has the canonical form (1 3)(2 5 4)(1\ 3)(2\ 5\ 4); the three other writings above violate (C1) or (C2). For τ=[2 3 1 5 4]\tau=[2\ 3\ 1\ 5\ 4] the canonical form is (1 2 3)(4 5)(1\ 2\ 3)(4\ 5).

  • The products computed in Section 2.5 are canonical as written: στ=(1 5 2)\sigma\tau=(1\ 5\ 2) and τσ=(2 4 3)\tau\sigma=(2\ 4\ 3). Note that (2 4 3)(2\ 4\ 3) is canonical (it starts with its minimum 22) although it is not increasing.

  • The net permutation of classic Heap on k=6k=6 items is (1 6 5 2 3 4)(1\ 6\ 5\ 2\ 3\ 4), canonical as written. The expression (b1 ⋯ bk−1 k)(b_1\ \cdots\ b_{k-1}\ k) of Theorem 6 is a cycle that ends with kk; its canonical form is obtained by rotating it to start with 1.

  • The net permutation of the extremal variant (§ 7) for n=8n=8 is (1 7 2 8)(3 6)(4 5)(1\ 7\ 2\ 8)(3\ 6)(4\ 5) in canonical form, while (8 1 7 2)(6 3)(5 4)(8\ 1\ 7\ 2)(6\ 3)(5\ 4) 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 σ\sigma above, the three conventions give

(1 3)(2 5 4)(this paper),(1\ 3)(2\ 5\ 4) \qquad\text{(this paper),}
(3 1)(5 4 2)(largest first, increasing),(3\ 1)(5\ 4\ 2) \qquad\text{(largest first, increasing),}
(2 5 4)(1 3)(smallest first, decreasing),(2\ 5\ 4)(1\ 3) \qquad\text{(smallest first, decreasing),}

and the corresponding one-line words after erasing parentheses are [ 3 1 5 4 2 ][\,3\ 1\ 5\ 4\ 2\,] and [ 2 5 4 1 3 ][\,2\ 5\ 4\ 1\ 3\,] 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 1,2,…,n1,2,\ldots,n and for results stated, like ours, with a distinguished point (the point 1, or the point kk).

Multiplication (composition)

We compose right to left: (στ)(x)=σ(τ(x))(\sigma\tau)(x)=\sigma(\tau(x)), i.e. τ\tau 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:

στ=[ 5 1 3 4 2 ]=(1 5 2),τσ=[ 1 4 2 3 5 ]=(2 4 3).\sigma\tau=[\,5\ 1\ 3\ 4\ 2\,]=(1\ 5\ 2),\qquad\tau\sigma=[\,1\ 4\ 2\ 3\ 5\,]=(2\ 4\ 3).

We show how each is obtained in each notation.

One-line notation. Use the entries of τ\tau as indices into σ\sigma: (στ)[i]=σ[τ[i]](\sigma\tau)[i]=\sigma[\tau[i]]. Here σ[τ[1]]=σ[2]=5\sigma[\tau[1]]=\sigma[2]=5, σ[τ[2]]=σ[3]=1\sigma[\tau[2]]=\sigma[3]=1, σ[τ[3]]=σ[1]=3\sigma[\tau[3]]=\sigma[1]=3, σ[τ[4]]=σ[5]=4\sigma[\tau[4]]=\sigma[5]=4, σ[τ[5]]=σ[4]=2\sigma[\tau[5]]=\sigma[4]=2, giving [ 5 1 3 4 2 ][\,5\ 1\ 3\ 4\ 2\,]. (In C: c[i] = s[t[i]].)

Two-line notation. Stack three rows: xx, then τ(x)\tau(x) (the bottom row of τ\tau), then σ(τ(x))\sigma(\tau(x)), obtained by looking up the middle entry in the top row of σ\sigma and reading what is below it. The product is the first and last rows:

(123452315451342)⟹στ=(1234551342)\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 2 & 3 & 1 & 5 & 4\\ 5 & 1 & 3 & 4 & 2 \end{pmatrix} \Longrightarrow \sigma\tau= \begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 5 & 1 & 3 & 4 & 2 \end{pmatrix}

Equivalently, reorder the columns of σ\sigma so that its top row equals the bottom row of τ\tau and glue.

Cycle notation. Trace every point through the factors, from the rightmost factor to the leftmost. For στ=(1 3)(2 5 4)⋅(1 2 3)(4 5)\sigma\tau=(1\ 3)(2\ 5\ 4)\cdot(1\ 2\ 3)(4\ 5): the point 1 goes 1→21\to2 in (1 2 3)(1\ 2\ 3), 2→52\to5 in (2 5 4)(2\ 5\ 4), and 5 is untouched by (1 3)(1\ 3); so 1↦51\mapsto5. Next, 5→45\to4 in (4 5)(4\ 5), 4→24\to2 in (2 5 4)(2\ 5\ 4), 2 is untouched by (1 3)(1\ 3); so 5↦25\mapsto2. Then 2→3→3→12\to3\to3\to1, so 2↦12\mapsto1, which closes the cycle (1 5 2)(1\ 5\ 2). The points 3 and 4 return to themselves (3→1→1→33\to1\to1\to3 and 4→5→4→44\to5\to4\to4).

Inversion

The inverse σ−1\sigma^{-1} undoes σ\sigma; (στ)−1=τ−1σ−1(\sigma\tau)^{-1}=\tau^{-1}\sigma^{-1}.

  • Two-line: swap the two rows, then sort the columns by the new top row. For σ\sigma: the swapped matrix has columns 3→13\to1, 5→25\to2, 1→31\to3, 2→42\to4, 4→54\to5; sorted, σ−1=(1234534152)\sigma^{-1}=\begin{pmatrix}1&2&3&4&5\\3&4&1&5&2\end{pmatrix}.

  • One-line: for every ii write ii at index σ[i]\sigma[i], i.e. σ−1[σ[i]]=i\sigma^{-1}[\sigma[i]]=i (in C: inv[s[i]] = i). For σ=[3 5 1 2 4]\sigma=[3\ 5\ 1\ 2\ 4]: 1 goes to index 3, 2 to index 5, 3 to index 1, 4 to index 2, 5 to index 4, giving [3 4 1 5 2][3\ 4\ 1\ 5\ 2].

  • Cycle: write every cycle backwards: σ−1=(1 3)(4 5 2)=(1 3)(2 4 5)\sigma^{-1}=(1\ 3)(4\ 5\ 2)=(1\ 3)(2\ 4\ 5).

Check: (στ)−1=(1 5 2)−1=(2 5 1)=(1 2 5)=[2 5 3 4 1](\sigma\tau)^{-1}=(1\ 5\ 2)^{-1}=(2\ 5\ 1)=(1\ 2\ 5)=[2\ 5\ 3\ 4\ 1], and τ−1σ−1\tau^{-1}\sigma^{-1} computed by the one-line rule gives the same array.

Two-lineOne-lineCycles
Product στ\sigma\tau (τ\tau first)stack τ\tau over σ\sigma (rows xx, τ(x)\tau(x), σ(τ(x))\sigma(\tau(x))), keep first and last rowsc[i]=s[t[i]]trace each point right to left
Inverse σ−1\sigma^{-1}swap rows, re-sort columnsinv[s[i]]=iwrite each cycle backwards
Left product (i j)σ(i\ j)\sigmaswap the values i,ji,j in the bottom rowswap the values i,ji,jsee § 2.7
Right product σ(i j)\sigma(i\ j)swap the bottom entries of columns ii and jj (top row unchanged)swap the entries at positions i,ji,jsee § 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 (i j)(i\ j) are the important case. In one-line notation:

  • (i j) σ(i\ j)\ \sigma (left product) swaps the values ii and jj, wherever they occur: (2 4)[3 5 1 2 4]=[3 5 1 4 2](2\ 4)[3\ 5\ 1\ 2\ 4]=[3\ 5\ 1\ 4\ 2].

  • σ(i j)\sigma(i\ j) (right product) swaps the entries at positions ii and jj: [3 5 1 2 4](2 4)=[3 2 1 5 4][3\ 5\ 1\ 2\ 4](2\ 4)=[3\ 2\ 1\ 5\ 4].

Indeed ((i j)σ)(x)=(i j)(σ(x))((i\ j)\sigma)(x)=(i\ j)(\sigma(x)) changes the values, whereas (σ(i j))(x)=σ((i j)(x))(\sigma(i\ j))(x)=\sigma((i\ j)(x)) reads σ\sigma at swapped indices. In cycle notation, multiplying by a transposition either splits a cycle (if ii and jj lie in the same cycle) or merges two cycles (if they lie in different cycles).

Permutations acting on arrays; states

An array a=[a1 ⋯ an]a=[a_1\ \cdots\ a_n] has positions 1,…,n1,\ldots,n. A permutation σ\sigma acts on arrays by moving the item at position pp to position σ(p)\sigma(p): the new array bb satisfies bσ(p)=apb_{\sigma(p)}=a_p. Performing σ1\sigma_1 first and σ2\sigma_2 second has total effect σ2σ1\sigma_2\sigma_1. Exchanging the items at positions ii and jj is the action of the transposition (i j)(i\ j), which is its own inverse.

Lemma 1 (Arrays are inverses). Applying σ\sigma to the identity array [1 2 ⋯ n][1\ 2\ \cdots\ n] produces the array

[σ−1(1) ⋯ σ−1(n)],[\sigma^{-1}(1)\ \cdots\ \sigma^{-1}(n)],

that is, the one-line notation of σ−1\sigma^{-1}.

Proof: The new array satisfies bσ(p)=pb_{\sigma(p)}=p for all pp, that is, bq=σ−1(q)b_q=\sigma^{-1}(q).

At any moment of an algorithm that starts from an array xx and only moves items, the current array is obtained from xx by a unique permutation ω\omega, which we call the state (relative to xx). The initial state is id\mathrm{id}. Swapping positions ii and jj replaces the state ω\omega by (i j)ω(i\ j)\omega (a left product). If xx is the identity array, the current array is [ω−1][\omega^{-1}]; consistently, swapping the entries at positions i,ji,j of [ω−1][\omega^{-1}] gives ω−1(i j)=((i j)ω)−1\omega^{-1}(i\ j)=((i\ j)\omega)^{-1} by § 2.7.

step mmswaparray [ω−1][\omega^{-1}]state ωm\omega_m (cycles)state ωm\omega_m (one-line)ωm=(swap) ωm−1\omega_m=(\text{swap})\ \omega_{m-1}
0—[1 2 3][1\ 2\ 3]id\mathrm{id}[1 2 3][1\ 2\ 3]—
1(1 2)(1\ 2)[2 1 3][2\ 1\ 3](1 2)(1\ 2)[2 1 3][2\ 1\ 3](1 2)id(1\ 2)\mathrm{id}
2(1 3)(1\ 3)[3 1 2][3\ 1\ 2](1 2 3)(1\ 2\ 3)[2 3 1][2\ 3\ 1](1 3)(1 2)(1\ 3)(1\ 2)
3(1 2)(1\ 2)[1 3 2][1\ 3\ 2](2 3)(2\ 3)[1 3 2][1\ 3\ 2](1 2)(1 2 3)(1\ 2)(1\ 2\ 3)
4(1 3)(1\ 3)[2 3 1][2\ 3\ 1](1 3 2)(1\ 3\ 2)[3 1 2][3\ 1\ 2](1 3)(2 3)(1\ 3)(2\ 3)
5(1 2)(1\ 2)[3 2 1][3\ 2\ 1](1 3)(1\ 3)[3 2 1][3\ 2\ 1](1 2)(1 3 2)(1\ 2)(1\ 3\ 2)

Table 2. The six arrays produced by Heap’s algorithm for n=3n=3 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 (1 3)(1\ 3), the net permutation of Heap(3)(3).

Example (Table 2). Going from step 1 to step 2: the state is multiplied on the left by (1 3)(1\ 3). In cycle notation, (1 3)(1 2)(1\ 3)(1\ 2): 1→2→21\to2\to2, 2→1→32\to1\to3, 3→3→13\to3\to1, so the product is (1 2 3)(1\ 2\ 3). In one-line notation, the state [2 1 3][2\ 1\ 3] has its values 1 and 3 exchanged, giving [2 3 1][2\ 3\ 1]. On the array, the entries at positions 1 and 3 of [2 1 3][2\ 1\ 3] are exchanged, giving [3 1 2]=[(2 3 1)−1][3\ 1\ 2]=[ (2\ 3\ 1)^{-1}].

Heap’s algorithm and its variants

The algorithm

Positions are numbered from 1. The procedure Heap⁡(k)\operatorname{Heap}(k) permutes the first kk positions of a global array aa:

  1. if k=1k = 1: output aa and return;

  2. call Heap⁡(k−1)\operatorname{Heap}(k-1);

  3. for i=1,2,…,k−1i = 1, 2, \ldots, k-1: swap the items at positions sk(i)s_k(i) and kk, then call Heap⁡(k−1)\operatorname{Heap}(k-1).

The numbers sk(i)∈{1,…,k−1}s_k(i) \in\{1,\ldots,k-1\} form the schedule; the call Heap⁡(n)\operatorname{Heap}(n) on an array of length nn is the whole algorithm. In classic Heap’s algorithm

sk(i)={1k odd,ik even.s_k(i) = \begin{cases} 1 & k\ \text{odd},\\ i & k\ \text{even}. \end{cases}

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 Heap⁡(k′)\operatorname{Heap}(k') begins with a call to Heap⁡(k′−1)\operatorname{Heap}(k'-1) and so on down to Heap⁡(1)\operatorname{Heap}(1). We will prove that all n!n! outputs are distinct, so the algorithm performs n!−1n! - 1 swaps.

Admissible schedules

Write ι2=id⁡\iota_2 = \operatorname{id} and ιk=(1 k−1)\iota_k = (1\ k-1) for even k≥4k \ge4.

Definition 2 (Admissible schedule) A schedule s=(sk)k≥2s = (s_k)_{k\ge2} is admissible if

(A1) sk(i)=1s_k(i) = 1 for all ii, for every odd k≥3k \ge3;

(A2) for every even k≥2k \ge2, the sequence bk=(bk(1),…,bk(k−1))b_k = (b_k(1), \ldots, b_k(k-1)) defined by

bk(i)={ιk(sk(i))i odd,sk(i)i even,b_k(i) = \begin{cases} \iota_k(s_k(i)) & i\ \text{odd},\\ s_k(i) & i\ \text{even}, \end{cases}

is a permutation of {1,…,k−1}\{1,\ldots,k-1\}.

Condition (A2) says that sks_k is obtained from some permutation bkb_k by applying the transposition ιk\iota_k at the odd indices; so there are exactly (k−1)!(k-1)! admissible choices of sks_k for each even kk.

Definition 3 (Cyclic variant) The cyclic variant uses the odd-kk rule of the classic algorithm and, for even k≥4k \ge4, the schedule

sk=(k−1,2,3,…,k−2,1),s_k = (k-1, 2, 3, \ldots, k-2, 1),

that is, sk(1)=k−1s_k(1) = k-1, sk(k−1)=1s_k(k-1) = 1 and sk(i)=is_k(i) = i otherwise; s2=(1)s_2 = (1). Thus it performs the swaps (k−1 k),(2 k),(3 k),…,(k−2 k),(1 k)(k-1\ k), (2\ k), (3\ k), \ldots, (k-2\ k), (1\ k): the first and last partners of the classic schedule are interchanged.

Lemma 4. The classic and the cyclic schedules are admissible. For even k≥4k \ge4 the classic schedule has bk=(k−1,2,3,…,k−2,1)b_k=(k-1,2,3,\ldots,k-2,1) and the cyclic one has bk=(1,2,3,…,k−1)b_k=(1,2,3,\ldots,k-1); for k=2k=2 both have b2=(1)b_2=(1).

Proof. (A1) is built in. Classic: bk(i)=ιk(i)b_k(i)=\iota_k(i) for odd ii, and bk(i)=ib_k(i)=i for even ii; since ιk\iota_k swaps only 11 and k−1k-1 (both odd), bk=(k−1,2,…,k−2,1)b_k=(k-1,2,\ldots,k-2,1). Cyclic: bk(1)=ιk(k−1)=1b_k(1)=\iota_k(k-1)=1, bk(k−1)=ιk(1)=k−1b_k(k-1)=\iota_k(1)=k-1, and bk(i)=ib_k(i)=i for the remaining indices (for odd ii with 3≤i≤k−33\le i\le k-3 because ιk\iota_k fixes ii, for even ii by definition), so bk=(1,2,…,k−1)b_k=(1,2,\ldots,k-1).

Net permutation and output states

Fix an admissible schedule. Start HEAP(k)\mathrm{HEAP}(k) on an array xx and let ω\omega denote the state relative to xx (§ 2.8); the swaps only involve positions ≤k\le k, so ω∈Sk\omega\in S_k, and they do not depend on the contents of the array.

Definition 5. The net permutation πk∈Sk\pi_k\in S_k is the state at the end of a complete call HEAP(k)\mathrm{HEAP}(k). The output states σk(1),…,σk(k!)\sigma_k^{(1)},\ldots,\sigma_k^{(k!)} are the states at which the successive outputs occur (so σk(1)=id\sigma_k^{(1)}=\mathrm{id}).

Since the effect of a call does not depend on the contents, a call started in state θ\theta (relative to some earlier array) ends in state πkθ\pi_k\theta and its outputs occur at the states σk(j)θ\sigma_k^{(j)}\theta.

Results

Theorem 6 (Structure of Heap-type algorithms). Let ss be an admissible schedule. For every k≥1k\ge1:

(i) Net permutation. π1=id\pi_1=\mathrm{id}; for odd k≥3k\ge3, πk=(1 k)\pi_k=(1\ k); for even k≥2k\ge2,

πk=(bk(1) bk(2) ⋯ bk(k−1) k),\pi_k=(b_k(1)\ b_k(2)\ \cdots\ b_k(k-1)\ k),

a kk-cycle.

(ii) Output. The output states σk(1),…,σk(k!)\sigma_k^{(1)},\ldots,\sigma_k^{(k!)} are pairwise distinct, hence a listing of all of SkS_k; consecutive output states differ by a transposition (σk(j+1)(σk(j))−1\sigma_k^{(j+1)}(\sigma_k^{(j)})^{-1} is a transposition); and the last one is σk(k!)=πk\sigma_k^{(k!)}=\pi_k.

(iii) Block structure. For k≥2k\ge2 the output of HEAP(k)\mathrm{HEAP}(k) consists of kk consecutive blocks, the mm-th (m=0,…,k−1m=0,\ldots,k-1) being the right coset Sk−1θmS_{k-1}\theta_m listed in the order of HEAP(k−1)\mathrm{HEAP}(k-1), where θm\theta_m is the state at the start of the block. During block mm the item that started at position eme_m stays at position kk, where

e0=k,em={bk(m)k even,πk−1−m(1)k odd,1≤m≤k−1,\begin{aligned} e_0&=k, \qquad e_m= \begin{cases} b_k(m) & k\text{ even},\\ \pi_{k-1}^{-m}(1) & k\text{ odd}, \end{cases} \qquad1\le m\le k-1, \end{aligned}

and e0,…,ek−1e_0,\ldots,e_{k-1} are a permutation of {1,…,k}\{1,\ldots,k\}.

Corollary 7 (Classic Heap’s algorithm). π2=(1 2)\pi_2=(1\ 2); πk=(1 k)\pi_k=(1\ k) for odd k≥3k\ge3; and for even k≥4k\ge4

πk=(1 k k−1 2 3 ⋯ k−2).\pi_k=(1\ k\ k-1\ 2\ 3\ \cdots\ k-2).

Corollary 8 (Cyclic variant). For the cyclic variant, πk=(1 k)\pi_k=(1\ k) for odd k≥3k\geq3 and πk=(1 2 3 ⋯ k)\pi_k=(1\ 2\ 3\ \cdots\ k) for even k≥2k\geq2. Consequently, for even kk a complete call HEAP(k)(k) rotates the array by one position to the right: [a1 a2 ⋯ ak]↦[ak a1 ⋯ ak−1][a_1\ a_2\ \cdots\ a_k]\mapsto[a_k\ a_1\ \cdots\ a_{k-1}].

Corollary 9 (Every kk-cycle occurs). Let k≥2k\geq2 be even. The map sk↦πks_k\mapsto\pi_k is a bijection from the (k−1)!(k-1)! admissible choices of sks_k onto the set of all kk-cycles of SkS_k.

Proposition 10 (Parity obstruction). Let k≥2k\geq2. In any procedure that outputs all k!k! permutations with consecutive outputs related by a single swap, the last state is an odd permutation. In particular it is never a kk-cycle for odd kk (a kk-cycle has sign (−1)k−1=+1(-1)^{k-1}=+1). For even kk the net permutation of HEAP(k)(k) is always odd, and the kk-cycles are odd.

Proofs

Three lemmas on products

Lemma 11 (Conjugation). For γ∈Sn\gamma\in S_n and a transposition (i j)(i\ j): γ(i j)γ−1=(γ(i) γ(j))\gamma(i\ j)\gamma^{-1}=(\gamma(i)\ \gamma(j)).

Proof. Let x∈[n]x\in[n] and y=γ−1(x)y=\gamma^{-1}(x). If y=iy=i, then x=γ(i)x=\gamma(i) and γ(i j)γ−1(x)=γ(j)\gamma(i\ j)\gamma^{-1}(x)=\gamma(j); if y=jy=j similarly γ(j)↦γ(i)\gamma(j)\mapsto\gamma(i). If y∉{i,j}y\notin\{i,j\}, then x∉{γ(i),γ(j)}x\notin\{\gamma(i),\gamma(j)\} and the left-hand side fixes xx.

Lemma 12 (Star product). Let r≥1r\geq1, let a1,…,ar,za_1,\ldots,a_r,z be distinct points. Then

(a1 z)(a2 z)⋯(ar z)=(z ar ar−1 ⋯ a1).(a_1\ z)(a_2\ z)\cdots(a_r\ z)=(z\ a_r\ a_{r-1}\ \cdots\ a_1).

the cycle z↦ar↦ar−1↦⋯↦a1↦zz\mapsto a_r\mapsto a_{r-1}\mapsto\cdots\mapsto a_1\mapsto z.

Proof. Induction on rr. For r=1r=1 both sides equal (a1 z)(a_1\ z). Let r≥1r\geq1 and assume the claim for rr; we prove it for r+1r+1 points a1,…,ar+1a_1,\ldots,a_{r+1}. By the induction hypothesis applied to a2,…,ar+1a_2,\ldots,a_{r+1},

(a1 z)(a2 z)⋯(ar+1 z)=(a1 z)γ,γ=(z ar+1 ar ⋯ a2).(1)(a_1\ z)(a_2\ z)\cdots(a_{r+1}\ z)=(a_1\ z)\gamma,\qquad\gamma=(z\ a_{r+1}\ a_r\ \cdots\ a_2). \tag*{(1)}

Apply γ\gamma first and then (a1 z)(a_1\ z). The point zz goes to ar+1a_{r+1}, which (a1 z)(a_1\ z) fixes. A point aja_j with 3≤j≤r+13 \le j \le r+1 goes to aj−1a_{j-1}, which (a1 z)(a_1\ z) fixes since j−1≥2j-1 \ge2. The point a2a_2 goes to zz and then to a1a_1. The point a1a_1 is fixed by γ\gamma and then goes to zz. So z↦ar+1↦ar↦⋯↦a2↦a1↦zz \mapsto a_{r+1} \mapsto a_r \mapsto\cdots\mapsto a_2 \mapsto a_1 \mapsto z, as claimed. □

Lemma 13 (Inserting a point into a cycle). Let k≥3k \ge3, let CC be a (k−1)(k-1)-cycle on {1,…,k−1}\{1,\ldots,k-1\} (fixing kk) and ρ=(1 k)\rho=(1\ k). Then CρC\rho is a kk-cycle, namely Cρ=(1 k C(1) C2(1) ⋯ Ck−2(1))C\rho=(1\ k\ C(1)\ C^2(1)\ \cdots\ C^{k-2}(1)). In particular (Cρ)k=id(C\rho)^k=\mathrm{id}.

Proof. Compute CρC\rho on each point (apply ρ\rho first): 1↦k↦k1 \mapsto k \mapsto k; k↦1↦C(1)k \mapsto1 \mapsto C(1); and x↦C(x)x \mapsto C(x) for x∉{1,k}x \notin\{1,k\}. Starting from 11 we get 1↦k↦C(1)1 \mapsto k \mapsto C(1); from then on, as long as the current point is neither 11 nor kk, the map simply applies CC, so we continue C(1)↦C2(1)↦⋯C(1) \mapsto C^2(1) \mapsto\cdots. Since CC is a (k−1)(k-1)-cycle, the points C(1),…,Ck−2(1)C(1),\ldots,C^{k-2}(1) are exactly the k−2k-2 elements of {2,…,k−1}\{2,\ldots,k-1\}, and C(Ck−2(1))=Ck−1(1)=1C(C^{k-2}(1))=C^{k-1}(1)=1. So the orbit of 11 contains all kk points and CρC\rho is a single kk-cycle. □

Unwinding the recursion

Lemma 14 (Unwinding). Let k≥2k \ge2, C=πk−1C=\pi_{k-1}, and τi=(sk(i) k)\tau_i=(s_k(i)\ k) for 1≤i≤k−11 \le i \le k-1. Define θ0=id\theta_0=\mathrm{id} and θm=τmCθm−1\theta_m=\tau_m C\theta_{m-1} for 1≤m≤k−11 \le m \le k-1. Then in a call HEAP⁡(k)\operatorname{HEAP}(k) started in state id\mathrm{id}:

(a) the (m+1)(m+1)-st of the kk calls to HEAP⁡(k−1)\operatorname{HEAP}(k-1) (“block mm”) starts in state θm\theta_m, its outputs occur at the states σk−1(j)θm\sigma^{(j)}_{k-1}\theta_m (1≤j≤(k−1)!)(1 \le j \le(k-1)!), and it ends in state CθmC\theta_m;

(b) θm=τmCτm−1C⋯τ1C\theta_m=\tau_m C\tau_{m-1}C\cdots\tau_1C, and

πk=Cθk−1=Cτk−1Cτk−2C⋯Cτ1C;(2)\pi_k=C\theta_{k-1}=C\tau_{k-1}C\tau_{k-2}C\cdots C\tau_1C; \tag*{(2)}

(c) during block mm the item at position kk is the one that started at position em:=θm−1(k)e_m:=\theta_m^{-1}(k).

Proof. (a) Block 0 starts in state id=θ0\mathrm{id}=\theta_0. A block that starts in state θm\theta_m ends in state CθmC\theta_m by the remark at the end of § 3; then the swap τm+1\tau_{m+1} is performed and the next block starts in τm+1Cθm=θm+1\tau_{m+1}C\theta_m=\theta_{m+1}. The statement about the output states is the same remark. (b) is immediate from the recursion; πk\pi_k is the state at the end of block k−1k-1, namely Cθk−1C\theta_{k-1}. (c) Every state in block mm has the form σθm\sigma\theta_m with σ∈Sk−1\sigma\in S_{k-1}, so σ\sigma fixes kk. The item now at position kk is the item pp with σθm(p)=k\sigma\theta_m(p)=k, i.e. θm(p)=k\theta_m(p)=k, i.e. p=θm−1(k)p=\theta_m^{-1}(k). □

Lemma 15 (Gluing). Let k≥2k \ge2 and suppose (ii) of Theorem 6 holds for k−1k-1. If e0,…,ek−1e_0,\ldots,e_{k-1} (from Lemma 14) are pairwise distinct, then (ii) holds for kk and the output of HEAP⁡(k)\operatorname{HEAP}(k) is the concatenation of the blocks of (iii).

Proof. Distinctness. By Lemma 14(a), block mm consists of the (k−1)!(k-1)! states σθm\sigma\theta_m, which are pairwise distinct because the σ=σk−1(j)\sigma=\sigma^{(j)}_{k-1} are. If ω=σθm\omega=\sigma\theta_m is in block mm then ω−1(k)=θm−1σ−1(k)=θm−1(k)=em\omega^{-1}(k)=\theta_m^{-1}\sigma^{-1}(k)=\theta_m^{-1}(k)=e_m. As the eme_m are distinct, no state lies in two blocks. So there are k⋅(k−1)!=k!k\cdot(k-1)!=k! distinct output states, i.e. all of SkS_k.

Consecutive states. Inside block mm, consecutive states σ(j)θm\sigma^{(j)}\theta_m and σ(j+1)θm\sigma^{(j+1)}\theta_m have quotient σ(j+1)(σ(j))−1\sigma^{(j+1)}(\sigma^{(j)})^{-1}, a transposition by hypothesis. Between blocks mm and m+1m+1, the last state of block $m is σk−1((k−1)!)θm=Cθm\sigma_{k-1}^{((k-1)!)}\theta_m=C\theta_m (hypothesis (ii): the last state is πk−1=C\pi_{k-1}=C), and the first state of block m+1m+1 is σk−1(1)θm+1=θm+1=τm+1(Cθm)\sigma_{k-1}^{(1)}\theta_{m+1}=\theta_{m+1}=\tau_{m+1}(C\theta_m), so the quotient is the transposition τm+1\tau_{m+1}.

Last state. The last output of HEAP(kk) is the last output of its last block, at state Cθk−1=πkC\theta_{k-1}=\pi_k by (2).

Proof of Theorem 6

We prove (i), (ii), (iii) together by induction on kk. The case k=1k=1 is trivial: HEAP(1) outputs once, at the identity, so π1=id\pi_1=\mathrm{id}, (ii) holds, and (iii) is empty. Let k≥2k\ge2 and assume the theorem for k−1k-1.

Case kk odd, k≥3k\ge3

Then k−1k-1 is even and C:=πk−1=(bk−1(1) ⋯ bk−1(k−2) k−1)C:=\pi_{k-1}=(b_{k-1}(1)\ \cdots\ b_{k-1}(k-2)\ k-1) is a (k−1)(k-1)-cycle on {1,…,k−1}\{1,\ldots,k-1\}, because bk−1b_{k-1} is a permutation of {1,…,k−2}\{1,\ldots,k-2\} (for k=3k=3 this reads C=(1 2)C=(1\ 2)). By (A1) all swaps equal ρ=(1 k)\rho=(1\ k), so τi=ρ\tau_i=\rho for all ii.

Proof of (i). By (2), πk=(Cρ)k−1C\pi_k=(C\rho)^{k-1}C. By Lemma 13, (Cρ)k=id(C\rho)^k=\mathrm{id}, hence (Cρ)k−1=(Cρ)−1=ρ−1C−1=ρC−1(C\rho)^{k-1}=(C\rho)^{-1}=\rho^{-1}C^{-1}=\rho C^{-1} and

πk=ρC−1C=ρ=(1 k).\pi_k=\rho C^{-1}C=\rho=(1\ k).

Proof of (iii). Here θm=(ρC)m\theta_m=(\rho C)^m, so θm−1=(C−1ρ)m\theta_m^{-1}=(C^{-1}\rho)^m and em=ψm(k)e_m=\psi^m(k) with ψ:=C−1ρ\psi:=C^{-1}\rho. We have ψ(k)=C−1(1)\psi(k)=C^{-1}(1), ψ(1)=k\psi(1)=k and ψ(x)=C−1(x)\psi(x)=C^{-1}(x) otherwise. We claim em=C−m(1)e_m=C^{-m}(1) for $1\le m\le k-1$. For m=1m=1 this is ψ(k)=C−1(1)\psi(k)=C^{-1}(1). If em=C−m(1)e_m=C^{-m}(1) with 1≤m≤k−21\le m\le k-2, then em∉{1,k}e_m\notin\{1,k\} (as CC has order k−1k-1 and does not fix 11, we have C−m(1)≠1C^{-m}(1)\ne1 for 1≤m≤k−2),so1\le m\le k-2), soe_{m+1}=\psi(e_m)=C^{-1}(e_m)=C^{-(m+1)}(1)$. The points C−m(1)C^{-m}(1), 1≤m≤k−11\le m\le k-1, are the k−1k-1 distinct elements of {1,…,k−1}\{1,\ldots,k-1\} (the orbit of 11 under the (k−1)(k-1)-cycle C−1C^{-1}), and e0=ke_0=k; so e0,…,ek−1e_0,\ldots,e_{k-1} are pairwise distinct.

Proof of (ii). Apply Lemma 15.

Case kk even, k≥2k\ge2

By the induction hypothesis (i), C:=πk−1C:=\pi_{k-1} equals id\mathrm{id} if k=2k=2 (since π1=id\pi_1=\mathrm{id}) and equals (1 k−1)(1\ k-1) if k≥4k\ge4 (since k−1k-1 is odd and ≥3\ge3). In both cases C=ιkC=\iota_k: CC is an involution, C−1=CC^{-1}=C, and C(k)=kC(k)=k. Write si=sk(i)s_i=s_k(i), bi=bk(i)b_i=b_k(i) and τi=(si k)\tau_i=(s_i\ k). By Lemma 11,

CτiC=C(si k)C−1=(C(si) k).(3)C\tau_iC=C(s_i\ k)C^{-1}=(C(s_i)\ k). \tag*{(3)}

Proof of (i). The word in (2) is Cτk−1Cτk−2⋯Cτ1CC\tau_{k-1}C\tau_{k-2}\cdots C\tau_1C: it has kk letters CC and k−1k-1 letters τ\tau, alternating, beginning and ending with CC. Since k−1k-1 is odd, the indices i=k−1,k−2,…,1i=k-1,k-2,\ldots,1 alternate odd, even, …\ldots, odd. Cut the word into consecutive pieces: CτiCC\tau_iC for every odd ii, and the single letter τi\tau_i for every even ii:

πk=(Cτk−1C)τk−2(Cτk−3C)τk−4⋯τ2(Cτ1C).\pi_k=(C\tau_{k-1}C)\tau_{k-2}(C\tau_{k-3}C)\tau_{k-4}\cdots\tau_2(C\tau_1C).

By (2), the piece belonging to ii is the transposition fi=(bi k)f_i=(b_i\ k) with bi=C(si)b_i=C(s_i) for odd ii and bi=sib_i=s_i for even ii; this is exactly the sequence bkb_k of (A2), a permutation of {1,…,k−1}\{1,\ldots,k-1\}. Thus

πk=(bk−1 k)(bk−2 k)⋯(b1 k).\pi_k=(b_{k-1}\ k)(b_{k-2}\ k)\cdots(b_1\ k).

Apply Lemma 12 with r=k−1r=k-1, z=kz=k and aj=bk−ja_j=b_{k-j} (so ar=b1a_r=b_1, ar−1=b2,…,a1=bk−1a_{r-1}=b_2,\ldots,a_1=b_{k-1}): the product equals (k b1 b2⋯bk−1)=(b1⋯bk−1 k)(k\ b_1\ b_2\cdots b_{k-1})=(b_1\cdots b_{k-1}\ k), as claimed. Proof of (iii). Since all letters are involutions, θm−1=Cτ1Cτ2⋯Cτm\theta_m^{-1}=C_{\tau_1}C_{\tau_2}\cdots C_{\tau_m} by Lemma 14(b) (reverse the order of the factors and invert each). Cut this word as before into f1=Cτ1Cf_1=C_{\tau_1}C, f2=τ2f_2=\tau_2, f3=Cτ3C,…f_3=C_{\tau_3}C,\ldots: if mm is even we get θm−1=f1f2⋯fm−1gm\theta_m^{-1}=f_1f_2\cdots f_{m-1}g_m with gm=τmg_m=\tau_m; if mm is odd we get θm−1=f1⋯fm−1gm\theta_m^{-1}=f_1\cdots f_{m-1}g_m with a last piece gm=Cτmg_m=C\tau_m (there is no closing CC). Here fj=(bj k)f_j=(b_j\ k) as in (2). Now gm(k)=sm=bmg_m(k)=s_m=b_m if mm is even and gm(k)=C(sm)=bmg_m(k)=C(s_m)=b_m if mm is odd. Each fjf_j with j<mj<m moves only bjb_j and kk, and bm∉{b1,…,bm−1,k}b_m\notin\{b_1,\ldots,b_{m-1},k\} by (A2), so f1⋯fm−1f_1\cdots f_{m-1} fixes bmb_m. Hence em=θm−1(k)=bme_m=\theta_m^{-1}(k)=b_m for 1≤m≤k−11\le m\le k-1, and e0=ke_0=k. These are pairwise distinct.

Proof of (ii). Apply Lemma 15. □\square

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 k≥4k\ge4: bk=(k−1,2,3,…,k−2,1)b_k=(k-1,2,3,\ldots,k-2,1), so πk=(k−1 2 3 ⋯ k−2 1 k)\pi_k=(k-1\ 2\ 3\ \cdots\ k-2\ 1\ k), which after rotating to start at 1 is (1 k k−1 2 3 ⋯ k−2)(1\ k\ k-1\ 2\ 3\ \cdots\ k-2). Cyclic: bk=(1,2,…,k−1)b_k=(1,2,\ldots,k-1), so πk=(1 2 ⋯ k)\pi_k=(1\ 2\ \cdots\ k). This permutation sends position pp to p+1p+1 for p<kp<k and kk to 1; the item at position pp moves to p+1p+1 and the item at position kk moves to position 1, which is the rotation claimed. For k=2k=2 both give (1 2)(1\ 2). □\square

Proof of Corollary 9: By Theorem 6(i), πk=(bk(1) ⋯ bk(k−1) k)\pi_k=(b_k(1)\ \cdots\ b_k(k-1)\ k). A kk-cycle of SkS_k can be written in exactly one way as a sequence that ends with kk (read the cycle cyclically starting just after kk), so the (k−1)!(k-1)! permutations bkb_k correspond bijectively to the (k−1)!(k-1)! kk-cycles. The map bk↦skb_k\mapsto s_k given by sk(i)=ιk(bk(i))s_k(i)=\iota_k(b_k(i)) for odd ii and sk(i)=bk(i)s_k(i)=b_k(i) for even ii is a bijection (as ιk\iota_k is an involution) onto the admissible choices of sks_k. □\square

Proof of Proposition 10: The last state is a product of k!−1k!-1 transpositions, one for each of the k!−1k!-1 swaps (consecutive outputs differ by one swap and the last output occurs after the last swap). Each transposition has sign −1-1 and sgn⁡\operatorname{sgn} is multiplicative, so the sign is (−1)k!−1=−1(-1)^{k!-1}=-1 because k!k! is even for k≥2k\ge2. A kk-cycle has sign (−1)k−1(-1)^{k-1}, which is +1+1 for odd kk. □\square

Remark 16 The proof shows where the odd/even dichotomy comes from. For odd kk the same swap (1 k)(1\ k) is used in every round and the argument collapses to a power of a single kk-cycle CρC_\rho: a kk-cycle has order kk, so the k−1k-1 swaps telescope to πk=(1 k)\pi_k=(1\ k). For even kk the inner net permutation is an involution, and conjugating by it turns the k−1k-1 rounds into a product of star transpositions, which Lemma 12 evaluates as a single kk-cycle. The choice of the schedule affects only the order of the points bk(1),…,bk(k−1)b_k(1),\ldots,b_k(k-1) 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 k≥2k\ge2 and a permutation C∈Sk−1⊆SkC\in S_{k-1}\subseteq S_k (so C(k)=kC(k)=k); in applications C=πk−1C=\pi_{k-1}, but nothing below uses this. Let s=(s(1),…,s(k−1))s=(s(1),\ldots,s(k-1)) be a schedule for level kk (each s(i)∈{1,…,k−1}s(i)\in\{1,\ldots,k-1\}), τi=(s(i) k)\tau_i=(s(i)\ k), and define as in Lemma 14

θ0=id⁡,θm=τmCθm−1 (1≤m≤k−1),\theta_0=\operatorname{id},\qquad\theta_m=\tau_m C\theta_{m-1}\ (1\le m\le k-1),
em=θm−1(k) (0≤m≤k−1),π(C,s)=Cθk−1.e_m=\theta_m^{-1}(k)\ (0\le m\le k-1),\qquad\pi(C,s)=C\theta_{k-1}.

Thus e0=ke_0=k and eme_m is the item (identified by its starting position) parked at position kk during block mm. We call ss valid for CC if e0,…,ek−1e_0,\ldots,e_{k-1} are pairwise distinct. By the proof of Lemma 15 this is exactly the condition that the kk blocks lie in different right cosets of Sk−1S_{k-1}; if C=πk−1C=\pi_{k-1} and the schedules below level kk are valid, then ss is valid for CC if and only if HEAP(k)(k) outputs every permutation of SkS_k exactly once. (If two parked items coincide, θmθm′−1\theta_m\theta_{m'}^{-1} fixes kk and two blocks lie in the same coset, so outputs repeat.)

Lemma 17 (Path product). For pairwise distinct points e0,…,eme_0,\ldots,e_m:

(e0 e1)(e1 e2)⋯(em−1 em)=(e0 e1⋯em).(e_0\ e_1)(e_1\ e_2)\cdots(e_{m-1}\ e_m)=(e_0\ e_1\cdots e_m).

Proof. Induction on mm; m=1m=1 is trivial. Write the product for mm as P(em−1 em)P(e_{m-1}\ e_m) with P=(e0⋯em−1)P=(e_0\cdots e_{m-1}) by hypothesis, and apply (em−1 em)(e_{m-1}\ e_m) first. Then em↦em−1↦e0e_m\mapsto e_{m-1}\mapsto e_0; em−1↦em↦eme_{m-1}\mapsto e_m\mapsto e_m (PP fixes eme_m); and ei↦ei↦ei+1e_i\mapsto e_i\mapsto e_{i+1} for i<m−1i<m-1. So e0↦e1↦⋯↦em↦e0e_0\mapsto e_1\mapsto\cdots\mapsto e_m\mapsto e_0. □\square

Theorem 18 (General net formula). Let k≥2k\ge2, C∈Sk−1C\in S_{k-1} and let ss be any schedule for level kk.

(a) s(m)=C(θm−1(em))s(m)=C(\theta_{m-1}(e_m)) for all mm, and θm=Cm(e0 e1)(e1 e2)⋯(em−1 em)\theta_m=C^m(e_0\ e_1)(e_1\ e_2)\cdots(e_{m-1}\ e_m).

(b) If ss is valid for CC, then θm=Cm(k e1⋯em)\theta_m=C^m(k\ e_1\cdots e_m) and

π(C,s)=Ck(k e1 e2⋯ek−1).\pi(C,s)=C^k(k\ e_1\ e_2\cdots e_{k-1}).

(c) The map s↦(e1,…,ek−1)s\mapsto(e_1,\ldots,e_{k-1}) is a bijection from the schedules valid for CC onto the orderings of {1,…,k−1}\{1,\ldots,k-1\}. In particular there are exactly (k−1)!(k-1)! valid schedules.

(d) Consequently the possible net permutations of level kk are exactly the elements CkZC^kZ with ZZ a kk-cycle of SkS_k, and a target T∈SkT\in S_k is the net permutation of some valid schedule if and only if C−kTC^{-k}T is a kk-cycle.

Proof. (a) Since θm−1=θm−1−1C−1τm\theta_m^{-1}=\theta_{m-1}^{-1}C^{-1}\tau_m and τm(k)=s(m)\tau_m(k)=s(m), we get em=θm−1−1(C−1(s(m)))e_m=\theta_{m-1}^{-1}(C^{-1}(s(m))), i.e. s(m)=C(u)s(m)=C(u) with u:=θm−1(em)u:=\theta_{m-1}(e_m). Because C(k)=kC(k)=k and s(m)≠ks(m)\ne k we have u≠ku\ne k, hence em≠em−1e_m\ne e_{m-1} (recall θm−1(em−1)=k\theta_{m-1}(e_{m-1})=k). By Lemma 11, τm=(C(u) k)=C(u k)C−1\tau_m=(C(u)\ k)=C(u\ k)C^{-1}, so

θm=τmCθm−1=C(u k)θm−1.\theta_m=\tau_mC\theta_{m-1}=C(u\ k)\theta_{m-1}.

Again by Lemma 11, and since θm−1(em)=u\theta_{m-1}(e_m)=u and θm−1(em−1)=k\theta_{m-1}(e_{m-1})=k, we have (u k)=θm−1(em−1 em)θm−1−1(u\ k)=\theta_{m-1}(e_{m-1}\ e_m)\theta_{m-1}^{-1}, so (u k)θm−1=θm−1(em−1 em)(u\ k)\theta_{m-1}=\theta_{m-1}(e_{m-1}\ e_m) and θm=Cθm−1(em−1 em)\theta_m=C\theta_{m-1}(e_{m-1}\ e_m). Induction from θ0=id⁡\theta_0=\operatorname{id} gives the stated product.

(b) If e0,…,ek−1e_0,\ldots,e_{k-1} are distinct, Lemma 17 turns the product into the cycle (e0⋯em)=(k e1⋯em)(e_0\cdots e_m)=(k\ e_1\cdots e_m), and π(C,s)=Cθk−1=Ck(k e1⋯ek−1)\pi(C,s)=C\theta_{k-1}=C^k(k\ e_1\cdots e_{k-1}).

(c) Injectivity: by (a), s(m)s(m) is determined by eme_m and θm−1\theta_{m-1}, which in turn is determined by e1,…,em−1e_1,\ldots,e_{m-1}. Surjectivity: given an ordering (e1,…,ek−1)(e_1,\ldots,e_{k-1}) of {1,…,k−1}\{1,\ldots,k-1\}, define s(m)s(m) C(θm−1(em))C(\theta_{m-1}(e_m)) and θm\theta_m recursively. Suppose the parked items of the first m−1m-1 blocks are the prescribed ones; then θm−1(em)≠k\theta_{m-1}(e_m) \ne k, because θm−1(em−1)=k\theta_{m-1}(e_{m-1})=k and em≠em−1e_m \ne e_{m-1}, so s(m)=C(θm−1(em))∈{1,…,k−1}s(m)=C(\theta_{m-1}(e_m)) \in\{1,\ldots,k-1\} (as CC fixes kk and permutes {1,…,k−1}\{1,\ldots,k-1\}), and by the computation in (a) the item parked in block mm is eme_m. Hence the schedule exists, and its parked items are the prescribed, pairwise distinct ones.

(d) By (b) and (c), the nets are CkZC^kZ with Z=(k e1⋯ek−1)Z=(k\ e_1\cdots e_{k-1}), and as (e1,…,ek−1)(e_1,\ldots,e_{k-1}) runs over all orderings, ZZ runs over all kk-cycles of SkS_k (a kk-cycle has a unique cyclic representation starting at kk). So T=CkZT=C^kZ for a kk-cycle ZZ if and only if C−kTC^{-k}T is a kk-cycle. □

Corollary 19 (Counting). There are exactly 1!⋅2!⋯(n−1)!1!\cdot2!\cdots(n-1)! valid Heap-type schedule families for nn items, i.e. choices of one valid schedule at each level 2,…,n2,\ldots,n.

Proof. By Theorem 18(c) there are (k−1)!(k-1)! valid schedules at level kk for each possible lower net CC, independently of CC; multiply over k=2,…,nk=2,\ldots,n. □

The cyclic variant in terms of parking orders

Corollary 20 (Parking orders of the classic and the cyclic variant). (i) For even kk, C=πk−1C=\pi_{k-1} is an involution fixing kk, so Ck=id⁡C^k=\operatorname{id} and πk=(k e1⋯ek−1)\pi_k=(k\ e_1\cdots e_{k-1}). The classic variant parks e=(k−1,2,3,…,k−2,1)e=(k-1,2,3,\ldots,k-2,1), the cyclic variant parks e=(1,2,…,k−1)e=(1,2,\ldots,k-1) (increasing order).

(ii) For odd k≥3k\ge3, the classic schedule s≡1s\equiv1 parks em=C−m(1)e_m=C^{-m}(1) (proof of Theorem 6(iii)). If the levels below are cyclic, C=(1 2⋯k−1)C=(1\ 2\cdots k-1) and so e=(k−1,k−2,…,1)e=(k-1,k-2,\ldots,1) (decreasing order), and indeed πk=C (k e1⋯ek−1)=(1 k)\pi_k=C\,(k\ e_1\cdots e_{k-1})=(1\ k).

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 em=bk(m)e_m=b_k(m), Lemma 4). (ii) The first claim is in the proof of Theorem 6; C−m(1)=k−mC^{-m}(1)=k-m for C=(1 2⋯k−1)C=(1\ 2\cdots k-1) and 1≤m≤k−11\le m\le k-1. For the product, let Z=(k k−1 k−2⋯1)Z=(k\ k-1\ k-2\cdots1), i.e. Z(k)=k−1Z(k)=k-1, Z(x)=x−1Z(x)=x-1 for 2≤x≤k−12\le x\le k-1, and Z(1)=kZ(1)=k. Since CC has order k−1k-1, Theorem 18(b) gives πk=CkZ=CZ\pi_k=C^kZ=CZ. Now CZ(k)=C(k−1)=1CZ(k)=C(k-1)=1, CZ(1)=C(k)=kCZ(1)=C(k)=k, and for 2≤x≤k−12\le x\le k-1, CZ(x)=C(x−1)=xCZ(x)=C(x-1)=x. So CZ=(1 k)CZ=(1\ k). □

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 [1 2⋯n][1\ 2\cdots n], 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 nn.

Which final arrangements are possible

Recall (Lemma 1) that if the state at the end is ω\omega then the final array is [ω−1][\omega^{-1}], a permutation of the same sign as ω\omega.

Proposition 21 (Lexicographically largest attainable arrangement). Let n≥2n \ge2. For every procedure that lists all arrangements of an nn-array, starting from [1 2 ⋯ n][1\ 2\ \cdots\ n], with consecutive arrangements differing by one swap, the final array is an odd permutation. The lexicographically largest odd permutation is

an∗={[n n−1 ⋯ 2 1] (the reversal)n≡2,3(mod4),[n n−1 ⋯ 3 1 2]n≡0,1(mod4).a_n^* = \begin{cases} [n\ n-1\ \cdots\ 2\ 1]\ \text{(the reversal)} & n \equiv2,3 \pmod{4},\\ [n\ n-1\ \cdots\ 3\ 1\ 2] & n \equiv0,1 \pmod{4}. \end{cases}

Proof. By Proposition 10 the final state is odd, hence so is the final array. The reversal is a product of ⌊n/2⌋\lfloor n/2 \rfloor disjoint transpositions (i n+1−i)(i\ n+1-i), so it is odd if and only if ⌊n/2⌋\lfloor n/2 \rfloor is odd, i.e. n≡2,3(mod4)n \equiv2,3 \pmod{4}; 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. [n ⋯ 3 1 2][n\ \cdots\ 3\ 1\ 2], which has the opposite sign and is therefore odd, hence is the largest odd permutation. □

Thus for even nn the true reversal can be the final arrangement only when n≡2(mod4)n \equiv2 \pmod{4}; for n≡0(mod4)n \equiv0 \pmod{4} (e.g. n=4,8,12n=4,8,12) the best possible is [n ⋯ 3 1 2][n\ \cdots\ 3\ 1\ 2]. By Theorem 6 no admissible schedule can reach the reversal for n≥4n \ge4, since the nets of admissible schedules are nn-cycles while the reversal is a product of ⌊n/2⌋≥2\lfloor n/2 \rfloor\ge2 disjoint transpositions; the construction below therefore uses a level that is not admissible. For even nn write Tn=(an∗)−1T_n=(a_n^*)^{-1} for the target state: TnT_n is the reversal v↦n+1−vv \mapsto n+1-v if n≡2(mod4)n \equiv2 \pmod{4} and

Tn:1↦n−1,2↦n,v↦n+1−v (3≤v≤n)if n≡0(mod4).T_n:\quad1 \mapsto n-1,\quad2 \mapsto n,\quad v \mapsto n+1-v\ (3 \le v \le n) \qquad\text{if }n \equiv0\pmod{4}.

The construction

**Definition 22 (Extremal variant, even n≥4).∗∗Levels$2,…,n−2n \ge4).** Levels \$2,\ldots,n-2 use the cyclic schedule. Level n−1n-1 (odd) parks the items 1,…,n−21,\ldots,n-2 in the order

En={(1,2,…,n−2)n≡0(mod4),(1,…,m,n−2,n−3,…,m+1),m=n−22n≡2(mod4).E_n= \begin{cases} (1,2,\ldots,n-2) & n \equiv0 \pmod{4},\\ (1,\ldots,m,n-2,n-3,\ldots,m+1),\quad m=\frac{n-2}{2} & n \equiv2 \pmod{4}. \end{cases}

Level nn parks the items in the order e1,…,en−1e_1,\ldots,e_{n-1} given by the nn-cycle

Zn=(n e1 ⋯ en−1):=πn−1−nTn,Z_n=(n\ e_1\ \cdots\ e_{n-1}) := \pi_{n-1}^{-n}T_n,

provided this permutation is an nn-cycle. For n=2n=2 the variant is the cyclic (= classic) one. The schedules sn−1s_{n-1} and sns_n are obtained from these orders by Theorem 18(a): s(m)=C(θm−1(em))s(m)=C(\theta_{m-1}(e_m)).

Thus the extremal variant coincides with the cyclic variant except at the two topmost levels, and level nn is defined by one explicit product of permutations; there is no need to search.

Theorem 23 (Extremal variant). Let n≥2n \ge2 be even.

(a) If ZnZ_n is an nn-cycle, then the extremal variant lists all n!n! permutations with one swap between consecutive arrangements and its final array, started from [1 2 ⋯ n][1\ 2\ \cdots\ n], is an∗a_n^*: the lexicographically largest arrangement that any single-swap enumeration can leave (Proposition 21).

(b) ZnZ_n is an nn-cycle whenever n≡0(mod4)n \equiv0 \pmod{4}.

(c) ZnZ_n is an nn-cycle for every even nn with 6≤n≤100006 \le n \le10000 (verified by computer, including n≡2(mod4)n \equiv2 \pmod{4}).

Proof of (a): By Corollary 8 and Theorem 6, levels 2,…,n−22,\ldots,n-2 are valid and πn−2=A:=(1 2 ⋯ n−2)\pi_{n-2}=A:=(1\ 2\ \cdots\ n-2). By Theorem 18(c) every parking order at level n−1n-1 is valid for C=AC=A, so by Lemma 15 levels up to n−1n-1 are valid. If ZnZ_n is an nn-cycle, Theorem 18(d) gives a valid schedule at level nn with net πn−1nZn=Tn\pi_{n-1}^{n}Z_n=T_n, and Lemma 15 shows that Heap(n)(n) enumerates SnS_n with one swap between consecutive arrangements. The final state is TnT_n and by Lemma 1 the final array is Tn−1=an∗T_n^{-1}=a_n^*. □\square

Lemma 24 (Net of level n−1n-1 for n≡0n\equiv0 (mod 4)). Let n≥4n\ge4, n≡0n\equiv0 (mod 4), and let levels ≤n−2\le n-2 be cyclic and level n−1n-1 use the order En=(1,…,n−2)E_n=(1,\ldots,n-2). Then

U:=πn−1=(1 3 5 ⋯ n−3)(2 4 ⋯ n−2 n−1).U:=\pi_{n-1}=(1\ 3\ 5\ \cdots\ n-3)(2\ 4\ \cdots\ n-2\ n-1).

Proof: With k=n−1k=n-1, C=A=(1 2 ⋯ n−2)C=A=(1\ 2\ \cdots\ n-2) (of order n−2n-2) and Z′=(n−1 1 2 ⋯ n−2)Z'=(n-1\ 1\ 2\ \cdots\ n-2), Theorem 18(b) gives U=An−1Z′=AZ′U=A^{n-1}Z'=AZ'. Now Z′(x)=x+1Z'(x)=x+1 for x≤n−2x\le n-2 and Z′(n−1)=1Z'(n-1)=1, and A(y)=y+1A(y)=y+1 for y≤n−3y\le n-3, A(n−2)=1A(n-2)=1, A(n−1)=n−1A(n-1)=n-1. Hence U(x)=x+2U(x)=x+2 for 1≤x≤n−41\le x\le n-4; U(n−3)=A(n−2)=1U(n-3)=A(n-2)=1; U(n−2)=A(n−1)=n−1U(n-2)=A(n-1)=n-1; U(n−1)=A(1)=2U(n-1)=A(1)=2. The odd points 1,3,…,n−31,3,\ldots,n-3 form one cycle, and 2,4,…,n−2,n−12,4,\ldots,n-2,n-1 another. □\square

Proof of (b): For n=4n=4 we have U=(2 3)U=(2\ 3) and U4=id⁡U^4=\operatorname{id}, so Z4=T4=(1 3 2 4)Z_4=T_4=(1\ 3\ 2\ 4) is a 4-cycle. Let n≥8n\ge8. Write V=(1 3 ⋯ n−3)V=(1\ 3\ \cdots\ n-3), of length L=n−22L=\frac{n-2}{2}, and W=(2 4 ⋯ n−2 n−1)W=(2\ 4\ \cdots\ n-2\ n-1), of length n2\frac{n}{2}. Since n=2⋅n−22+2=2L+2n=2\cdot\frac{n-2}{2}+2=2L+2, Wn=id⁡W^n=\operatorname{id} and Vn=V2V^n=V^2, so Zn=U−nTn=V−2TnZ_n=U^{-n}T_n=V^{-2}T_n. The permutation V−2V^{-2} moves only odd points: y↦y−4y\mapsto y-4 for odd y≥5y\ge5, 3↦n−33\mapsto n-3, 1↦n−51\mapsto n-5. With the explicit TnT_n above, Z:=ZnZ:=Z_n is therefore given by

Z(1)=n−1,Z(n−1)=2,Z(2)=n,Z(n)=n−5,Z(x)=n+1−xfor odd x, 3≤x≤n−3,Z(x)=n−3−xfor even x, 4≤x≤n−4,Z(n−2)=n−3.\begin{aligned} Z(1)&=n-1,\quad Z(n-1)=2,\quad Z(2)=n,\quad Z(n)=n-5,\\ Z(x)&=n+1-x\quad\text{for odd }x,\ 3\le x\le n-3,\\ Z(x)&=n-3-x\quad\text{for even }x,\ 4\le x\le n-4,\quad Z(n-2)=n-3. \end{aligned}

(For odd xx in the range, Tn(x)=n+1−xT_n(x)=n+1-x is even and fixed by V−2V^{-2}; for even x≤n−4x\le n-4, Tn(x)T_n(x) is odd ≥5\ge5 and V−2V^{-2} subtracts 4; for x=n−2x=n-2, Tn(x)=3T_n(x)=3.) Put J=n−44J=\frac{n-4}{4} and, for suitable jj,

aj=n−1−4j,bj=4j+2(1≤j≤J);cj=n−3−4j,dj=4j+4(0≤j≤J−1).a_j=n-1-4j,\quad b_j=4j+2\quad(1\le j\le J);\qquad c_j=n-3-4j,\quad d_j=4j+4\quad(0\le j\le J-1).

Then Z(n)=a1Z(n)=a_1; Z(aj)=bjZ(a_j)=b_j for 1≤j≤J1\le j\le J (as 3≤aj≤n−33\le a_j\le n-3); Z(bj)=aj+1Z(b_j)=a_{j+1} for j≤J−1j\le J-1 (as 4≤bj≤n−44\le b_j\le n-4); Z(bJ)=Z(n−2)=n−3=c0Z(b_J)=Z(n-2)=n-3=c_0; Z(cj)=djZ(c_j)=d_j for 0≤j≤J−10\le j\le J-1 (as 5≤cj≤n−35\le c_j\le n-3); Z(dj)=cj+1Z(d_j)=c_{j+1} for j≤J−2j\le J-2; and Z(dJ−1)=Z(n−4)=1Z(d_{J-1})=Z(n-4)=1. Hence the orbit of 1 is

1→n−1→2→n→a1→b1→⋯→aJ→bJ→c0→d0→⋯→cJ−1→dJ−1→1.1\to n-1\to2\to n\to a_1\to b_1\to\cdots\to a_J\to b_J\to c_0\to d_0\to\cdots\to c_{J-1}\to d_{J-1}\to1.

It consists of 4+4J=n4+4J=n points, and they are pairwise distinct: modulo 4 the points 1,c0,…,cJ−11,c_0,\ldots,c_{J-1} are ≡1\equiv1 (the values 1,5,9,…,n−31,5,9,\ldots,n-3), the points n−1,a1,…,aJn-1,a_1,\ldots,a_J are ≡3\equiv3 (the values 3,7,…,n−13,7,\ldots,n-1), the points 2,b1,…,bJ2,b_1,\ldots,b_J are ≡2\equiv2 (the values 2,6,…,n−22,6,\ldots,n-2) and the points n,d0,…,dJ−1n,d_0,\ldots,d_{J-1} are ≡0\equiv0 (the values 4,8,…,n4,8,\ldots,n). So the orbit is all of {1,…,n}\{1,\ldots,n\} and ZnZ_n is an nn-cycle. □\square

The case n≡2(mod4)n \equiv2 \pmod{4}. Here the same reduction applies with a different explicit UU: for m=n−22m = \frac{n-2}{2} one finds (and we have verified by computer for n=6,10,…,2000n = 6, 10, \ldots, 2000) that

πn−1=(1 3 ⋯ m−1 m+1 n−1 2 4 ⋯ m)\pi_{n-1}=(1\ 3\ \cdots\ m-1\ m+1\ n-1\ 2\ 4\ \cdots\ m)

with all other points fixed, a cycle of length n+22\frac{n+2}{2}, so that Zn=U−nTn=U2TnZ_n=U^{-n}T_n=U^2T_n is again an explicit permutation (as n≡−2n\equiv-2 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 nn. Part (c) was verified by computing ZnZ_n and checking that the cycle through nn has length nn, for all even nn from 6 to 10000; exhaustive runs confirm the end-to-end behaviour for n≤10n\leq10, and the final array for n=12n=12 (§ 9).

Examples and remarks

Table 4 lists the schedules of the two top levels for n=4,6,8,10n=4,6,8,10 and the resulting nets; the corresponding runs enumerate all n!n! permutations and end in the final arrays shown (checked exhaustively; for n=10n=10 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 n−1n-1 and nn that would give a kk-cycle for every kk; for 6≤n≤166\leq n\leq16 there is none, and the order at level nn 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 n−1n-1 has an explicit order, and level nn is defined by one product of permutations, computable in O(n2)O(n^2) time.

  1. Per-level optimality fails. The tempting rule “every level ends in its own lexicographically largest attainable arrangement” is not realisable: the required cycle πk−1−kTk\pi_{k-1}^{-k}T_k fails to be a kk-cycle for every even kk from 8 to 40 (while it succeeds for all odd k≤39k\leq39 and for k≤7k\leq7). The levels below the top must therefore be chosen to make the top level work, as in Definition 22.

  1. Odd nn. For odd nn the same construction (cyclic below) succeeds only for n=3,5n=3,5 and fails for $7\leq n\leq 31; we do not provide the variant for odd nn. Whether other choices at lower levels make the largest attainable arrangement reachable for odd nn is not investigated here.

Worked examples for n=4n = 4

Table 5 lists the 24 arrays produced for n=4n = 4 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 (1 4),(2 4),(3 4)(1\ 4), (2\ 4), (3\ 4) for the classic schedule (s4=(1,2,3)s_4 = (1,2,3) with ι4=(1 3)\iota_4 = (1\ 3) giving b4=(3,2,1)b_4 = (3,2,1)) and (3 4),(2 4),(1 4)(3\ 4), (2\ 4), (1\ 4) for the cyclic one (s4=(3,2,1)s_4 = (3,2,1), b4=(1,2,3)b_4 = (1,2,3)). The item parked at position 4 is the last entry of each array in a block; it is em=4,3,2,1e_m = 4,3,2,1 for the classic variant and em=4,1,2,3e_m = 4,1,2,3 for the cyclic one, as predicted by em=b4(m)e_m = b_4(m). The final arrays [2 3 4 1][2\ 3\ 4\ 1] and [4 1 2 3][4\ 1\ 2\ 3] are the entries for k=4k = 4 in Table 3.

kkclassic net πk\pi_kfinal arraycyclic net πk\pi_kfinal array
2(1 2)(1\ 2)[2 1][2\ 1]samesame
3(1 3)(1\ 3)[3 2 1][3\ 2\ 1]samesame
4(1 4 3 2)(1\ 4\ 3\ 2)[2 3 4 1][2\ 3\ 4\ 1](1 2 3 4)(1\ 2\ 3\ 4)[4 1 2 3][4\ 1\ 2\ 3]
5(1 5)(1\ 5)[5 2 3 4 1][5\ 2\ 3\ 4\ 1]samesame
6(1 6 5 2 3 4)(1\ 6\ 5\ 2\ 3\ 4)[4 5 2 3 6 1][4\ 5\ 2\ 3\ 6\ 1](1 2 3 4 5 6)(1\ 2\ 3\ 4\ 5\ 6)[6 1 2 3 4 5][6\ 1\ 2\ 3\ 4\ 5]
7(1 7)(1\ 7)[7 2 3 4 5 6 1][7\ 2\ 3\ 4\ 5\ 6\ 1]samesame
8(1 8 7 2 3 4 5 6)(1\ 8\ 7\ 2\ 3\ 4\ 5\ 6)[6 7 2 3 4 5 8 1][6\ 7\ 2\ 3\ 4\ 5\ 8\ 1](1 2 ⋯ 8)(1\ 2\ \cdots\ 8)[8 1 2 3 4 5 6 7][8\ 1\ 2\ 3\ 4\ 5\ 6\ 7]

Table 3. Net permutations (Corollaries 7 and 8) and the array obtained when a complete call HEAP(k)(k) is run on [1 2 ⋯ k][1\ 2\ \cdots\ k]. By Lemma 1 the final array is the one-line notation of πk−1\pi_k^{-1}. These entries were also confirmed by running the algorithm.

blockclassic variant (swap before block)cyclic variant (swap before block)
0— 1234 2134 3124 1324 2314 3214— 1234 2134 3124 1324 2314 3214
1(1 4)(1\ 4) 4213 2413 1423 4123 2143 1243(3 4)(3\ 4) 3241 2341 4321 3421 2431 4231
2(2 4)(2\ 4) 1342 3142 4132 1432 3412 4312(2 4)(2\ 4) 4132 1432 3412 4312 1342 3142
3(3 4)(3\ 4) 4321 3421 2431 4231 3241 2341(1 4)(1\ 4) 2143 1243 4213 2413 1423 4123

Table 5. All 24 arrays for n=4n = 4 (digits written without brackets).

Computational verification

All results of this paper are proved except part (c) of Theorem 23, the formula for πn−1\pi_{n-1} stated for n≡2n \equiv2 (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 nn. 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(nn) directly on states, performing for each swap (i j)(i\ j) the left product ω↦(i j)ω\omega\mapsto(i\ j)\omega of § 2.8, and checks the following.

  1. For the classic and the cyclic variant and k≤7k \le7, all k!k! 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.

  1. For the extremal variant and n=2,4,6,8n = 2, 4, 6, 8, with the schedules obtained from the parking orders of Definition 22 by Theorem 18(a), the same properties hold and the last state is TnT_n. The schedules, parking orders and net permutations of Table 4 are reproduced.

nnlevel n−1n-1: order EnE_n and schedule sn−1s_{n-1}level nn: order (e1,…,en−1)(e_1,\ldots,e_{n-1}) and schedule sns_nnet πn\pi_n (canonical)final array
4(1,2)(1,2); (2,2)(2,2)(1,3,2)(1,3,2); (1,3,3)(1,3,3)(1 3 2 4)(1\ 3\ 2\ 4)[4 3 1 2][4\ 3\ 1\ 2]
6(1,2,4,3)(1,2,4,3); (2,4,3,3)(2,4,3,3)(5,3,4,2,1)(5,3,4,2,1); (2,2,4,2,3)(2,2,4,2,3)(1 6)(2 5)(3 4)(1\ 6)(2\ 5)(3\ 4)[6 5 4 3 2 1][6\ 5\ 4\ 3\ 2\ 1]
8(1,…,6)(1,\ldots,6); (2,4,6,2,4,6)(2,4,6,2,4,6)(3,6,5,4,1,7,2)(3,6,5,4,1,7,2); (5,2,5,4,5,4,7)(5,2,5,4,5,4,7)(1 7 2 8)(3 6)(4 5)(1\ 7\ 2\ 8)(3\ 6)(4\ 5)[8 7 6 5 4 3 1 2][8\ 7\ 6\ 5\ 4\ 3\ 1\ 2]
10(1,2,3,4,8,7,6,5)(1,2,3,4,8,7,6,5); (2,4,6,8,5,5,5,5)(2,4,6,8,5,5,5,5)(5,6,2,4,7,3,8,9,1)(5,6,2,4,7,3,8,9,1); (9,6,3,9,7,3,8,4,9)(9,6,3,9,7,3,8,4,9)(1 10)(2 9)(3 8)(4 7)(5 6)(1\ 10)(2\ 9)(3\ 8)(4\ 7)(5\ 6)[10 9 ⋯ 2 1][10\ 9\ \cdots\ 2\ 1]

Table 4. Schedules of the two topmost levels of the extremal variant (positions s(i)s(i) swapped with the last position in rounds i=1,2,…i=1,2,\ldots; levels 2,…,n−22,\ldots,n-2 are cyclic). For n=12n=12 the final array is [12 11 ⋯ 3 1 2][12\ 11\ \cdots\ 3\ 1\ 2], with net (1 11 2 12)(3 10)(4 9)(5 8)(6 7)(1\ 11\ 2\ 12)(3\ 10)(4\ 9)(5\ 8)(6\ 7).

  1. For n≤4n \le4, a search over all 1⋅22⋅33=1081 \cdot2^2 \cdot3^3 = 108 schedule families finds exactly the 1!2!3!=121!2!3! = 12 valid ones of Corollary 19.

  1. For every even nn with 6≤n≤100006 \le n \le10000, the permutation ZnZ_n of Definition 22 is an nn-cycle (Theorem 23(c)); for n≡0n \equiv0 (mod 4) in this range, πn−1\pi_{n-1} agrees with Lemma 24; and for n≡2n \equiv2 (mod 4) with n≤2000n \le2000, πn−1\pi_{n-1} agrees with the formula of § 7. Here πn−1\pi_{n-1} is computed by Theorem 18(b) and the power πn−1−n\pi_{n-1}^{-n} by repeated squaring, so that each nn costs O(nlog⁡n)O(n\log n) operations.

  1. The statements on per-level optimality and on odd nn 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 n≤10n \le10, that all n!n! 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 n=11n = 11 and n=12n = 12 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 Sk−1S_{k-1} in SkS_k with consecutive arrangements related by one transposition, and proved a general net formula πk=πk−1k(k e1 ⋯ ek−1)\pi_k = \pi_{k-1}^{k}(k\ e_1\ \cdots\ e_{k-1}) in which the parking order ee may be chosen freely. The formula explains the odd/even dichotomy of the classic algorithm, yields the cyclic variant (net permutation (1 2 ⋯ k)(1\ 2\ \cdots\ k) for even kk) and a variant for even nn whose final arrangement is the lexicographically largest attainable one, which a parity argument identifies as the reversal exactly when n≡2(mod4)n \equiv2 \pmod{4}. The statements that are not proved were verified by computer.

Limitations and open questions.

  1. The correctness of the extremal variant is proved for n≡0(mod4)n \equiv0 \pmod{4} and verified by computer for all even n≤10000n \le10000; a proof for n≡2(mod4)n \equiv2 \pmod{4} (the orbit structure of Zn\mathbb{Z}_n) is open.

  1. We found no closed formula for the parking order at the top level and no variant for odd n≥7n \ge7 with the cyclic variant below it; whether other lower levels make the largest attainable arrangement reachable for odd nn is open.

  1. A complete description of all schedules, beyond the (k−1)!(k-1)! 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. [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. [2]Edsger W. Dijkstra. A Discipline of Programming. Prentice-Hall, 1976.
  3. [3]Gideon Ehrlich. Loopless algorithms for generating permutations, combinations, and other combinatorial configurations. Journal of the ACM, 20(3):500–513, 1973.DOI
  4. [4]Dominique Foata. On the Netto inversion number of a sequence. Proceedings of the American Mathematical Society, 19:236–240, 1968.DOI
  5. [5]B. R. Heap. Permutations by interchanges. The Computer Journal, 6(3):293–294, 1963.DOI
  6. [6]ISO/IEC. ISO/IEC 14882: Programming languages — C++. International Organization for Standardization, 2020.
  7. [7]F. M. Ives. Permutation enumeration: four new permutation algorithms. Communications of the ACM, 19(2):68–72, 1976.DOI
  8. [8]Selmer M. Johnson. Generation of permutations by adjacent transposition. Mathematics of Computation, 17:282–285, 1963.DOI
  9. [9]Donald E. Knuth. The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1. Addison–Wesley, 2011.
  10. [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. [11]Donald L. Kreher and Douglas R. Stinson. Combinatorial Algorithms: Generation, Enumeration, and Search. CRC Press, 1999.
  12. [12]Glen G. Langdon, Jr. An algorithm for generating permutations. Communications of the ACM, 10(5):298–299, 1967.DOI
  13. [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. [14]Torsten Mütze. Combinatorial Gray codes — an updated survey. Electronic Journal of Combinatorics, 30(3):#DS26, 2023.arxiv.org/abs/2202.01280
  15. [15]Albert Nijenhuis and Herbert S. Wilf. Combinatorial Algorithms for Computers and Calculators. Academic Press, 2nd edition, 1978.
  16. [16]R. J. Ord-Smith. Generation of permutation sequences: Part 1. The Computer Journal, 13(2):152–155, 1970.
  17. [17]R. J. Ord-Smith. Generation of permutation sequences: Part 2. The Computer Journal, 14(2):136–139, 1971.
  18. [18]J. E. L. Peck and G. F. Schrack. Algorithm 86: Permute. Communications of the ACM, 5(4):208, 1962.DOI
  19. [19]Edward M. Reingold, Jurg Nievergelt, and Narsingh Deo. Combinatorial Algorithms: Theory and Practice. Prentice-Hall, 1977.
  20. [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. [21]Carla Savage. A survey of combinatorial Gray codes. SIAM Review, 39(4):605–629, 1997.DOI
  22. [22]Robert Sedgewick. Permutation generation methods. ACM Computing Surveys, 9(2):137–164, 1977.DOI
  23. [23]Richard P. Stanley. Enumerative Combinatorics, Vol. 1. Cambridge University Press, 2nd edition, 2012.
  24. [24]Hugo Steinhaus. One Hundred Problems in Elementary Mathematics. Basic Books, New York, 1964.
  25. [25]H. F. Trotter. Algorithm 115: Perm. Communications of the ACM, 5(8):434–435, 1962.DOI
  26. [26]Mark B. Wells. Generation of permutations by transposition. Mathematics of Computation, 15:192–195, 1961.DOI
  27. [27]Wikipedia contributors. Heap’s algorithm. https://en.wikipedia.org/wiki/Heap%27s_algorithm, 2026. Accessed 28 October 2026.

Paper details

vlnc:W_xtktrk95
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents