PERMUTING IN PLACE: ANALYSIS OF TWO STOPPING RULES

ALOIS PANHOLZER, HELMUT PRODINGER^{†}, AND MARKO RIEDEL

Abstract. Permuting in place has been first analyzed by Knuth. It uses the cycle structure of the permutation. The elements of an array to be permuted are only moved when one sees a cycle leader (smallest element in its cycle). So the essential part of such an algorithm is to test an element i about whether it is a cycle leader. Recently, Keller [3] introduced two stopping rules: “If the last cycle leader has been detected, all elements have been moved, and no further tests are necessary” (Heuristic 1), resp. “If only r elements have not been moved, then proceeding along a cycle is only useful for r steps” (Heuristic 2).

We analyze the average costs of these modifications applied to the standard algorithm of Knuth; they are (n+2)H_{n}− \frac{5n}{2} − \frac{1}{2} ∼ n log n resp. \frac{2n+1}{4}H_{⌊ \frac{n+1}{2} ⌋}+ \frac{1}{2}H_{2⌊ \frac{n+1}{2} ⌋}− \frac{1}{2}(⌊\frac{n+1}{2}⌋−⌊\frac{n}{2}⌋)− \frac{n+1}{2} ∼ \frac{n}{2} log n, as opposed to (n+1)H_{n}−2n ∼ n log n in the classical case.

1. Introduction and the classical algorithm

Permuting in place has been first analyzed by Knuth [5]; compare also [4, 6]. Further developments can be found in [1].

The algorithm is supposed to permute the elements of a one-dimensional array (x_{1}, …, x_{n}) in place by a permutation π, i. e., replacing the array by (x_{π(1)}, …, x_{π(n)}), using only a bounded amount of auxiliary memory. The permutation π is not allowed to be changed. A most natural way to achieve this is to follow the cycle structure of π. The essential thing is to test an element i about whether it is a cycle leader (the smallest element in its cycle). Once a cycle leader has been found, the elements in the array with indices belonging to that cycle can be easily permuted, and one does this until all cycles have appeared. Naturally, one has to test each individual element whether it is a cycle leader. The classical cycle leader checking algorithm which has been analyzed by Knuth in [5], is given here as Algorithm 1.

The total number of steps to test all the elements 1, …, n, measured by the number of passes of the while-loop in Algorithm 1, is a fundamental parameter for permutation in place. Knuth called it simply “a” (a precise definition follows soon). As Knuth has demonstrated in his fundamental analysis, it is important to consider for a permutation π its canonical representation q_{1} … q_{n} as a product of cycles. It is obtained by arranging the cycles with the cycle leaders in first place, and then arranging them according to their cycle leaders in decreasing order. This is also well described in the book [8].

Date: January 24, 2004.

Key words and phrases. Analysis of Algorithms, permuting in place, Knuth’s parameter a, harmonic numbers.

Part of this work was done during the first author’s visit to the John Knopfmacher Centre for Applicable Analysis and Number Theory at the University of the Witwatersrand, Johannesburg, South Africa.

†Supported by NRF Grant 2053748.

Algorithm 1 Classical cycle leader checking algorithm. Input: π = (π(1), …, π(n)) permutation of length n, 1 ≤ i ≤ n integer. Output: leader ∈ {true, false}, leader = true iff i is a cycle leader.

leader ← true j ← π(i) while j > i do

j ← π(j) end while if j ≠ i then

leader ← false end if

return leader

Knuth’s “parameter a” is much easier to understand in this setting and is then for a given permutation q_{1} … q_{n} defined by

a = #{(i, j) | 1 ≤ i < j ≤ n, q_{i} < q_{i+1}, q_{i} < q_{i+2}, …, q_{i} < q_{j}}.  (1)

There are simple methods to go back and forth between (π(1), …, π(n)) and q_{1} … q_{n}. For all our considerations, we assume that a permutation is given as q_{1} … q_{n}.

In the average-case analysis of the algorithms, we will always assume, that all n! permutations of length n can occur as permutations q_{1} … q_{n} with equal probability; then Knuth’s “parameter a” is on average given by

𝔼(a) = ∑_{1≤i<j≤n} \frac{1}{j − i + 1} = (n + 1)H_{n} − 2n.  (2)

(The numbers involved are the harmonic numbers H_{n} = ∑_{1≤k≤n} 1/k.)

In the recent paper [3], Keller introduced two stopping rules. For his experiments comparing the savings of execution times he used the number of function calls of pi (evaluations π(i) for a given permutation π and any element i) in the cycle leader checking algorithm IsLeader. This parameter, which is denoted here by κ, is related to the a parameter as follows. For each element, which is tested in the algorithm IsLeader about being a cycle leader, Keller counts one more. (Because of the various stopping rules under consideration, not every element must be tested, therefore the difference is not n for all the rules.)

In the classical algorithm, we have of course

κ = #{(i, j) | 1 ≤ i ≤ j ≤ n, q_{i} ≤ q_{i+1}, q_{i} ≤ q_{i+2}, …, q_{i} ≤ q_{j}},  (3)

thus κ = a + n for every permutation of length n, and we have in particular

𝔼(κ) = (n + 1)H_{n} − n.  (4)

Keller says that algorithm A1 (the simple algorithm analyzed by Knuth) behaves on the average like \frac{2}{3}n log n, which does not match with the result (n+1)H_{n}−n. However^{1} Keller means the binary logarithm when he writes log, and 2/(3 log 2) ≈ 0.96. Probably one cannot distinguish this value from the true constant 1 even with Keller’s elaborate experiments. That is why we have to analyze algorithms! There are insights that only a thorough theoretical analysis can unveil.

1Personal communication

In [5], the variance is already given:

𝕍(a) = 𝕍(κ) = 2n^{2} − (n + 1)^{2}H_{n}^{(2)} − (n + 1)H_{n} + 4n,  (5)

which is asymptotically equivalent to (2 − \frac{π^{2}}{6} )n^{2}. (Here the second order harmonic numbers H_{n}^{(2)} = ∑_{1≤k≤n} 1/k^{2} also appear.) In [6], q-analogues for the expectation and the variance of this parameter a are given.

Knuth said in 1972 that the corresponding computation should have been done by a computer. Indeed, recently Carsten Schneider [7] has written an impressive Ph. D. thesis that allows to manipulate intricate sums involving harmonic numbers with a computer. However, his software is not yet in the public domain. For Knuth’s original parameter “a” alternative methods using generating functions are available, see [4, 8]. Certain functional equations allow then, at least in principle, to compute all moments, which was demonstrated in [4]. It was shown there, that asymptotically for n → ∞, the s-th moment 𝔼(a^{s}) is given by n^{s} log^{s} n+(γ −2)sn^{s} log^{s−1} n+O(n^{s} log^{s−2} n), where γ denotes the Euler constant. Studying these equations further, it is even possible to obtain limiting distribution results, as was sketched in [2].

While this sounds promising, for the various modifications (stopping rules) studied in this paper, such manageable functional equations do not seem to exist. One is thus back to the methods that Knuth used already 30 years ago!

Since no theoretical analysis of the average cost of the standard permutation algorithm (called A1 in [3]) together with the stopping rules was provided in [3], we study these parameters a resp. κ in the sequel. The remaining algorithms (A2 and A3 in [3]) seem to be more complicated and are left for future research, as well as the bit complexity of the algorithms^{2}.

Since Knuth and Keller consider two quantities that differ slightly, we analyzed both of them; mathematically, both versions are equally difficult. However, for Keller’s heuristic 2, there is a third variant to be analyzed, namely his implementation of this heuristic. Although this implemenation is slightly inferior to the one presented in this paper, we do so to be able to compare experimental data from Keller’s paper with theoretical formulæ.

2. Analysis of Keller’s heuristic 1

The first heuristic given in [3] and denoted Fastbreak 1 uses the fact that if the last cycle leader has been detected, all elements have been moved (this can be checked easily by simply counting the number of elements already moved), and thus no further tests are necessary. This means that for the remaining elements, the cycle leader checking algorithm Algorithm 1 is not called anymore. That is included in the permutation algorithm given in [3, Fig. 3].

Intuitively, one will expect, that for a length-n permutation the number of function calls (measured by κ) will decrease by this heuristic on average by about n: a length-n permutation has on average log n cycles and the expected length of a cycle is n/ log n; thus the expected savings due to not checking the last cycle are about n/ log n · H_{⌊n/ log n⌋} ∼ n. Our exact computations will confirm this intuition.

2A referee suggested to study this.

We assume that the elements 1, 2, …, n are tested in that order. However, the last cycle leader is the first element q_{1} in the canonical representation!

We will first treat Knuth’s parameter a^{[FB1]} and must consequently consider

a^{[FB1]} = #{(i, j) | 1 ≤ i < j ≤ n, q_{i} < q_{i+1}, …, q_{i} < q_{j} and q_{i} ≤ q_{1}}.  (6)

It is a good idea to recall the original analysis of Knuth: He introduced indicator variables y_{ij}, defined by

y_{ij} = \begin{cases}1 & if q_{i} = min\{q_{i}, q_{i+1}, …, q_{j}\}, \\ 0 & otherwise. \end{cases}

Then the average of “parameter a” is given by

𝔼(a) = ∑_{1≤i<j≤n} 𝔼(y_{ij});

note that 𝔼(y_{ij}) is just the probability that q_{i} = min{q_{i}, q_{i+1}, …, q_{j}}.

For the modification a^{[FB1]} it is a good idea to split the contributions into i = 1 and i ≥ 2, since

y_{ij}^{[FB1]} = \begin{cases}1 & if q_{i} = min\{q_{i}, q_{i+1}, …, q_{j}\} and q_{i} ≤ q_{1}, \\ 0 & otherwise. \end{cases}

We start with the instance i ≥ 2. Assume that q_{1} = L. We compute the probability that q_{i} = min{q_{i}, q_{i+1}, …, q_{j}} and q_{i} < L. It is perhaps slightly easier to think about q_{2} … q_{n} as a random permutation of {1, …, n−1}, and a number L with 0 ≤ L ≤ n−1 being given; we compute the probability that q_{i} = min{q_{i}, q_{i+1}, …, q_{j}} and q_{i} ≤ L. It is

∑_{k=1}^{L} \frac{1}{n − 1} \begin{matrix}( & {n−1−k \atop j−i} & ) \\ ( & {n−2 \atop j−i} & ) \end{matrix} = \frac{1}{(n − 1)\binom{n−2}{j−i}} [\binom{n − 1}{j − i + 1} − \binom{n − 1 − L}{j − i + 1}] .

We need the average of this over L = 0, …, n − 1:

\frac{1}{n} ∑_{L=0}^{n−1} \frac{1}{(n − 1)\binom{n−2}{j−i}} [\binom{n − 1}{j − i + 1} − \binom{n − 1 − L}{j − i + 1}]

= \frac{1}{j − i + 1} − \frac{1}{n(n − 1)\binom{n−2}{j−i}} \binom{n}{j − i + 2}

= \frac{1}{j − i + 1} − \frac{1}{(j − i + 2)(j − i + 1)}

= \frac{1}{j − i + 2}.

For i = 1 we get 1/j, as in the traditional case. Thus

𝔼(a^{[FB1]}) = ∑_{1≤i<j≤n} 𝔼(y_{ij}^{[FB1]}) = ∑_{2≤j≤n} \frac{1}{j} + ∑_{2≤i<j≤n} \frac{1}{j − i + 2}

= H_{n} − 1 + ∑_{3≤r≤n} \frac{n + 1 − r}{r}

= H_{n} − 1 + (n + 1)(H_{n} − \frac{3}{2}) − (n − 2)

= (n + 2)H_{n} − \frac{5n}{2} − \frac{1}{2}.  (7)

For n = 1, 2, 3, 4, … we get the values 0, \frac{1}{2}, \frac{7}{6}, 2, …, which checks. Experiments with permutations of up to 100 elements checked as well.

Knuth sketches this variation already in his original paper [5]. Comparing this result with the formula (n + 1)H_{n} − 2n for the standard case, we see that asymptotically (on average) there are no savings obtained by using this stopping rule.

The computations for κ^{[FB1]} are analogous; for completeness we give its definition

κ^{[FB1]} = #{(i, j) | 1 ≤ i ≤ j ≤ n, q_{i} ≤ q_{i+1}, …, q_{i} ≤ q_{j} and q_{i} ≤ q_{1}}  (8)

and get

𝔼(κ^{[FB1]}) = ∑_{1≤j≤n} \frac{1}{j} + ∑_{1≤i≤j≤n} \frac{1}{j − i + 2},

which gives

𝔼(κ^{[FB1]}) = (n + 2)H_{n} − 2n.  (9)

Next we also sketch the computation of the variances 𝕍(a^{[FB1]}) resp. 𝕍(κ^{[FB1]}). The second moment 𝔼((a^{[FB1]})^{2}) for Knuth’s parameter a is given by

𝔼((a^{[FB1]})^{2}) = 𝔼(a^{[FB1]}) + ∑_{\begin{matrix}1≤i_{1}<j_{1}≤n, \\ 1≤i_{2}<j_{2}≤n, \\ (i_{1},j_{1})≠(i_{2},j_{2}) \end{matrix}} 𝔼(y_{i_{1}j_{1}}^{[FB1]}y_{i_{2}j_{2}}^{[FB1]}),

and by considering all possible cases we get

𝔼((a^{[FB1]})^{2}) = (n + 2)H_{n} − \frac{5n}{2} − \frac{1}{2}

+ 2 ∑_{2≤i_{1}<j_{1}<i_{2}<j_{2}≤n} \frac{1}{j_{1} − i_{1} + j_{2} − i_{2} + 3} (\frac{1}{j_{2} − i_{2} + 2} + \frac{1}{j_{1} − i_{1} + 2})

+ 2 ∑_{2≤i_{1}<i_{2}<j_{2}≤j_{1}≤n} \frac{1}{(j_{1} − i_{1} + 2)(j_{2} − i_{2} + 2)}

+ 2 ∑_{2≤i_{1}<i_{2}≤j_{1}<j_{2}≤n} \frac{1}{(j_{2} − i_{1} + 2)(j_{2} − i_{2} + 2)} + 2 ∑_{2≤i<j_{1}<j_{2}≤n} \frac{1}{j_{2} − i + 2}

+ 2 ∑_{2≤j_{1}<i<j_{2}≤n} \frac{1}{(j_{2} − i + j_{1} + 1)j_{1}} + 2 ∑_{2≤j_{1}<j_{2}≤n} \frac{1}{j_{2}} .

(The last summations cover the cases, where i := i_{1} = i_{2}, resp. i_{1} = i_{2} = 1.)

As an example, we consider the range 2 ≤ i_{1} < i_{2} ≤ j_{1} < j_{2} ≤ n and describe how to compute the quantity 𝔼(y_{i_{1}j_{1}}^{[FB1]}y_{i_{2}j_{2}}^{[FB1]}) = ℙ{y_{i_{1}j_{1}}^{[FB1]}y_{i_{2}j_{2}}^{[FB1]} = 1} via

\frac{1}{n!}\binom{n}{j_{2} − i_{1} + 2}\binom{j_{2} − i_{1} + 1}{j_{2} − i_{2} + 2}(j_{2} − i_{2} + 1)!(i_{2} − i_{1} − 1)!(n − (j_{2} − i_{1} + 2))!

= \frac{1}{(j_{2} − i_{1} + 2)(j_{2} − i_{2} + 2)}.

All permutations with y_{i_{1}j_{1}}^{[FB1]}y_{i_{2}j_{2}}^{[FB1]} = 1 can be obtained in this case in the following way: Choose from the given set {1, …, n} exactly j_{2} − i_{1} + 2 elements, which will be put into positions i_{1}, …, j_{2} resp. position 1 in the way described later on. Of course, the remaining n − (j_{2} − i_{1} + 2) elements can be put into the remaining positions in (n − (j_{2} − i_{1} + 2))! different ways. From the chosen elements we select the smallest and put it into position i_{1}. Next we choose from the j_{2} − i_{1} + 1 remaining elements again a set of j_{2} − i_{2} + 2 elements. The smallest element of this set is put into position i_{2} and the other j_{2} − i_{2} + 1 elements are put in arbitrary order ((j_{2} − i_{2} + 1)! possibilities) into positions 1 resp. i_{2}+1, …, j_{2}. The i_{2}−i_{1}−1 elements that are not chosen in the second round are put in one of (i_{2} − i_{1} − 1)! different ways into the positions i_{1} + 1, …, i_{2} − 1. This leads to the probability as given above. Similar considerations for the remaining cases give the above formula.

We also show for this example how to simplify the sums that are appearing:

∑_{2≤i_{1}<i_{2}≤j_{1}<j_{2}≤n} \frac{1}{(j_{2} − i_{1} + 2)(j_{2} − i_{2} + 2)}

= ∑_{i_{1}=2}^{n−2} ∑_{i_{2}=i_{1}+1}^{n−1} ∑_{j_{2}=i_{2}+1}^{n} ∑_{j_{1}=i_{2}}^{j_{2}−1} \frac{1}{(j_{2} − i_{1} + 2)(j_{2} − i_{2} + 2)}

= ∑_{i_{1}=2}^{n−2} ∑_{j_{2}=i_{1}+2}^{n} ∑_{i_{2}=i_{1}+1}^{j_{2}−1} \frac{1}{j_{2} − i_{1} + 2} (1 − \frac{2}{j_{2} − i_{2} + 2})

= ∑_{i_{1}=2}^{n−2} ∑_{j_{2}=i_{1}+2}^{n} \frac{1}{j_{2} − i_{1} + 2} (j_{2} − i_{1} − 1 − 2(H_{j_{2}−i_{1}+1} − \frac{3}{2}))

= ∑_{i_{1}=2}^{n−2} ∑_{j_{2}=i_{1}+2}^{n} (1 − 2\frac{H_{j_{2}−i_{1}+2}}{j_{2} − i_{1} + 2} + \frac{2}{(j_{2} − i_{1} + 2)^{2}} )

= ∑_{i_{1}=2}^{n−2} (n − i_{1} − 1 − H_{n−i_{1}+2}^{2} − H_{n−i_{1}+2}^{(2)} + H_{3}^{2} + H_{3}^{(2)} + 2H_{n−i_{1}+2}^{(2)} − 2H_{3}^{(2)})

= ∑_{k=1}^{n−3} k − ∑_{k=4}^{n} H_{k}^{2} + ∑_{k=4}^{n} H_{k}^{(2)} + (H_{3}^{2} − H_{3}^{(2)})(n − 3)

\begin{matrix}= \frac{(n − 3)(n − 2)}{2} − (n + 1)H_{n}^{2} + (2n + 1)H_{n} − 2n + 4H_{3}^{2} − 7H_{3} + 6 \\ + (n + 1)H_{n}^{(2)} − H_{n} − 4H_{3}^{(2)} + H_{3} + (n − 3)(H_{3}^{2} − H_{3}^{(2)}); \end{matrix}

we used here and for the remaining cases several identities involving harmonic numbers to simplify the sums that occur. The identities in question are

∑_{k=1}^{n} H_{k} = (n + 1)H_{n} − n,  ∑_{k=1}^{n} H_{k}^{(2)} = (n + 1)H_{n}^{(2)} − H_{n},

∑_{k=1}^{n} \frac{H_{k}}{k} = \frac{1}{2}(H_{n}^{2} + H_{n}^{(2)}),  ∑_{k=1}^{n} kH_{k} = \frac{n(n + 1)}{2}H_{n} − \frac{n(n − 1)}{2},

∑_{k=1}^{n} H_{k}^{2} = (n + 1)H_{n}^{2} − (2n + 1)H_{n} + 2n.

These identities are all known. Once such an identity is known, it can easily be proved by induction. Of course, generating functions also help. As a simple example consider

∑_{n≥1} H_{n}z^{n} = \frac{1}{1 − z} log \frac{1}{1 − z};

from this explicit form various others can be derived by standard manipulations, such as differentiations, integrations, etc. Of course, they can all be derived with C. Schneider’s software Σ, see [7].

By simplifying the remaining sums in the same manner, we get a closed form for the second moment. Subtracting the square of the expectation from that we finally find that the variance 𝕍(a^{[FB1]}) = 𝔼((a^{[FB1]})^{2}) − (𝔼(a^{[FB1]}))^{2} is given by

𝕍(a^{[FB1]}) = −(2n + 3)H_{n}^{2} − (n + 1)^{2}H_{n}^{(2)} + (3n − 2)H_{n} + \frac{31}{12}n^{2} + \frac{11}{2}n − \frac{1}{12}, (10)

and asymptotically by

𝕍(a^{[FB1]}) = (\frac{31}{12} − \frac{π^{2}}{6} )n^{2} + O(n log^{2} n).  (11)

Analogous computations give the variance 𝕍(κ^{[FB1]}):

𝕍(κ^{[FB1]}) = −(2n + 3)H_{n}^{2} − (n + 1)^{2}H_{n}^{(2)} + (n − 4)H_{n} + 3n(n + 3),  (12)

and asymptotically

𝕍(κ^{[FB1]}) = (3 − \frac{π^{2}}{6} )n^{2} + O(n log^{2} n).  (13)

3. Analysis of Keller’s heuristic 2

Heuristic 2 for cycle leader checking (called Fastbreak 2) is described by Keller as follows: If only r elements have not been visited yet by function PermuteCycle, then proceeding along a cycle is only useful for r steps. Otherwise, the cycle currently traversed must contain an element that has already been visited by function PermuteCycle, the cycle hence has already been permuted, and i cannot be a leader.

An implementation of this heuristic 2 was given by Keller (see [3, Fig. 4]), and is here also given as Algorithm 2.

It should be remarked that this implementation of heuristic 2 does not make full usage of the power of this rule, since in the implementation, the cycle leader check is not stopped (if not earlier by other conditions) until the number of steps that are done Algorithm 2 Keller’s cycle leader checking algorithm from [3] for heuristic 2.

Input: π = (π(1), …, π(n)) permutation of length n,

1 ≤ i ≤ n, 0 ≤ remaining ≤ n integers. Output: leader ∈ {true, false}, leader = true iff i is a cycle leader.

j ← i

leader ← true

steps ← 0

repeat j ← π(j) steps ← steps + 1 if (j < i) or (steps > remaining) then

leader ← false break end if

until j = i

return leader

checking a certain element is larger than the number of remaining steps. However, one could already leave when the number of steps equals the number of remaining steps. Then we either found a cycle of the length of the number of remaining steps, and we call the permuting algorithm, or we know then that the checked element is not a cycle leader. A modified cycle leader checking algorithm, which uses this principle is given as Algorithm 3. It is assumed, that each implementation (Algorithm 2 or Algorithm 3) is used together with the permutation algorithm given in [3, Fig. 3]. Then it is guaranteed, that the case, where (in above described heuristic 2) r = 0 elements have not been visited, is also covered (this is exactly heuristic 1). We implemented all algorithms in C as well since all algorithms given by Keller are implemented in C. These versions can be obtained from the authors. We replaced Keller’s “TestHypo(j,i)” by “j ≥ i” since that is exactly what it is. Our average-case analysis is based on this improved implementation.

In Keller’s implementation of heuristic 2 as given by Algorithm 2, more function calls are made on average, and although this has asymptotically no influence to the main term, the savings are quite noteworthy for smaller sizes. The smallest permutation where a difference between both implementations occurs is (4)(123). Detecting element 1 as a cycle leader requires in both implementations 3 function calls, but by checking the element 2 for a possible cycle leader, one could stop after one step (it is already known, that only a cycle of length one is missing), but Keller’s implementation uses 2 steps. Since by checking the elements 3 and 4 for possible cycle leaders, both implementations make one function call for each element, we obtain that Algorithm 3 requires here 6 function calls whereas Algorithm 2 requires 7 function call. Since all the experimental results in [3] are given for his implementation, we briefly analyze this version also.

Now we come to the average-case analysis of the algorithm with heuristic 2 as implemented by Algorithm 3. We first study the parameter κ (the number of function calls) in detail, showing how to compute 𝔼(κ^{[FB2]}).

For Knuth’s parameter a (the number of passes of the while-loop), we only give the formula for the expectation and omit the analogous computations to produce 𝔼(a^{[FB2]}).

Algorithm 3 Keller’s cycle leader checking algorithm from [3] for heuristic 2 with improvement as discussed in the text. Input: π = (π(1), …, π(n)) permutation of length n,

1 ≤ i ≤ n, 0 ≤ remaining ≤ n integers. Output: leader ∈ {true, false}, leader = true iff i is a cycle leader.

leader ← true

j ← π(i)

steps ← 1

while (j > i) and (steps < remaining) do j ← π(j) steps ← steps + 1

end while

if j ≠ i then

leader ← false end if

return leader

The third variation that we briefly discuss at the end of this section, as the computations are somewhat similar, is the study of the number of function calls in Keller’s implementation given by Algorithm 2. We will also obtain a formula for 𝔼(κ̃^{[FB2]}).

If q_{1} … q_{n} is the (canonical) cycle representation of a given permutation π of length n, then we get the following number κ^{[FB2]} of function calls:

κ^{[FB2]} = #{(i, j) | 1 ≤ i ≤ j ≤ n, (q_{i} ≤ q_{i+1}, q_{i} ≤ q_{i+2}, …, q_{i} ≤ q_{j}) and

[(j − i + 2 ≤ min_{k<i} {k | q_{k} < q_{i} and q_{1} > q_{i}, …, q_{k−1} > q_{i}} )

or (q_{1} > q_{i}, …, q_{i−1} > q_{i})] }. (14)

Then a first formula for the expected value 𝔼(κ^{[FB2]}) of this parameter is given by the following expression:

𝔼(κ^{[FB2]}) = ∑_{1≤i≤j≤n} \frac{1}{n!} ∑_{L=1}^{n} [\binom{n − L}{j − 1}(j − 1)!(n − j)!  (15)

+ ∑_{k=j−i+2}^{i−1} \binom{n − L}{j − i + k − 1}(j − i + k − 1)!(L − 1)(n − k − (j − i) − 1)!].

It is obtained by summing up the expectations of the indicator variable which is true iff the function call π(q_{j}) is made when testing q_{i} as a possible cycle leader for 1 ≤ i ≤ j ≤ n. This means of course that at least j − i + 1 function calls are done to check whether q_{i} is a cycle leader. This happens only if q_{i+1} > q_{i}, …, q_{j} > q_{i} and either q_{i} is actually a cycle leader (q_{1} > q_{i}, …, q_{i−1} > q_{i}) or the number of steps j − i + 1 is not larger than the number of remaining steps, which is given by k − 1, where k is the position of the largest cycle leader q_{k} being smaller than q_{i} (q_{k} < q_{i} and q_{1} > q_{i}, …, q_{k−1} > q_{i}). If one distinguishes the possible values of L := q_{i} the formula (15) follows.

10 A. PANHOLZER, H. PRODINGER, AND M. RIEDEL

In the following we want to get a closed formula for the expression (15). We consider first the simpler part of this expression and get

∑_{i=1}^{n} ∑_{j=i}^{n} \frac{1}{n!} ∑_{L=1}^{n} \binom{n − L}{j − 1}(j − 1)!(n − j)! = \frac{1}{n} ∑_{i=1}^{n} ∑_{j=i}^{n} \frac{1}{\binom{n−1}{j−1}} ∑_{L=1}^{n} \binom{n − L}{j − 1}

= \frac{1}{n} ∑_{i=1}^{n} ∑_{j=i}^{n} \begin{matrix}( & {n \atop j} & ) \\ ( & {n−1 \atop j−1} & ) \end{matrix} = ∑_{i=1}^{n} ∑_{j=i}^{n} \frac{1}{j} = ∑_{j=1}^{n} \frac{1}{j} ∑_{i=1}^{j} 1 = n.

For the other part of expression (15) we get first

∑_{i=1}^{n} ∑_{j=i}^{n} \frac{1}{n!} ∑_{L=1}^{n} ∑_{k=j−i+2}^{i−1} \binom{n − L}{j − i + k − 1}(j − i + k − 1)!(L − 1)(n − k − (j − i) − 1)!

= \frac{1}{n(n − 1)} ∑_{i=1}^{n} ∑_{j=i}^{n} ∑_{k=j−i+2}^{i−1} \frac{1}{\binom{n−2}{j−i+k−1}} ∑_{L=1}^{n} \binom{n − L}{j − i + k − 1}(L − 1)

= \frac{1}{n − 1} ∑_{i=1}^{n} ∑_{j=i}^{n} ∑_{k=j−i+2}^{i−1} \frac{1}{\binom{n−2}{j−i+k−1}} ∑_{L=1}^{n} \binom{n − L}{j − i + k − 1}

− \frac{1}{n} ∑_{i=1}^{n} ∑_{j=i}^{n} ∑_{k=j−i+2}^{i−1} \frac{1}{\binom{n−1}{j−i+k}} ∑_{L=1}^{n} \binom{n − L + 1}{j − i + k}

= \frac{1}{n − 1} ∑_{i=1}^{n} ∑_{j=i}^{n} ∑_{k=j−i+2}^{i−1} \begin{matrix}( & {n \atop j−i+k} & ) \\ ( & {n−2 \atop j−i+k−1} & ) \end{matrix} − \frac{1}{n} ∑_{i=1}^{n} ∑_{j=i}^{n} ∑_{k=j−i+2}^{i−1} \begin{matrix}( & {n+1 \atop j−i+k+1} & ) \\ ( & {n−1 \atop j−i+k} & ) \end{matrix}

= ∑_{i=1}^{n} ∑_{j=i}^{n} ∑_{k=j−i+2}^{i−1} (\frac{n}{(j − i + k)(n − (j − i) − k)} − \frac{n + 1}{(j − i + k + 1)(n − (j − i) − k)})

= ∑_{i=1}^{n} ∑_{l=0}^{n−i} ∑_{k=l+2}^{i−1} (\frac{1}{l + k} − \frac{1}{l + k + 1}) = ∑_{i=3}^{n} ∑_{l=0}^{min(i−3,n−i)} ∑_{k=l+2}^{i−1} (\frac{1}{l + k} − \frac{1}{l + k + 1})

= ∑_{i=3}^{n} ∑_{l=0}^{min(i−3,n−i)} (\frac{1}{2l + 2} − \frac{1}{l + i}) .

This sum can be further simplified to

∑_{i=3}^{n} ∑_{l=0}^{min(i−3,n−i)} (\frac{1}{2l + 2} − \frac{1}{l + i}) = ∑_{l=0}^{⌊ \frac{n+1}{2} ⌋−2} ∑_{i=l+3}^{n−l} (\frac{1}{2l + 2} − \frac{1}{l + i})

= ∑_{l=0}^{⌊ \frac{n+1}{2} ⌋−2} (\frac{n}{2l + 2} − 1 − H_{n} + H_{2l+2})

= (⌊\frac{n − 1}{2}⌋ + \frac{1}{2})H_{2⌊ \frac{n−1}{2} ⌋} + (\frac{n}{2} + \frac{1}{4})H_{⌊ \frac{n−1}{2} ⌋} − ⌊\frac{n − 1}{2}⌋H_{n} − 2⌊\frac{n − 1}{2}⌋,

PERMUTING IN PLACE 11

where we used

∑_{k=1}^{n} H_{2k} = (n + \frac{1}{2})H_{2n} + \frac{1}{4}H_{n} − n.

Adding both parts, we get for the expected number 𝔼(κ^{[FB2]}) of function calls

𝔼(κ^{[FB2]}) = (⌊\frac{n − 1}{2}⌋ + \frac{1}{2})H_{2⌊ \frac{n−1}{2} ⌋} + (\frac{n}{2} + \frac{1}{4})H_{⌊ \frac{n−1}{2} ⌋} − ⌊\frac{n − 1}{2}⌋H_{n}

− 2⌊\frac{n − 1}{2}⌋ + n.

It can also be written as

𝔼(κ^{[FB2]}) = (⌊\frac{n}{2}⌋ + \frac{1}{4})H_{⌊ \frac{n}{2} ⌋} + \frac{1}{2}H_{n} + \frac{1}{2} (⌈\frac{n}{2}⌉ − ⌊\frac{n}{2}⌋) (H_{⌊ \frac{n}{2} ⌋} + 1),  (16)

and is asymptotically given by

𝔼(κ^{[FB2]}) = \frac{1}{2}n log n + O(n).  (17)

For Knuth’s parameter a^{[FB2]}, defined by

a^{[FB2]} = #{(i, j) | 1 ≤ i < j ≤ n, (q_{i} < q_{i+1}, q_{i} < q_{i+2}, …, q_{i} < q_{j}) and

[(j − i + 2 ≤ min_{k<i} {k | q_{k} < q_{i} and q_{1} > q_{i}, …, q_{k−1} > q_{i}} )

or (q_{1} > q_{i}, …, q_{i−1} > q_{i})] }, (18)

we get in the same style the expectation

𝔼(a^{[FB2]}) = \frac{2n + 1}{4}H_{⌊ \frac{n+1}{2} ⌋} + \frac{1}{2}H_{2⌊ \frac{n+1}{2} ⌋} − \frac{1}{2}(⌊\frac{n + 1}{2}⌋ − ⌊\frac{n}{2}⌋) − \frac{n + 1}{2}. (19)

In Keller’s implementation of heuristic 2, the number κ̃^{[FB2]} of function calls for a given permutation π of length n can be described by

κ̃^{[FB2]} = #{(i, j) | 1 ≤ i < j ≤ n, (q_{i} < q_{i+1}, q_{i} < q_{i+2}, …, q_{i} < q_{j}) and

[(j − i + 1 ≤ min_{k<i} {k | q_{k} < q_{i} and q_{1} > q_{i}, …, q_{k−1} > q_{i}} )

or (q_{1} > q_{i}, …, q_{i−1} > q_{i}) ]} + # {i | q_{i} ≤ q_{1}} . (20)

The expected value 𝔼(κ̃^{[FB2]}) is then given by the following expression:

𝔼(κ̃^{[FB2]}) = ∑_{1≤i<j≤n} \frac{1}{n!} ∑_{L=1}^{n} [\binom{n − L}{j − 1}(j − 1)!(n − j)!

+ ∑_{k=j−i+1}^{i−1} \binom{n − L}{j − i + k − 1}(j − i + k − 1)!(L − 1)(n − k − (j − i) − 1)!]

+ \frac{1}{2}(n − 1) + 1.  (21)

One computes

∑_{i=1}^{n} ∑_{j=i+1}^{n} \frac{1}{n!} ∑_{L=1}^{n} \binom{n − L}{j − 1}(j − 1)!(n − j)! = n − H_{n},

∑_{i=1}^{n} ∑_{j=i+1}^{n} \frac{1}{n!} ∑_{L=1}^{n} ∑_{k=j−i+1}^{i−1} \binom{n − L}{j − i + k − 1}(j − i + k − 1)!(L − 1)(n − k − (j − i) − 1)!

= ∑_{i=2}^{n} ∑_{l=1}^{min(i−2,n−i)} (\frac{1}{2l + 1} − \frac{1}{l + i}) = ∑_{l=1}^{⌊ \frac{n}{2} ⌋−1} ∑_{i=l+2}^{n−l} (\frac{1}{2l + 1} − \frac{1}{l + i})

=^{n>1} (n + ⌊\frac{n}{2}⌋ + \frac{1}{2})H_{2⌊ \frac{n}{2} ⌋−1} − (\frac{n}{2} + \frac{1}{4})H_{⌊ \frac{n}{2} ⌋−1} − (⌊\frac{n}{2}⌋ − 1)H_{n} − 2⌊\frac{n}{2}⌋ − n + \frac{1}{2},

where we used for the last equation the formula

∑_{k=0}^{n} H_{2k+1} = (n + \frac{3}{2})H_{2n+1} − n − \frac{1}{2} − \frac{1}{4}H_{n}.

Adding all parts, one gets a formula for 𝔼(κ̃^{[FB2]}), which can be simplified to

𝔼(κ̃^{[FB2]}) = \frac{1}{2}(n + 1)H_{n} − \frac{n}{2} + \frac{1}{2} + \frac{n}{2}H_{2⌊ \frac{n}{2} ⌋} − (\frac{n}{2} + \frac{1}{4})H_{⌊ \frac{n}{2} ⌋},  (22)

and is asymptotically again given by

𝔼(κ̃^{[FB2]}) = \frac{1}{2}n log n + O(n).  (23)

4. Experimental results compared to the mathematical formulæ

In order to compare our theoretical findings of the expected savings due to heuristics 1 resp. 2, we also produced some experimental results. We used the computer algebra system Maple and generated for each n = 2^{5}, 2^{6}, …, 2^{20} with the randperm function of the combinat package 50 random permutations of length n and counted the number of function calls within the cycle leader checking algorithm for each of the analyzed variants.

Figures 1, 2 and 3 show the savings of function calls using heuristic 1, heuristic 2 (the improved implementation given in this paper) and heuristic 2 (implementation by Keller), compared to the standard algorithm. In the figures the horizontal bars mark for each n the mean value of the experimental result, whereas the boxes mark the theoretical average savings, which are obtained from our formulæ κ, κ^{[FB1]}, κ^{[FB2]} resp. κ̃^{[FB2]}.

Figure 1. Expected savings of function calls with heuristic 1.

Figure 2. Expected savings of function calls with heuristic 2 (implementation presented in this paper).

Figure 3. Expected savings of function calls with heuristic 2 (Keller’s implementation).

Our theoretical results fit quite well with the experimental results presented here and also with the experimental results given by Keller, although only relatively small test sets are used (compared to the huge number of permutations of length 2^{20}, say).

For the reader’s convenience, we collect our major findings in a table.

quantity  name def.  exact formula  asympt.
Knuth’s parameter “a”  a  (1)  (n + 1)H_{n} − 2n  n log n
Keller’s version “κ”  κ  (3)  (n + 1)H_{n} − n  n log n
“a” with Fastbreak 1 a^{[FB1]} (6)  (n + 2)H_{n} − \frac{5n}{2} − \frac{1}{2}  n log n
“κ” with Fastbreak 1 κ^{[FB1]} (8)  (n + 2)H_{n} − 2n  n log n
“a” with Fastbreak 2 a^{[FB2]} (18)  \frac{2n+1}{4}H_{⌊ \frac{n+1}{2} ⌋} + \frac{1}{2}H_{2⌊ \frac{n+1}{2} ⌋}  \frac{1}{2}n log n
−\frac{1}{2}(⌊\frac{n+1}{2}⌋ − ⌊\frac{n}{2}⌋) − \frac{n+1}{2}
“κ” with Fastbreak 2 κ^{[FB2]} (14)  (⌊\frac{n}{2}⌋ + \frac{1}{4})H_{⌊ \frac{n}{2} ⌋} + \frac{1}{2}H_{n}  \frac{1}{2}n log n
+\frac{1}{2}(⌈\frac{n}{2}⌉ − ⌊\frac{n}{2}⌋)(H_{⌊ \frac{n}{2} ⌋} + 1)
Keller’s implementation κ̃^{[FB2]} (20)  (n + ⌊\frac{n}{2}⌋ + \frac{1}{2})H_{2⌊ \frac{n}{2} ⌋−1}  \frac{1}{2}n log n
of “κ” with Fastbreak 2  −(\frac{n}{2} + \frac{1}{4})H_{⌊ \frac{n}{2} ⌋−1} − (⌊\frac{n}{2}⌋ − 1)H_{n}
−2⌊\frac{n}{2}⌋ − n + \frac{1}{2}

Figure 4. The averages of the parameters studied in this paper.

Acknowledgment. The comments of two referees helped to improve the presentation.

References

1. F. E. Fich, J. I. Munro, and P. V. Poblete, Permuting in place, SIAM Journal on Computing 24 (1995), 266–278.

2. H.-K. Hwang and R. Neininger, Phase change of limit laws in the quicksort recurrence under varying toll functions, SIAM Journal on Computing 31 (2002), 1687–1722.

3. J. Keller, A heuristic to accelerate in–situ permutation algorithms, Information Processing Letters 81 (2002), 119–125.

4. P. Kirschenhofer, H. Prodinger, and R. F. Tichy, A contribution to the analysis of in situ permutation, Glasnik Mathematicki 22(42) (1987), 269–278.

5. D. E. Knuth, Mathematical analysis of algorithms, Information Processing 71, North Holland Publishing Company, 1972, Proceedings of IFIP Congress, Ljubljana, 1971, pp. 19–27. Reprinted in: Selected papers on analysis of algorithms, CSLI Publications, Stanford, CA, 2000.

6. H. Prodinger, Combinatorics of geometrically distributed random variables: Inversions and a parameter of Knuth, Annals of Combinatorics 5 (2001), 241–250.

7. C. Schneider, Symbolic summation in difference fields, PhD thesis, Univ. Linz, 2001.

8. R. Sedgewick and P. Flajolet, An introduction to the analysis of algorithms, Addison-Wesley, 1996.

Alois Panholzer, Institut für Algebra und Computermathematik, TU Wien, Wiedner Hauptstr. 8-10, 1040 Wien, Austria

  E-mail address: Alois.Panholzer@tuwien.ac.at

Helmut Prodinger, The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa

  E-mail address: helmut@staff.ms.wits.ac.za

Marko Riedel, EDV, Neue Arbeit gGmbH, Presselstr. 29, 70191 Stuttgart, Germany

  E-mail address: mriedel@neuearbeit.de