\documentclass[12pt,a4paper,reqno]{amsart}%{article}
\usepackage{url}
\usepackage{array}
\usepackage{epsfig}

\usepackage{algorithmic,algorithm}


%\renewcommand{\algorithmicrepeat}{\textbf{do}}
%\renewcommand{\algorithmicuntil}{\textbf{while}}

\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

\newcommand{\assign}{\leftarrow}
\newcommand{\NOT}{\textbf{not}\ }
\newcommand{\AND}{\textbf{and}\ }
\newcommand{\OR}{\textbf{or}\ }

%\RequirePackage{theorem}

\allowdisplaybreaks

\hfuzz=10pt

\newtheorem{theorem}{Theorem}%[section]
\newtheorem{proposition}{Proposition}%[section]
\newtheorem{lemma}{Lemma}%[section]
\newtheorem{cor}{Corollary}
\renewcommand{\thecor}{}
\newtheorem{ncor}{Corollary}

\newtheorem{df}{Definition}[section]
\newtheorem{ex}{Example}
\renewcommand{\theex}{}

\def\aK{a^{\textrm{[FB1]}}}
\def\kK{\kappa^{\textrm{[FB1]}}}
\def\ak{a^{\textrm{[FB2]}}}
\def\kk{\kappa^{\textrm{[FB2]}}}
\def\kt{\tilde{\kappa}^{\textrm{[FB2]}}}
\def\U{{\cal{U}}}
\def\E{{\cal{E}}}
\def\T{{\cal{T}}}
\def\P{{\cal{P}}}
\def\a{{\bold{a}}}
\def\p{{\bold{p}}}
\def\la{\lambda}
\def\mcirc{{\bigcirc}}
\def\dilog{\operatorname{dilog}}
\def\C{{\cal C}}
\def\P{{\cal P}}
\newcommand{\gauss}[2]{\genfrac{[}{]}{0
pt}{}{#1}{#2}_q}  
\newcommand{\gausss}[2]{\genfrac{[}{]}{
0pt}{}{#1}{#2}_{1/q}}
\def\bl{\operatorname{L}}






\newtheorem{rem}{Remark}
\renewcommand{\therem}{}
\newtheorem{nrem}{Remark}

%\section{packages}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
%\usepackage{theorem}
%\usepackage{xspace}

\topmargin 0 pt                        
\textheight 46\baselineskip     
\advance\textheight by \topskip

\setlength{\textwidth}{155mm}         
\setlength{\oddsidemargin}{5.6mm}     
\setlength{\evensidemargin}{5.6mm}   





\def\Prob{\mathbb{P}}

\newcommand{\Res}[1]{\mathop{\textrm{Re
s}}\nolimits\left\ldlm#1\right\rdlm}
                                       
            % Residue
\newcommand{\ffact}[2]{#1^{\underline{#2}}}
\newcommand{\img}{\text{i}}
\newcommand{\bigOh}{\mathop{\mathcal{O}
}\nolimits}  
\newcommand{\Pm}{\operatorname{pm}}
\def\bb#1{[\![#1]\!]}
\def\a{\alpha}
\def\b{\beta}


%\section{preamble}
\title[Permuting in place]
{Permuting in place: Analysis of two stopping rules}

\author[A.~Panholzer]{Alois Panholzer}
\address{Alois Panholzer\\
Institut f{\"u}r Algebra und Computermathematik\\
TU Wien\\
Wiedner Hauptstr. 8-10\\
1040 Wien, Austria}
\email{Alois.Panholzer@tuwien.ac.at} 
\thanks{ 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}

\author[H.~Prodinger]{Helmut Prodinger$^\dag{}$}


\thanks{$^\dag{}$Supported by NRF Grant 2053748}


\address{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}
\email{helmut@staff.ms.wits.ac.za}

\author[M.~Riedel]{Marko Riedel}
\address{Marko Riedel\\
EDV, Neue Arbeit gGmbH\\
Presselstr. 29, 70191 Stuttgart, Germany}
\email{mriedel@neuearbeit.de} 

\keywords{Analysis of Algorithms, permuting in place, Knuth's parameter $a$, 
harmonic numbers}

\date{\today}


\begin{document}



\begin{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 \cite{Keller02} 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}\sim n\log n$ resp. 
$\frac{2n+1}{4} H_{\lfloor\frac{n+1}{2}\rfloor} 
   + \frac{1}{2} H_{2\lfloor\frac{n+1}{2}\rfloor} 
   - \frac{1}{2} (\lfloor\frac{n+1}{2}\rfloor - \lfloor\frac{n}{2}\rfloor) 
   - \frac{n+1}{2}\sim\frac n2\log n$, as opposed to $(n+1)H_n-2n\sim n\log n$
in the classical case. 
\end{abstract}

\maketitle

\section{Introduction and the classical algorithm}

Permuting in place has been first analyzed by Knuth \cite{Knuth72};
compare also \cite{KiPrTi87, Prodinger99}.
Further developments can be found in \cite{FiMuPo95}.

The algorithm is supposed to permute the elements of a one-dimensional
array $(x_1,\ldots,x_n)$ in place by a permutation $\pi$, i.~e., 
replacing the array by $(x_{\pi(1)},\ldots,x_{\pi(n)})$, using only a
bounded amount of auxiliary memory. The permutation $\pi$ is not allowed to
be changed.  A most natural way to achieve this is to follow the cycle
structure of $\pi$. 
 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 \cite{Knuth72}, is  given here as Algorithm~\ref{alg1}.
\begin{algorithm}\label{fig5}
  \caption{Classical cycle leader checking algorithm.
\label{alg1}}
  \begin{algorithmic}
    \REQUIRE $\pi = (\pi(1), \dots, \pi(n))$ permutation of length $n$,
    $1 \le i \le n$ integer.
    \ENSURE $\textrm{leader} \in \{\textrm{true},\textrm{false}\}$, $\textrm{leader}=\textrm{true}$
     iff $i$ is a cycle leader.% and $\textrm{leader}=\textrm{false}$ otherwise.
   
    \STATE $\textrm{leader} \assign \textrm{true}$
	\STATE $j \assign \pi(i)$
        
    \WHILE{$j > i$}{
       \STATE $j \assign \pi(j)$}
    \ENDWHILE
    \IF{$j \neq i$} \STATE $\textrm{leader} \assign \textrm{false}$ \ENDIF
    \STATE $\textbf{return} \; \textrm{leader}$
  \end{algorithmic}
\end{algorithm}

The total number of steps to test all the elements $1,\ldots,n$, 
measured by the number of passes of the {\texttt{while}}-loop
in Algorithm~\ref{alg1}, 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 $\pi$ its canonical representation $q_1\dots 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 \cite{SeFl96}. 
Knuth's ``parameter $a$'' is much easier to understand in this setting and
is then for a given permutation $q_1\dots q_n$ defined by
\begin{equation}\label{def_a}   
a=\#\{(i,j)\mid 1 \le i<j\le n,\quad q_i<q_{i+1},q_i<q_{i+2},\dots, q_i<q_j\}.
\end{equation}
There are simple methods to go back and forth between $(\pi(1),\ldots,\pi(n))$
and $q_1\dots q_n$. For all our considerations, we assume that a permutation
is given as $q_1\dots 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\dots q_n$ with equal probability;
then Knuth's ``parameter $a$'' is on average given by
%
\begin{equation}   
\mathbb{E}(a)=\sum_{1\le i< j\le n}\frac{1}{j-i+1}=(n+1)H_n-2n.
\end{equation}
%
(The numbers involved are the harmonic numbers $H_n=\sum_{1\le k\le n}1/k$.)



\medskip

In the recent paper \cite{Keller02}, Keller introduced two stopping rules.
For his experiments  comparing the savings of execution times
he used  the number
of \emph{function calls} of \texttt{pi} 
(evaluations $\pi(i)$ for a given permutation $\pi$ 
and any element $i$) in the cycle leader checking algorithm \texttt{IsLeader}.
This parameter, which is  denoted here by $\kappa$, is related to the $a$ parameter
as follows. For each element, which is tested 
in the algorithm \texttt{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
\begin{equation}\label{def_keller}
\kappa=\#\{(i,j)\mid 1 \le i \le j\le n,\quad q_i \le q_{i+1},q_i \le q_{i+2},\dots, q_i \le q_j\},   
\end{equation}
thus $\kappa=a+n$ for every permutation of length $n$, and we have in particular
\begin{equation}   
\mathbb{E}(\kappa)=(n+1)H_n-n.
\end{equation}

\medskip

Keller says that algorithm \textbf{A1} (the simple
algorithm analyzed by Knuth) behaves on the average like $\frac23 n\log n$,
which does not match with the result $(n+1)H_n-n$. 
However\footnote{Personal communication}
Keller means the binary logarithm when he writes $\log$, and
 $2/(3\log2)\approx 0.96$.
Probably one cannot distinguish this value 
from the true constant~$1$ even with Keller's elaborate experiments.
That is why we \emph{have} to analyze algorithms! There are insights that
only a thorough theoretical analysis can unveil.

\medskip

In \cite{Knuth72}, the variance is already given:
\begin{equation}
   \mathbb{V}(a) = \mathbb{V}(\kappa) = 2n^2 -(n+1)^2 H_{n}^{(2)} - 
     (n+1) H_{n} + 4n,
\end{equation}
which is asymptotically equivalent to $(2-\frac{\pi^2}{6}) n^{2}$.
(Here the second order harmonic numbers $H_{n}^{(2)} = \sum_{1 \le k \le n} 1/k^{2}$
also appear.)
In \cite{Prodinger99}, $q$-analogues for the expectation and the variance of this
parameter $a$ are given.
\smallskip

Knuth said in 1972 that the corresponding computation should have been done by
a computer. Indeed, recently Carsten Schneider \cite{Schneider01} 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 \cite{KiPrTi87, SeFl96}. Certain
functional equations allow then, at least in principle, to compute all moments,
which was demonstrated in \cite{KiPrTi87}. It was shown there, that asymptotically
for $n \to \infty$, the $s$-th moment
$\mathbb{E}(a^{s})$ is given by $n^{s} \log^{s} n + (\gamma - 2) s n^{s} \log^{s-1} n+ \mathcal{O}(n^{s} \log^{s-2} n)$, where $\gamma$ denotes the Euler constant.
Studying these equations further, 
it is even possible to obtain limiting distribution results, 
as was sketched in \cite{HwNe02}.

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!



\medskip

Since no theoretical analysis of the average cost of the standard permutation algorithm 
(called \textbf{A1} in \cite{Keller02}) together
with the stopping rules was provided in \cite{Keller02}, 
we study these parameters $a$ resp. $\kappa$ in the sequel. The remaining
algorithms (\textbf{A2} and \textbf{A3} in \cite{Keller02}) seem
to be more complicated and are left for future research, as well as
the \emph{bit complexity} of the algorithms\footnote{A referee suggested to
study this.}.

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{\ae}.








\section{Analysis of Keller's heuristic 1}

The first heuristic given in \cite{Keller02} and denoted \texttt{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~\ref{alg1} is not called anymore. 
That is included in the permutation algorithm given in \cite[Fig.~3]{Keller02}.

Intuitively, one will expect, that for a length-$n$ permutation the number of function calls 
(measured by $\kappa$) 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 \cdot H_{\lfloor n/\log n\rfloor} \sim n$. 
Our exact computations will confirm this intuition.

We assume that the elements $1,2,\dots,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 $\aK$ and must consequently consider 
\begin{equation}\label{def_afb1}   
\aK=\#\{(i,j)\mid 1 \le i<j\le n,\quad q_i < q_{i+1},\dots, q_i < q_j
\textbf{\ and  } q_i\le q_1\}.
\end{equation}
%

\medskip

It is a good idea to recall the original analysis of Knuth:
He introduced indicator variables $y_{ij}$, defined by
\begin{equation*}   
y_{ij}=\begin{cases}   
1 &\text{if\ } q_i=\min\{q_i,q_{i+1},\dots,q_j\},\\
0&\text{otherwise.}
\end{cases}
\end{equation*} 
%
Then the average of ``parameter $a$'' is given by
\begin{equation*}   
\mathbb{E}(a)=\sum_{1\le i<j\le n}\mathbb{E}(y_{ij});
\end{equation*}
note that $\mathbb{E}(y_{ij})$ is just the probability that
$q_i=\min\{q_i,q_{i+1},\dots,q_j\}$. 

For the modification $\aK$ it is a good idea to split
the contributions into $i=1$ and $i\ge2$, since
\begin{equation*}   
y_{ij}^{\textrm{[FB1]}}=\begin{cases}   
1 &\text{if\ } q_i=\min\{q_i,q_{i+1},\dots,q_j\} \textbf{\ and  } q_i\le q_1,\\
0&\text{otherwise.}
\end{cases}
\end{equation*} 

We start with the instance $i \ge 2$. 
Assume that $q_1=L$. We compute the probability that
$q_i=\min\{q_i,q_{i+1},\dots,q_j\}$ \textbf{\ and\ } $q_i< L$. It is perhaps
slightly easier to think about $q_2\dots q_n$  as a random
permutation of $\{1,\dots,n-1\}$, and a number $L$ with
$0\le L\le n-1$ being given; we compute the probability that
$q_i=\min\{q_i,q_{i+1},\dots,q_j\} \textbf{\ and\ } q_i\le L$.
It is
\begin{align*}
\sum_{k=1}^L\frac{1}{n-1}\frac{\binom{n-1-k}{j-i}}{\binom{n-2}{j-i}}&=
\frac{1}{(n-1)\binom{n-2}{j-i}}\left[
\binom{n-1}{j-i+1}-\binom{n-1-L}{j-i+1}\right].
\end{align*}
We need the average of this over $L=0,\dots,n-1$:
\begin{align*}
\frac{1}{n}\sum_{L=0}^{n-1}\frac{1}{(n-1)\binom{n-2}{j-i}}{}&{}\left[
\binom{n-1}{j-i+1}-\binom{n-1-L}{j-i+1}\right]\\
&=\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}.\\
\end{align*} 
%
For $i=1$ we get $1/j$, as in the traditional case. 
 Thus
\begin{align}
\mathbb{E}({\aK})=\sum_{1\le i<j\le n}\mathbb{E}(y_{ij}^{\textrm{[FB1]}})
&=\sum_{2\le j\le n}\frac{1}{j}+
\sum_{2\le i<j\le n}\frac{1}{j-i+2} \notag\\*
&=H_n-1+\sum_{3\le r\le n}\frac{n+1-r}{r} \notag\\
&=H_n-1+(n+1)\Big(H_n-\frac32\Big)-(n-2) \notag\\
&=(n+2)H_n-\frac{5n}{2}-\frac{1}{2}.
\end{align}						
For $n=1,2,3,4,\dots$ we get the values $0,\frac{1}{2},\frac{7}{6},
2,\dots$, which checks. Experiments with permutations of up
to 100 elements checked as well.

Knuth sketches this variation already in his original paper \cite{Knuth72}.
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 $\kK$ are analogous; for completeness we give
its definition
\begin{equation}\label{def_kappafb1}   
\kK=\#\{(i,j)\mid 1 \le i\le j\le n,\quad q_i \le q_{i+1},\dots, q_i \le q_j
\textbf{\ and  } q_i\le q_1\}
\end{equation}
 and get
\begin{equation*}
   \mathbb{E}(\kK) = \sum_{1 \le j \le n} \frac{1}{j} 
   + \sum_{1 \le i \le j \le n} \frac{1}{j-i+2},
\end{equation*}
which gives
\begin{equation}
   \mathbb{E}(\kK) = (n+2) H_{n} - 2n.
\end{equation}

\medskip

Next we also sketch the computation of the variances $\mathbb{V}(\aK)$ resp. $\mathbb{V}(\kK)$.
The second moment $\mathbb{E}\big((\aK)^{2}\big)$ for Knuth's parameter $a$ is given by
\begin{equation*}
   \mathbb{E}\big((\aK)^{2}\big) = \mathbb{E}(\aK) + \sum_{
   \shortstack[c]{$\scriptstyle{1 \le i_{1} < j_{1} \le n,}$ \\
   $\scriptstyle{1 \le i_{2} < j_{2} \le n,}$ \\ $\scriptstyle{(i_{1},j_{1}) \neq (i_{2}, j_{2})}$}} 
   \mathbb{E}\big(y_{i_{1}j_{1}}^{\textrm{[FB1]}} y_{i_{2}j_{2}}^{\textrm{[FB1]}}\big),
\end{equation*} 
and by considering all possible cases we get
\begin{align*}
   \mathbb{E}\big((\aK)^{2}\big) & = (n+2)H_n-\frac{5n}{2}-\frac{1}{2} \\*
   & \mbox{} + 2 \sum_{2 \le i_{1} < j_{1} < i_{2} < j_{2} \le n}
   \frac{1}{j_{1}-i_{1}+j_{2}-i_{2}+3} \left(\frac{1}{j_{2}-i_{2}+2}+\frac{1}{j_{1}-i_{1}+2}\right) \\
   & \mbox{} + 2 \sum_{2 \le i_{1} < i_{2} < j_{2} \le j_{1} \le n}
   \frac{1}{(j_{1}-i_{1}+2) (j_{2}-i_{2}+2)} \\
   & \mbox{} + 2 \sum_{2 \le i_{1} < i_{2} \le j_{1} < j_{2} \le n}
   \frac{1}{(j_{2}-i_{1}+2) (j_{2}-i_{2}+2)} 
   + 2 \sum_{2 \le i < j_{1} < j_{2} \le n}
   \frac{1}{j_{2}-i+2} \\
   & \mbox{} + 2 \sum_{2 \le j_{1} < i < j_{2} \le n}
   \frac{1}{(j_{2}-i+j_{1}+1) j_{1}}
   + 2 \sum_{2 \le j_{1} < j_{2} \le n}
   \frac{1}{j_{2}}.
\end{align*}
(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 \le i_{1} < i_{2} \le j_{1} < j_{2} \le n$ and describe 
how to compute the quantity
$\mathbb{E}\big(y_{i_{1}j_{1}}^{\textrm{[FB1]}} y_{i_{2}j_{2}}^{\textrm{[FB1]}}\big)
= \mathbb{P}\big\{y_{i_{1}j_{1}}^{\textrm{[FB1]}} y_{i_{2}j_{2}}^{\textrm{[FB1]}}=1\big\}$
via
\begin{align*}
   & \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)}.
\end{align*}
All permutations with 
$y_{i_{1}j_{1}}^{\textrm{[FB1]}} y_{i_{2}j_{2}}^{\textrm{[FB1]}}=1$
can be obtained in this case in the following way: Choose from the given set $\{1, \dots, n\}$ 
exactly $j_{2}-i_{1}+2$ elements, which will be put 
into positions $i_{1}, \dots, 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, \dots, 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, \dots, 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:
\begin{align*}
   & \sum_{2 \le i_{1} < i_{2} \le j_{1} < j_{2} \le n}
   \frac{1}{(j_{2}-i_{1}+2) (j_{2}-i_{2}+2)} \\*
   & = \sum_{i_{1}=2}^{n-2} \sum_{i_{2}=i_{1}+1}^{n-1} \sum_{j_{2}=i_{2}+1}^{n}
   \sum_{j_{1}=i_{2}}^{j_{2}-1} \frac{1}{(j_{2}-i_{1}+2)(j_{2}-i_{2}+2)} \\
   & = \sum_{i_{1}=2}^{n-2} \sum_{j_{2}=i_{1}+2}^{n} \sum_{i_{2}=i_{1}+1}^{j_{2}-1}
   \frac{1}{j_{2}-i_{1}+2}\left(1-\frac{2}{j_{2}-i_{2}+2}\right) \\
   & = \sum_{i_{1}=2}^{n-2} \sum_{j_{2}=i_{1}+2}^{n} \frac{1}{j_{2}-i_{1}+2}
   \left(j_{2}-i_{1}-1-2\Big(H_{j_{2}-i_{1}+1}-\frac{3}{2}\Big)\right) \\
   & = \sum_{i_{1}=2}^{n-2} \sum_{j_{2}=i_{1}+2}^{n} 
   \left(1-2\frac{H_{j_{2}-i_{1}+2}}{j_{2}-i_{1}+2}+\frac{2}{(j_{2}-i_{1}+2)^{2}}\right) \\
   & = \sum_{i_{1}=2}^{n-2} \left(n-i_{1}-1-H_{n-i_{1}+2}^{2}-H_{n-i_{1}+2}^{(2)}
   + H_{3}^{2} + H_{3}^{(2)} + 2 H_{n-i_{1}+2}^{(2)}-2 H_{3}^{(2)}\right) \\
   & = \sum_{k=1}^{n-3} k - \sum_{k=4}^{n} H_{k}^{2} + \sum_{k=4}^{n} H_{k}^{(2)}
   + (H_{3}^{2}-H_{3}^{(2)}) (n-3) \\
   \begin{split}
   & = \frac{(n-3)(n-2)}{2} - (n+1) H_{n}^{2} + (2n+1) H_{n} - 2n + 4 H_{3}^{2}
   - 7 H_{3} + 6 \\
   & \quad \mbox{} + (n+1) H_{n}^{(2)} - H_{n} - 4 H_{3}^{(2)} + H_{3}
   + (n-3) (H_{3}^{2} - H_{3}^{(2)});
   \end{split}
\end{align*}
 we used here and for the remaining cases several identities involving 
harmonic numbers to simplify the   sums that occur. The identities in question are 
\begin{align*}
   \sum_{k=1}^{n} H_{k} & = (n+1) H_{n} - n, & \sum_{k=1}^{n} H_{k}^{(2)} & = (n+1) H_{n}^{(2)} - H_{n}, \\
   \sum_{k=1}^{n} \frac{H_{k}}{k} & = \frac{1}{2}(H_{n}^{2}+ H_{n}^{(2)}), &  \sum_{k=1}^{n} k H_{k} & = \frac{n (n+1)}{2} H_{n} - \frac{n (n-1)}{2}, \\
   \sum_{k=1}^{n} H_{k}^{2} & = (n+1) H_{n}^{2} - (2n+1) H_{n} + 2n.
   \end{align*}
%
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
\begin{equation*}
\sum_{n\ge1}H_nz^n=\frac1{1-z}\log\frac1{1-z};
\end{equation*}
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 $\Sigma$, see
\cite{Schneider01}.


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 $\mathbb{V}(\aK) = 
\mathbb{E}\big((\aK)^{2}\big)-\big(\mathbb{E}(\aK)\big)^{2}$ is given by
\begin{equation}
   \mathbb{V}(\aK) = -(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},
\end{equation}
and asymptotically by
\begin{equation}
   \mathbb{V}(\aK) = \Big(\frac{31}{12} - \frac{\pi^{2}}{6}\Big) n^{2} + \mathcal{O}(n \log^{2} n).
\end{equation}

Analogous computations give the variance $\mathbb{V}(\kK)$:
\begin{equation}
   \mathbb{V}(\kK) = -(2n+3) H_{n}^{2} - (n+1)^{2} H_{n}^{(2)} + (n-4) H_{n} 
   + 3n(n+3),
\end{equation}
and asymptotically
\begin{equation}
   \mathbb{V}(\kK) = \Big(3 - \frac{\pi^{2}}{6}\Big) n^{2} + \mathcal{O}(n \log^{2} n).
\end{equation}

\section{Analysis of Keller's heuristic 2}

Heuristic 2 for cycle leader checking (called \texttt{Fastbreak~2}) 
is described by Keller as follows:\\
\emph{If only $r$ elements have not been visited yet by function
\texttt{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 \texttt{PermuteCycle}, the cycle hence has
already been permuted, and $i$ cannot be a leader.}

\medskip

An implementation of this heuristic~2 was given by Keller (see \cite[Fig.~4]{Keller02}),
and is here also given as Algorithm~\ref{alg2}.
\begin{algorithm}\label{fig6}
  \caption{Keller's cycle leader checking algorithm from \cite{Keller02} for heuristic 2.
\label{alg2}}
  \begin{algorithmic}
    \REQUIRE $\pi = (\pi(1), \dots, \pi(n))$ permutation of length $n$, \\
    $1 \le i \le n$, 
    $0 \le \textrm{remaining} \le n$ integers.
    \ENSURE $\textrm{leader} \in \{\textrm{true},\textrm{false}\}$, $\textrm{leader}=\textrm{true}$
     iff $i$ is a cycle leader.% and $\textrm{leader}=\textrm{false}$ otherwise.
   
    \STATE $j \assign i$
	\STATE $\textrm{leader} \assign \textrm{true}$
    \STATE $\textrm{steps} \assign 0$
    
    \REPEAT 
       \STATE $j \assign \pi(j)$
       \STATE $\textrm{steps} \assign \textrm{steps}+1$
       \IF{($j<i$) \OR ($\textrm{steps} > \textrm{remaining}$)}
         \STATE $\textrm{leader} \assign \textrm{false}$
		 \STATE $\textbf{break}$
       \ENDIF
    \UNTIL{$j = i$}
    \STATE $\textbf{return} \; \textrm{leader}$
  \end{algorithmic}
\end{algorithm}

It should be remarked that this 
\emph{implementation\/} of heuristic~2 does \emph{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 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 \emph{modified\/} cycle leader checking algorithm, 
which uses this principle is given as Algorithm~\ref{alg3}.
It is assumed, that each implementation (Algorithm~\ref{alg2} or Algorithm~\ref{alg3})
is used together with the permutation algorithm given in \cite[Fig.~3]{Keller02}.
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 \texttt{C} as well since
all algorithms given by Keller are implemented in \texttt{C}.
These versions can be obtained from the authors. We replaced
Keller's ``\texttt{TestHypo(j,i)}'' by ``$j \ge i$''
since that is exactly what it is.
Our average-case analysis is based on this improved implementation.

\begin{algorithm}\label{fig4}
  \caption{Keller's cycle leader checking algorithm from \cite{Keller02} for heuristic 2 
  with improvement as discussed in the text.
\label{alg3}}
  \begin{algorithmic}
    \REQUIRE $\pi = (\pi(1), \dots, \pi(n))$ permutation of length $n$, \\
    $1 \le i \le n$, 
    $0 \le \textrm{remaining} \le n$ integers.
    \ENSURE $\textrm{leader} \in \{\textrm{true},\textrm{false}\}$, $\textrm{leader}=\textrm{true}$
     iff $i$ is a cycle leader.% and $\textrm{leader}=\textrm{false}$ otherwise.
   
    \STATE $\textrm{leader} \assign \textrm{true}$
	\STATE $j \assign \pi(i)$
	\STATE $\textrm{steps} \assign 1$
        
    \WHILE{($j > i$) \AND ($\textrm{steps} < \textrm{remaining}$)}{
       \STATE $j \assign \pi(j)$
	   \STATE $\textrm{steps} \assign \textrm{steps}+1$}
    \ENDWHILE
    \IF{$j \neq i$} \STATE $\textrm{leader} \assign \textrm{false}$ \ENDIF
    \STATE $\textbf{return} \; \textrm{leader}$
  \end{algorithmic}
\end{algorithm}

In Keller's implementation of heuristic~2 as given by Algorithm~\ref{alg2}, 
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~\ref{alg3} requires here $6$ function calls whereas 
Algorithm~\ref{alg2} requires $7$ function call.
Since all the experimental results in \cite{Keller02} are given for 
his implementation, we briefly analyze this version also. 

\medskip

Now we come to the average-case analysis of the algorithm with heuristic~2 as 
implemented by Algorithm~\ref{alg3}. We  first
study  the parameter $\kappa$ (the number of function
calls)  in  detail, showing how to compute $\mathbb{E}(\kk)$. 

For Knuth's parameter $a$ (the number of passes of the {\texttt{while}}-loop),
we only give the formula for the expectation and omit
the analogous computations to produce $\mathbb{E}(\ak)$. 


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~\ref{alg2}. We will also obtain a formula for $\mathbb{E}(\kt)$. 

If $q_{1} \dots q_{n}$ is the 
(canonical) cycle representation of a given permutation $\pi$ of length $n$,
then we get the following number $\kk$ of function calls:
\begin{multline}\label{def_kappafb2}
 \kk = \#\bigg\{(i,j)\: \big\vert \:1 \le i \le j \le n, \, \left(q_{i} \le q_{i+1}, q_{i} \le q_{i+2}, \dots, 
   q_{i} \le q_{j}\right) \textbf{ and } \\*
 \Big[\Big(j-i+2 \le \min_{k<i}\left\{k \: | \: q_{k}<q_{i} \textbf{ and } q_{1}>q_{i}, \dots,
   q_{k-1}>q_{i}\right\}\Big)\\*
 \textbf{ or } \left(q_{1}>q_{i}, \dots, q_{i-1}>q_{i}
    \Big)\right]\bigg\}.
\end{multline}

%\newpage

\noindent
Then a first formula for the
 expected value $\mathbb{E}(\kk)$ of this parameter is given by the
following expression:
\begin{align}
   \mathbb{E}(\kk)  &= \sum_{1 \le i \le j \le n} \frac{1}{n!} \sum_{L=1}^{n} 
      \Bigg[ 
   \binom{n-L}{j-1} (j-1)! (n-j)!   \label{eqn2} \\*
  &+ \sum_{k=j-i+2}^{i-1} \binom{n-L}{j-i+k-1} (j-i+k-1)! (L-1)
   (n-k-(j-i)-1)! \Bigg]. \notag
\end{align}
It is obtained by summing up  the expectations of the indicator variable which is
true iff
the function call $\pi(q_{j})$ is made when testing $q_{i}$ as a possible cycle leader
for $1 \le i \le j \le 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}, \dots, q_{j}>q_{i}$ and either
$q_{i}$ is actually a cycle leader ($q_{1}>q_{i}, \dots, 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} \textbf{ and } q_{1}>q_{i}, \dots, q_{k-1}>q_{i}$). 
If one distinguishes the possible 
values of $L:=q_{i}$ the formula \eqref{eqn2} follows.

In the following we want to get a closed formula for the expression \eqref{eqn2}.
We consider first the simpler part of this expression and get
\begin{align*}
   & \sum_{i=1}^{n} \sum_{j=i}^{n} \frac{1}{n!} \sum_{L=1}^{n} \binom{n-L}{j-1} (j-1)! (n-j)!
   = \frac{1}{n} \sum_{i=1}^{n} \sum_{j=i}^{n} \frac{1}{\binom{n-1}{j-1}}
   \sum_{L=1}^{n} \binom{n-L}{j-1} \\
   & = \frac{1}{n} \sum_{i=1}^{n} \sum_{j=i}^{n}
   \frac{\binom{n}{j}}{\binom{n-1}{j-1}} = \sum_{i=1}^{n} \sum_{j=i}^{n} \frac{1}{j}
   = \sum_{j=1}^{n} \frac{1}{j} \sum_{i=1}^{j} 1 = n.
\end{align*}
%
For the other part of expression \eqref{eqn2} we get first
\begin{align*}
   & \sum_{i=1}^{n} \sum_{j=i}^{n} \frac{1}{n!} \sum_{L=1}^{n} \sum_{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)} \sum_{i=1}^{n} \sum_{j=i}^{n} \sum_{k=j-i+2}^{i-1} 
   \frac{1}{\binom{n-2}{j-i+k-1}} \sum_{L=1}^{n} \binom{n-L}{j-i+k-1} (L-1) \\
   & = \frac{1}{n-1} \sum_{i=1}^{n} \sum_{j=i}^{n} \sum_{k=j-i+2}^{i-1}
   \frac{1}{\binom{n-2}{j-i+k-1}} \sum_{L=1}^{n} \binom{n-L}{j-i+k-1} \\
   & \quad \mbox{} - \frac{1}{n} \sum_{i=1}^{n} \sum_{j=i}^{n} \sum_{k=j-i+2}^{i-1}
   \frac{1}{\binom{n-1}{j-i+k}} \sum_{L=1}^{n} \binom{n-L+1}{j-i+k} \\
   & = \frac{1}{n-1} \sum_{i=1}^{n} \sum_{j=i}^{n} \sum_{k=j-i+2}^{i-1}
   \frac{\binom{n}{j-i+k}}{\binom{n-2}{j-i+k-1}} 
   - \frac{1}{n} \sum_{i=1}^{n} \sum_{j=i}^{n} \sum_{k=j-i+2}^{i-1}
   \frac{\binom{n+1}{j-i+k+1}}{\binom{n-1}{j-i+k}} \\
   & = \sum_{i=1}^{n} \sum_{j=i}^{n} \sum_{k=j-i+2}^{i-1}
   \left(\frac{n}{(j-i+k)(n-(j-i)-k)} - \frac{n+1}{(j-i+k+1)(n-(j-i)-k)}\right) \\
   & = \sum_{i=1}^{n} \sum_{l=0}^{n-i} \sum_{k=l+2}^{i-1} 
   \left(\frac{1}{l+k} - \frac{1}{l+k+1}\right)
   = \sum_{i=3}^{n} \sum_{l=0}^{\min(i-3,n-i)} \sum_{k=l+2}^{i-1} 
   \left(\frac{1}{l+k} - \frac{1}{l+k+1}\right) \\
   & = \sum_{i=3}^{n} \sum_{l=0}^{\min(i-3,n-i)} \left(\frac{1}{2l+2}-\frac{1}{l+i}\right).
\end{align*}
%
This sum can be further simplified to
\begin{align*}
   & \sum_{i=3}^{n} \sum_{l=0}^{\min(i-3,n-i)} \left(\frac{1}{2l+2}-\frac{1}{l+i}\right)
   = \sum_{l=0}^{\lfloor\frac{n+1}{2}\rfloor-2} \sum_{i=l+3}^{n-l}
   \left(\frac{1}{2l+2} - \frac{1}{l+i}\right) \\
   & = \sum_{l=0}^{\lfloor\frac{n+1}{2}\rfloor-2} \left(\frac{n}{2l+2} -1 -H_{n}
   + H_{2l+2}\right) \\
   & = \Big(\Big\lfloor\frac{n-1}{2}\Big\rfloor+\frac{1}{2}\Big)
 H_{2\lfloor\frac{n-1}{2}\rfloor}
   + \Big(\frac{n}{2}+\frac{1}{4}\Big) H_{\lfloor\frac{n-1}{2}\rfloor}
   - \Big\lfloor\frac{n-1}{2}\Big\rfloor H_{n} 
   - 2 \Big\lfloor\frac{n-1}{2}\Big\rfloor,
\end{align*}
where we used 
\begin{equation*}
\sum_{k=1}^{n}H_{2k}=\Big(n+\frac{1}{2}\Big)H_{2n}+\frac{1}{4}H_n-n.
\end{equation*}
%
Adding both parts, we get for the expected number $\mathbb{E}(\kk)$ of function calls
\begin{align*}
   \mathbb{E}(\kk) & = 
   \Big(\Big\lfloor\frac{n-1}{2}\Big\rfloor+\frac{1}{2}\Big) H_{2\lfloor\frac{n-1}{2}\rfloor}
   + \Big(\frac{n}{2}+\frac{1}{4}\Big) H_{\lfloor\frac{n-1}{2}\rfloor}
   - \Big\lfloor\frac{n-1}{2}\Big\rfloor H_{n} \\
   & \quad \mbox{} - 2 \Big\lfloor\frac{n-1}{2}\Big\rfloor + n.
\end{align*}
It can also be written as
\begin{equation}
   \mathbb{E}(\kk) = \Big(\Big\lfloor\frac{n}{2}\Big\rfloor+\frac{1}{4}\Big)
   H_{\lfloor\frac{n}{2}\rfloor} + \frac{1}{2} H_{n} 
   + \frac{1}{2} \left(\Big\lceil\frac{n}{2}\Big\rceil
   -\Big\lfloor\frac{n}{2}\Big\rfloor\right) \big(H_{\lfloor\frac{n}{2}\rfloor}+1\big),
\end{equation}
and is asymptotically given by
\begin{equation}
   \mathbb{E}(\kk) = \frac{1}{2} n \log n + \mathcal{O}(n).
\end{equation}

\medskip

For Knuth's parameter $\ak$, defined by
\begin{multline}\label{def_afb2}
 \ak = \#\bigg\{(i,j)\: \big\vert \:1 \le i < j \le n, \, 
 \left(q_{i} < q_{i+1}, q_{i} < q_{i+2}, \dots, 
   q_{i} < q_{j}\right) \textbf{ and } \\*
 \Big[\Big(j-i+2 \le \min_{k<i}\left\{k \: | \: q_{k}<q_{i} \textbf{ and } q_{1}>q_{i}, \dots,
   q_{k-1}>q_{i}\right\}\Big)\\*
 \textbf{ or } \left(q_{1}>q_{i}, \dots, q_{i-1}>q_{i}
    \Big)\right]\bigg\},
\end{multline}
 we get in the same style the expectation
\begin{equation}
   \mathbb{E}(\ak) = \frac{2n+1}{4} H_{\lfloor\frac{n+1}{2}\rfloor} 
   + \frac{1}{2} H_{2\lfloor\frac{n+1}{2}\rfloor} 
   - \frac{1}{2} \Big(\Big\lfloor\frac{n+1}{2}\Big\rfloor - 
            \Big\lfloor\frac{n}{2}\Big\rfloor\Big) 
   - \frac{n+1}{2}.
\end{equation}

\medskip

In Keller's implementation of heuristic~2, the number $\kt$ of function calls for
 a given permutation $\pi$ of length $n$ can be described by
\begin{multline}\label{def_kappatildafb2}
    \kt = \#\bigg\{(i,j) \: \big| \: 1 \le i < j \le n, \, \left(q_{i} < q_{i+1}, q_{i} < q_{i+2}, \dots, 
   q_{i} < q_{j}\right) \textbf{ and } \\
    \Big[\Big(j-i+1 \le \min_{k<i}\left\{k \: | \: q_{k}<q_{i} \textbf{ and } q_{1}>q_{i}, \dots,
   q_{k-1}>q_{i}\right\}\Big) \\
\textbf{ or } \left(q_{1}>q_{i}, \dots, q_{i-1}>q_{i}\right)\Big]\bigg\} 
 + \#\left\{i \: | \: q_{i} \le q_{1}\right\}.
\end{multline}
The expected value $\mathbb{E}(\kt)$ is then given 
by the following expression:
\begin{align}
   \mathbb{E}(\kt) & = \sum_{1 \le i < j \le n} \frac{1}{n!} \sum_{L=1}^{n} \left[ 
   \binom{n-L}{j-1} (j-1)! (n-j)!  \right. \notag \\
   & \left. + \sum_{k=j-i+1}^{i-1} \binom{n-L}{j-i+k-1} (j-i+k-1)! (L-1)
   (n-k-(j-i)-1)! \right] \notag \\
   &  + \frac{1}{2}(n-1)+1.\label{eqn3}
\end{align}
%
One computes
\begin{align*}
   & \sum_{i=1}^{n} \sum_{j=i+1}^{n} \frac{1}{n!} \sum_{L=1}^{n} \binom{n-L}{j-1} (j-1)! (n-j)!
   = n-H_{n}, \\
   & \sum_{i=1}^{n} \sum_{j=i+1}^{n} \frac{1}{n!} \sum_{L=1}^{n} \sum_{k=j-i+1}^{i-1}
   \binom{n-L}{j-i+k-1} (j-i+k-1)! (L-1) (n-k-(j-i)-1)! \\ 
   & \quad = \sum_{i=2}^{n} \sum_{l=1}^{\min(i-2,n-i)} \left(\frac{1}{2l+1}-\frac{1}{l+i}\right)
   = \sum_{l=1}^{\lfloor\frac{n}{2}\rfloor-1}\sum_{i=l+2}^{n-l} \left(\frac{1}{2l+1}-\frac{1}{l+i}\right) \\
   & \quad \overset{n > 1}{=} \Big(n+\Big\lfloor\frac{n}{2}\Big\rfloor 
+ \frac{1}{2}\Big) H_{2\lfloor\frac{n}{2}\rfloor-1}
   -\Big(\frac{n}{2}+\frac{1}{4}\Big) H_{\lfloor\frac{n}{2}\rfloor-1} 
   - \Big(\Big\lfloor\frac{n}{2}\Big\rfloor-1\Big) H_{n} 
-2 \Big\lfloor\frac{n}{2}\Big\rfloor -n + \frac{1}{2},
\end{align*}
where we used for the last equation the formula
\begin{equation*}
   \sum_{k=0}^{n} H_{2k+1} = \Big(n+\frac{3}{2}\Big) H_{2n+1} 
       -n - \frac{1}{2} - \frac{1}{4} H_{n}.
\end{equation*}
Adding all parts, one gets a formula for $\mathbb{E}(\kt)$, which can be simplified to
\begin{equation}
   \mathbb{E}(\kt) = \frac{1}{2} (n+1) H_{n} - \frac{n}{2} + \frac{1}{2} + \frac{n}{2}
   H_{2\lfloor\frac{n}{2}\rfloor} - \Big(\frac{n}{2}+\frac{1}{4}\Big)
        H_{\lfloor\frac{n}{2}\rfloor},
\end{equation}
and is asymptotically again given by
\begin{equation}
   \mathbb{E}(\kt) = \frac{1}{2} n \log n + \mathcal{O}(n).
\end{equation}

\section{Experimental results compared to the mathematical formul{\ae}}

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}, \dots, 2^{20}$ with the \texttt{randperm} function of the \texttt{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 \ref{fig1}, \ref{fig2} and \ref{fig3} 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{\ae} $\kappa$, $\kK$, $\kk$ resp. $\kt$. 
\begin{figure}[h]
\epsfig{file=savpl1.eps, height=6cm}
\caption{Expected savings of function calls with heuristic 1.\label{fig1}}
\end{figure}
\begin{figure}[h]
\epsfig{file=savpl2.eps, height=6cm}
\caption{Expected savings of function calls with heuristic 2 (implementation presented in this paper).\label{fig2}}
\end{figure}
\begin{figure}[h]
\epsfig{file=savpl3.eps, height=6cm}
\caption{Expected savings of function calls with heuristic 2 (Keller's implementation).\label{fig3}}
\end{figure}

\clearpage

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

\bigskip

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

\begin{small}

\begin{figure}[h]
\renewcommand{\arraystretch}{2}
\begin{tabular}{|c|c|c|c|c|}
\hline
 quantity 
&name&def.  & exact formula& asympt.\\
\hline\hline
Knuth's parameter ``$a$''&
$a$&(\ref{def_a})&$(n+1)H_n-2n$&$n\log n$\\
\hline
Keller's version ``$\kappa$''&
$\kappa$&(\ref{def_keller})&$(n+1)H_n-n$&$n\log n$\\
\hline\hline
``$a$'' with \texttt{Fastbreak 1}&
$a^{[\textrm{FB1}]}$&
(\ref{def_afb1})
&$(n+2)H_n-\frac{5n}{2}-\frac12$&$n\log n$\\
\hline
``$\kappa$'' with \texttt{Fastbreak 1}&
$\kappa^{[\textrm{FB1}]}$&(\ref{def_kappafb1})&$(n+2)H_n-2n$&$n\log n$\\
\hline\hline
``$a$'' with \texttt{Fastbreak 2}&
$a^{[\textrm{FB2}]}$&(\ref{def_afb2})&$\frac{2n+1}{4} H_{\lfloor\frac{n+1}{2}\rfloor} 
   + \frac{1}{2} H_{2\lfloor\frac{n+1}{2}\rfloor}$ &$\frac12n\log n$
 \\
&&&$   - \frac{1}{2} (\lfloor\frac{n+1}{2}\rfloor -\lfloor\frac{n}{2}\rfloor) 
   - \frac{n+1}{2}$&\\
\hline
``$\kappa$'' with \texttt{Fastbreak 2}&
$\kappa^{[\textrm{FB2}]}$&(\ref{def_kappafb2})&$
(\lfloor\frac{n}{2}\rfloor+\frac{1}{4})
   H_{\lfloor\frac{n}{2}\rfloor} + \frac{1}{2} H_{n} 
$ &$\frac12n\log n$ \\
&&&$   + \frac{1}{2} (\lceil\frac{n}{2}\rceil
   -\lfloor\frac{n}{2}\rfloor) (H_{\lfloor\frac{n}{2}\rfloor}+1)
 $&\\
\hline
Keller's implementation &
$\tilde\kappa^{[\textrm{FB2}]}$&(\ref{def_kappatildafb2})&$
(n+\lfloor\frac{n}{2}\rfloor 
+ \frac{1}{2}) H_{2\lfloor\frac{n}{2}\rfloor-1}
      $ &$\frac12n\log n$ \\
of ``$\kappa$'' with \texttt{Fastbreak 2}&&&$ 
 -(\frac{n}{2}+\frac{1}{4}) H_{\lfloor\frac{n}{2}\rfloor-1} 
- (\lfloor\frac{n}{2}\rfloor-1) H_{n} 
$&\\
&&&$ 
-2 \lfloor\frac{n}{2}\rfloor -n + \frac{1}{2}
$&\\
\hline


\end{tabular}
\caption{The averages of the parameters studied in this paper.}
\end{figure}

\end{small}



\bigskip



\textbf{Acknowledgment.} The  comments of two referees helped
to improve the presentation.


%\newpage

\bibliographystyle{amsplain}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{1}

\bibitem{FiMuPo95}
F.~E.~Fich, J.~I.~Munro, and P.~V.~Poblete, 
\emph{Permuting in place}, SIAM Journal on Computing \textbf{24} (1995), 266--278.

\bibitem{HwNe02}
{H.-K.~Hwang} and R.~Neininger, \emph{Phase change of limit laws in the quicksort recurrence
under varying toll functions}, SIAM Journal on Computing \textbf{31} (2002), 1687--1722.

\bibitem{Keller02}
J.~Keller, \emph{A heuristic to accelerate in--situ permutation algorithms},
  Information Processing Letters \textbf{81} (2002), 119--125.

\bibitem{KiPrTi87}
P.~Kirschenhofer, {H.~ {P}rodinger}, and R.~F. Tichy, \emph{A contribution to
  the analysis of in situ permutation}, Glasnik Mathematicki \textbf{22(42)}
  (1987), 269--278.

\bibitem{Knuth72}
D.~E. Knuth, \emph{Mathematical analysis of algorithms}, Information Processing
  71, North Holland Publishing Company, 1972, Proceedings of IFIP Congress,
  Ljubljana, 1971, pp.~19--27.
Reprinted in: \emph{Selected papers on analysis of algorithms}, CSLI Publications, Stanford, CA, 2000.





\bibitem{Prodinger99}
H.~Prodinger, \emph{Combinatorics of geometrically distributed random
  variables: {I}nversions and a parameter of {K}nuth}, 
Annals of Combinatorics \textbf{5} (2001), 241--250.

\bibitem{Schneider01}
C.~Schneider, \emph{Symbolic summation in difference fields}, PhD~thesis, Univ.~Linz, 2001.


\bibitem{SeFl96}
R.~Sedgewick and P.~Flajolet, \emph{An introduction to the analysis of
  algorithms}, Addison-Wesley, 1996.

\end{thebibliography}

%\bibliography{C:/texfiles/pro_bib}


\end{document}
