# Strictly In-Place Algorithms for Permuting and Inverting Permutations

Bartłomiej Dudek  Institute of Computer Science, University of Wrocław, Poland
<EMAIL_ADDRESS>Paweł Gawrychowski
Institute of Computer Science, University of Wrocław, Poland
<EMAIL_ADDRESS>Karol Pokorski  Institute of
Computer Science, University of Wrocław, Poland
<EMAIL_ADDRESS>
###### Abstract

We revisit the problem of permuting an array of length $n$ according to a
given permutation in place, that is, using only a small number of bits of
extra storage. Fich, Munro and Poblete [FOCS 1990, SICOMP 1995] obtained an
elegant $\mathcal{O}(n\log n)$-time algorithm using only
$\mathcal{O}(\log^{2}n)$ bits of extra space for this basic problem by
designing a procedure that scans the permutation and outputs exactly one
element from each of its cycles. However, in the strict sense in place should
be understood as using only an asymptotically optimal $\mathcal{O}(\log n)$
bits of extra space, or storing a constant number of indices. The problem of
permuting in this version is, in fact, a well-known interview question, with
the expected solution being a quadratic-time algorithm. Surprisingly, no
faster algorithm seems to be known in the literature.

Our first contribution is a strictly in-place generalisation of the method of
Fich et al. that works in $\mathcal{O}_{\varepsilon}(n^{1+\varepsilon})$ time,
for any $\varepsilon>0$. Then, we build on this generalisation to obtain a
strictly in-place algorithm for inverting a given permutation on $n$ elements
working in the same complexity. This is a significant improvement on a recent
result of Guśpiel [arXiv 2019], who designed an $\mathcal{O}(n^{1.5})$-time
algorithm.

##  1 Introduction

Permutations are often used as building blocks in combinatorial algorithms
operating on more complex objects. This brings the need for being able to
efficiently operate on permutations. One of the most fundamental operations is
rearranging an array $A[1..n]$ according to a permutation $\pi$. This can be
used, for example, to transpose a rectangular array [23, Ex. 1.3.3-12].
Denoting by $a_{i}$ the value stored in $A[i]$, the goal is to make every
$A[i]=a_{\pi^{-1}(i)}$. This is trivial if we can allocate a temporary array
$B[1..n]$ and, after setting $B[i]\leftarrow A[\pi(i)]$ for every $i$, copy
$B[1..n]$ to $A[1..n]$. Alternatively, one can iterate over the cycles of
$\pi$ and rearrange the values on each cycle. Then there is no need for
allocating a temporary array as long as we can recognise the elements of $\pi$
in already processed cycles. This is easy if we can overwrite $\pi$, say by
setting $\pi(i)\leftarrow i$ after having processed $\pi(i)$. However, we
might want to use the same $\pi$ later, and thus cannot overwrite its
elements. In such a case, assuming that every $\pi(i)$ can store at least one
extra bit, we could mark the processed elements by temporarily setting
$\pi(i)\leftarrow-\pi(i)$, and after having rearranged the array restoring the
original $\pi$. Even though this reduces the extra space to just one bit per
element, this might be still too much, and $\pi(i)$ might be not stored
explicitly but computed on-the-fly, as in the example of transposing a
rectangular array. This motivates the challenge of designing an efficient
algorithm that only assumes access to $\pi$ through an oracle and uses a small
number of bits of extra storage.

Designing a fast algorithm that permutes $A[1..n]$ given oracle access to
$\pi$ and using only a little extra storage is a known interview puzzle [1,
Sec. 6.9]. The expected solution is a quadratic-time algorithm that identifies
the cycles of $\pi$ by iterating over $i=1,2,\ldots,n$ and checking if $i$ is
the smallest on its cycle in $\pi$. Having identified such $i$, we permute the
values $A[i],A[\pi(i)],A[\pi^{2}(i)],\ldots$. This uses only a constant number
of auxiliary variables, or $\mathcal{O}(\log n)$ bits of additional space,
which is asymptotically optimal as we need to be able to specify an index
consisting of $\lceil\log n\rceil$ bits. However, its worst-case running time
is quadratic. Designing a faster solution is nontrivial, but Fich, Munro and
Poblete obtained an elegant $\mathcal{O}(n\log n)$-time algorithm using only
$\mathcal{O}(\log^{2}n)$ bits of extra space [12]. Their approach is also
based on identifying the cycles of $\pi$. This is implemented by scanning the
elements $i=1,2,\ldots,n$ while testing if the current $i$ is the leader on
its cycle, designating exactly one element on every cycle to be its leader. We
call this a cycle leaders procedure. Due to the unidirectional nature of the
input, the test must be implemented by considering the elements
$i,\pi(i),\pi^{2}(i),\ldots$ until we can conclude if $i$ is the leader of its
cycle. The main contribution of Fich et al. is an appropriate definition of a
leader that allows to implement such a test while storing only
$\mathcal{O}(\log n)$ indices and making the total number of accesses to $\pi$
only $\mathcal{O}(n\log n)$. They also show an algorithm running in
$\mathcal{O}(n^{2}/b)$ time and $b+\mathcal{O}(\log n)$ bits of space for
arbitrary $b\leq n$.

A procedure that transforms the input using only a small number of bits of
extra storage is usually referred to as an in-place algorithm. The allowed
extra space depends on the problem, but in the most strict form, this is
$\mathcal{O}(\log n)$ bits where $n$ is the size of the input. We call such a
procedure strictly in-place. This is related to the well-studied complexity
class $L$ capturing decision problems solvable by a deterministic Turing
machine with $\mathcal{O}(\log n)$ bits of additional writable space with
read-only access to the input. There is a large body of work concerned with
time-space tradeoffs assuming read-only random access to the input. Example
problems include: sorting and selection [5, 4, 26, 2, 24, 16, 25, 28, 6, 7],
constructing the convex hull [8], multiple pattern matching [13] or
constructing the sparse suffix array [17, 3].

This raises the question: is there a deterministic subquadratic strictly in-
place algorithm for permuting an array? We provide an affirmative answer to
this question by designing, for every $\varepsilon>0$, a strictly in-place
algorithm for this problem that works in
$\mathcal{O}_{\varepsilon}(n^{1+\varepsilon})$ time. 111We write
$\mathcal{O}_{\varepsilon}(f(n))$ to emphasise that the hidden constant
depends on $\varepsilon$.

### Previous and related work.

Fich et al. [12] designed a cycle leaders algorithm that works in
$\mathcal{O}(n\log n)$ time and uses $\mathcal{O}(\log^{2}n)$ bits of extra
space. Given oracle access to both $\pi$ and $\pi^{-1}$, they also show a
simpler algorithm that needs only $\mathcal{O}(\log n)$ bits of extra space
and the same time. Both algorithms have interesting connections to leader
election in, respectively, unidirectional [9, 27] and bidirectional [20, 15]
rings. While in certain scenarios, such as $\pi$ being specified with an
explicit formula, one can assume access to both $\pi$ and $\pi^{-1}$, in the
general case this is known to significantly increase the necessary space [18].
For a random input, traversing the cycle from $i$ until we encounter a smaller
element takes in total $\mathcal{O}(n\log n)$ average time and uses only
$\mathcal{O}(\log n)$ bits of space [22]. Using hashing, one can also design
an algorithm using expected $\mathcal{O}(n\log n)$ time and $\mathcal{O}(\log
n)$ bits of space without any assumption on $\pi$ (interestingly, a different
application of randomisation is known to help in leader election in anonymous
unidirectional rings [21]). Better cycle leaders algorithms are known for some
specific permutations, such as the perfect shuffle [11].

An interesting related question is that of inverting a given permutation $\pi$
on $n$ elements. For example, it allows us to work with both the suffix array
and the inverse suffix array without explicitly storing both of them [14]. The
goal of this problem is to replace $\pi$ with its inverse $\pi^{-1}$
efficiently while using a small amount of extra space. El-Zein, Munro and
Robertson [10] solve this in $\mathcal{O}(n\log n)$ time using only
$\mathcal{O}(\log^{2}n)$ bits of extra space. The high-level idea of their
procedure is to identify cycle leaders and invert every cycle of $\pi$ at its
leader $i$. The difficulty in such an approach is that the leader $i^{\prime}$
of the inverted cycle might be encountered again, forcing the cycle to be
restored to its original state. El-Zein et al. deal with this hurdle by
temporarily lifting the restriction that $\pi$ is a permutation. Very
recently, Guśpiel [19] designed a strictly in-place algorithm for this problem
that works in $\mathcal{O}(n^{1.5})$ time. We stress that his approach does
not provide a subquadratic strictly in-place solution for identifying cycle
leaders, and so does not imply such an algorithm for permuting an array. See
Table 1 with the summary of previous work.

| Permuting | Inverting
---|---|---
Trivial | $(n,n)$
$(n^{2},\log n)$
With hashing222This approach runs in expected $\mathcal{O}(n\log n)$ time. | $(n\log n,\log n)$ | -
Fich et al. [12] | $(n^{2}/b,b+\log n)$ | -
$(n\log n,\log^{2}n)$ | -
El-Zein et al. [10] | - | $(n\log n,\log^{2}n)$
Guśpiel [19] | - | $(n^{1.5},\log n)$
This work333The constant in time and space complexity depends on $\varepsilon$. | $(n^{1+\varepsilon},\log n)$
Table 1: Comparison of different algorithms for in-place permuting and
inverting a permutation. $(f(n),g(n))$ denotes that the algorithm runs in
$\mathcal{O}(f(n))$ time and uses $\mathcal{O}(g(n))$ bits of space.

### Our contribution.

Building on the approach of Fich et al. we design, for every $\varepsilon>0$,
a cycle leaders algorithm that works in
$\mathcal{O}_{\varepsilon}(n^{1+\varepsilon})$ time and uses
$\mathcal{O}_{\varepsilon}(\log n)$ bits of extra space. This implies a
strictly in-place algorithm for permuting an array in
$\mathcal{O}_{\varepsilon}(n^{1+\varepsilon})$ time. In other words, we show
that by increasing the number of auxiliary variables to a larger constant we
can make the exponent in the running time arbitrarily close to 1. Then, we
apply our improved cycle leaders algorithm to obtain a solution for inverting
a given permutation in the same time and space. This significantly improves on
the recent result of Guśpiel [19].

### Techniques and roadmap.

The main high-level idea in Fich et al. is to work with local minima, defined
as the elements $i\in E_{1}=[n]$ of $\pi_{1}=\pi$ such that
$\pi^{-1}(i)>i<\pi(i)$. This is applied iteratively by defining a new
permutation $\pi_{2}$ on the set $E_{2}$ of local minima, and repeating the
same construction on $\pi_{2}$. After at most $t\leq\lfloor\log n\rfloor$
iterations, there is only the smallest element $m$ remaining and the leader is
chosen as the unique $i$ on the cycle such that
$\pi_{t}\circ\ldots\circ\pi_{1}(i)=m$. Checking if $i$ is a leader is done by
introducing the so-called _elbows_. For completeness, we provide a full
description of the algorithm in Appendix A. Compared to the original version,
we introduce new notation and change some implementation details to make the
subsequent modifications easier to state. The crucial point is that the extra
space used by the algorithm is bounded by a constant number of words per
iteration in the above definition. The natural approach for decreasing the
space to $\mathcal{O}(\log n)$ is to modify the definition of the local
minimum to decrease the number of iterations to a constant. To this end, we
work with $b$-local minima defined as elements less than all of their $b$
successors and predecessors, for $b=\lceil n^{\varepsilon}\rceil$ where
$\varepsilon$ is a sufficiently small constant. This decreases the number of
iterations to $\log n/\log b=1/\varepsilon=\mathcal{O}_{\varepsilon}(1)$.
There is, however, a nontrivial technical difficulty when trying to work with
this idea. In the original version, one can check $\pi_{r}(x)\in E_{r}$ should
be ’’promoted‘‘ to $E_{r+1}$ by explicitly maintaining $x,\pi_{r}(x)$ and
$\pi_{r}(\pi_{r}(x))$ and simply comparing $\pi_{r}(x)$ with $x$ and
$\pi_{r}(\pi_{r}(x))$. For larger values of $b$, this translates into
explicitly maintaining
$x,\pi_{r}(x),\pi_{r}(\pi_{r}(x)),\ldots,\pi_{r}^{2b}(x)$ to check if
$\pi_{r}^{b}(x)\in E_{r+1}$, which of course takes too much space. We overcome
this difficulty by designing and analysing a recursive pointer. This gives us
our cycle leaders algorithm described in Section 3.

Similarly as El-Zein et al. [10], we use our cycle leaders algorithm to design
a solution to the permutation inversion problem. The high-level idea is to
identify the leader $i$ of a cycle, and then invert the cycle by traversing it
from $i$. We need to somehow guarantee that the cycle is not inverted again,
but do not have enough extra space to store $j$. El-Zein et al. mark the
already inverted cycles that otherwise would be again inverted in the future
by converting them to paths, that is, changing some $\pi(x)$ to undefined.
This is then gradually repaired to a cycle, which requires a nontrivial
interleave of four different scans. Our starting point is a simplification of
their algorithm described in Appendix B based on encoding slightly more (but
still very little) information about the cycle. In Section 4 we further extend
this method to work with $b$-local minima.

##  2 Preliminaries

$[n]$ denotes the set of integers $\\{1,2,\ldots,n\\}$ and for a function $f$
and a nonnegative integer $k$ we define $f^{k}(x)$ to be $x$ when $k=0$ and
$f(f^{k-1}(x))$ otherwise. If $f$ is a permutation then $f^{-1}$ denotes its
inverse and we define $f^{-k}(x)$ to be $f^{-k}(x)=f^{-1}(f^{-k+1}(x))$ for
$k>0$. Throughout the paper $\log$ denotes $\log_{2}$.

In the cycle leaders problem, we assume that the permutation $\pi$ on $[n]$ is
given through an oracle that returns any $\pi(i)$ in constant time. The goal
is to identify exactly one element on each cycle of $\pi$ as a leader. All of
our algorithms follow the same left-to-right scheme: we consider the elements
$i=1,2,\ldots,n$ in this order and test if the current $i$ is the leader of
its cycle by considering the elements $i,\pi(i),\pi^{2}(i),\ldots$ until we
can determine if $i$ is a leader.

1:for $i=1..n$ do $\textsc{Process}(i)$

Algorithm 1 A general framework of left-to-right algorithms.

Whenever we refer to a range $x\ldots y$, we mean
$x,\pi(x),\pi(\pi(x)),\dots,y$. We will also consider ranges $x\ldots y$
longer than a full cycle, but in such cases there will be always an middle
point $z$ (clear from the context) such that $x\ldots y$ consists of two
ranges $x\ldots z$ and $z\ldots y$, each shorter than a full cycle. For
example, in the range $\pi^{-k}(x)\ldots\pi^{k}(x)$ there are elements from
$\pi^{-k}(x)\ldots x$ and from $x\ldots\pi^{k}(x)$. We use
$\ell(i,i^{\prime})$ to denote $\min\\{k>0:\pi^{k}(i)=i^{\prime}\\}$.
$\textsc{MinRange}(a,b)$ naively finds the minimum between $a$ and $b$ on the
same cycle of $\pi$, that is, $\min\\{a,\pi(a),\pi^{2}(a),\ldots,b\\}$. If
$a=b$, we assume it computes the minimum of the full cycle of $a$. We also
create ternary MinRange as follows:
$\textsc{MinRange}(x,y,z)=\min(\textsc{MinRange}(x,y),\textsc{MinRange}(y,z))$.
Using this notation, the naive cycle leaders algorithm is presented in
Algorithm 2.

1:function Process($i$)

2: if $i=\textsc{MinRange}(i,i)$ then Report that $i$ is a leader.

Algorithm 2 A naive cycle leaders algorithm.

When inverting $\pi$, we assume constant-time random access to the input. Due
to the final goal being replacing every $\pi(i)$ with $\pi^{-1}(i)$, we allow
temporarily overwriting $\pi(i)$ with any value from $[n]$ as long as after
the algorithm terminates the input is overwritten as required. Additional
space used by our algorithms consists of a number of auxiliary variables
called words, each capable of storing a single integer from $[n]$. We assume
that basic operations on such variables take constant time. We assume that the
value of $n$ is known to the algorithm.

##  3 Leader election in smaller space

In this section, we extend the algorithm of Fich et al. [12] to obtain, for
any $\varepsilon>0$, a solution to the cycle leaders problem in
$\mathcal{O}_{\varepsilon}(n^{1+\varepsilon})$ time and using
$\mathcal{O}_{\varepsilon}(\log n)$ bits of extra space.

Let $E_{1}=[n]$ and $\pi_{1}=\pi$. We denote by $b=\lceil
n^{\varepsilon}\rceil$ the size of the neighborhood considered while
determining local minima and declare an element of a permutation to be a
$b$-local minimum if it is strictly smaller than all of its $b$ successors and
predecessors. Then, $E_{r}$ is the set of all $b$-local minima in $E_{r-1}$,
that is, $E_{r}=\\{i\in E_{r-1}:i<\pi_{r-1}^{k}(i)\textrm{ for all
}k\in\\{-b,\dots,b\\}\setminus\\{0\\}\\}$. We say that an element is on level
$r$ if it belongs to $E_{r}$. We define $\pi_{r}:E_{r}\rightarrow E_{r}$ as
follows: $\pi_{r}(e)$ is the first element of $E_{r}$ appearing after $e$ on
its cycle in $\pi$. For $b=1$ this is exactly the definition used by Fich et
al. [12], and for the reader who is unfamiliar with their work we provide a
recap of the algorithm and some intuition in Appendix A.

We use the same framework in the next section for the permutation inversion
problem, and so we already introduce some additional definitions that are only
used later.

######  Definition 3.1.

A _path_ of $\pi$ is a partial function obtained from a cycle $C$ of $\pi$ by
replacing $\pi(x)$ with $\perp$, for some $x\in C$.

$\perp$ should be understood as an undefined element. For a path, $\pi_{r}$ is
undefined for the last element from $E_{r}$, and similarly $\pi^{-1}_{r}$ is
undefined for the first element from $E_{r}$. When deciding if an element is a
$b$-local minimum on a path, we disregard comparisons with such undefined
elements. Furthermore, we assume that $\pi_{r}(\perp)=\perp$ and
$\pi^{-1}_{r}(\perp)=\perp$ for every $r$.

For each level $r$, only at most $\frac{1}{b+1}$ of its elements can belong to
the level $r+1$. For a cycle or a path $C$, let $t$ be the largest number such
that $|E_{t}\cap C|>b$. We set $t=0$ for $|C|\leq b$ and observe that
$t<\frac{1}{\epsilon}$ for every $C$. We note that if $C$ is a cycle then
$E_{t+2}\cap C=\emptyset$, but for $C$ being a path $|E_{t+2}\cap C|=1$.
Because all algorithms presented in this paper follow the framework given in
Algorithm 1 and during the execution of $\textsc{Process}(i)$, we only
consider the elements that can be reached from $i$, we restrict our
considerations to just one cycle or path and we are going to omit the ’’$\cap
C$‘‘ part everywhere later.

######  Definition 3.2.

A _$b$ -staircase_ of size $r$ from $i$ is a sequence of elements
$(i=i_{1},i_{2},\ldots,i_{r+1}=m=j_{r+1},j_{r},j_{r-1},\ldots,j_{1}=i^{\prime})$
such that $i_{k},j_{k}\in E_{k}$, for $k\in[r+1]$ and
$i_{k+1}=\pi_{k}^{b}(i_{k})$, $j_{k}=\pi_{k}^{b}(j_{k+1})$ for $k\in[r]$.
Elements $i$, $m$ and $i^{\prime}$ are called _the start_ , _the middle_ and
_the end_ of the $b$-staircase, respectively. The part of the $b$-staircase
from the start to the middle is called its _left part_ and the part from the
middle to the end is called its _right part_.

######  Definition 3.3.

An _almost $b$-staircase_ of size $r$ from $i$ is a sequence of elements
$(i=i_{1},i_{2},\ldots,i_{r+1}=m=j_{r+1},j_{r},j_{r-1},\ldots,j_{1}=i^{\prime})$,
such that $i_{k},j_{k}\in E_{k}$, for $k\in[r]$ and
$i_{k+1}=\pi_{k}^{b}(i_{k})$ and $j_{k}=\pi_{k}^{b}(j_{k+1})$ for $k\in[r]$.

######  Definition 3.4.

An almost $b$-staircase of size $r$
$(i=i_{1},i_{2},\ldots,i_{r+1}=m=j_{r+1},j_{r},j_{r-1},\ldots,j_{1}=i^{\prime})$
is called _proper_ if $|E_{r}|>b$.

######  Definition 3.5.

A $b$-staircase of size $r$ from $i$ is called the _best $b$-staircase from
$i$_ if there is no proper almost $b$-staircase of size $r+1$ from $i$
(possibly there is no best $b$-staircase from $i$).

######  Definition 3.6.

An element $i$ is the leader of its cycle if the best $b$-staircase from $i$
exists and its middle $m$ is the minimum on the cycle.

######  Lemma 3.7.

There is exactly one leader on any cycle of a permutation.

###### Proof.

Let $m$ be the minimum on the cycle and $t$ be the largest size of a proper
$b$-staircase on the cycle. Consider the $b$-staircase $B$ of size $t$ with
its start in $i=\pi_{1}^{-b}(\ldots(\pi_{t-1}^{-b}(\pi_{t}^{-b}(m)))\ldots)$.
As $m$ is the minimum on the cycle, there is no proper staircase of size $t+1$
from $i$, so $B$ is the best $b$-staircase and hence $i$ satisfies Definition
3.5 of the leader. As all the best $b$-staircases are of the same size we
cannot have more than one leader on the cycle. ∎

It may be that a $b$-staircase is longer than a full cycle if it visits some
elements twice (before and after reaching the middle of the $b$-staircase).
All elements occur at most once in each part of the $b$-staircase. We allow
computing $\textsc{MinRange}(x,y)$ for $x=\perp$ or $y=\perp$. In such a case,
the minimum is computed from the beginning or to the end of the path,
respectively.

######  Lemma 3.8.

Consider $m\in E_{r}$ on a cycle or a path where $|E_{r}|>b$. Then $m$ is a
$b$-local minimum on level $r$ in $\pi$ if and only if
$m=\textsc{MinRange}(\pi_{r}^{-b}(m),m,\pi_{r}^{b}(m))$.

###### Proof.

($\Leftarrow$) Trivial. ($\Rightarrow$) Proof by induction on level $r$. The
base case $r=1$ is immediate.

For $r>1$, assume that $m$ is a $b$-local minimum on level $r$. We consider
the elements in $\pi_{r}^{-b}(m)\ldots\pi_{r}^{b}(m)$, appropriately truncated
if we are on a path. Among these elements, only
$m_{k}=\pi_{r}^{k}(m)\neq\perp$ for $k\in\\{-b,\dots,b\\}$ are $b$-local
minima on level $r-1$. All of them are also larger than $m$ (if $k\neq 0$). By
the induction hypothesis, for all $k\in\\{-b,\dots,b\\}$ (such that
$m_{k}\neq\perp$) any element between $\pi_{r-1}^{-b}(m_{k})$ and
$\pi_{r-1}^{b}(m_{k})$ on the cycle/path is larger than or equal to $m_{k}$
and hence also larger than $m$. We call the above ranges the _ranges around
$m_{k}$_ and they are represented as segments in Figure 1.

Figure 1:  Filled nodes represent elements $m_{k}=\pi_{r}^{k}(m)$ for
$k\in\\{-b,\ldots,b\\}$ and each segment represents the range around $m_{k}$.
All the elements in the ranges (different than $m$) are larger than $m$ by
induction hypothesis.

Consider an element $x$ in $\pi_{r}^{-b}(m)\ldots\pi_{r}^{b}(m)$ which is not
in the range around $m_{k}$ for any $k$. In Figure 1, this corresponds to $x$
in a gap between the ranges. Clearly, $x\not\in E_{r}$, so there is an
$\ell<r$ such that $x\in E_{\ell}\setminus E_{\ell+1}$. Hence $x$ is larger
than some $x^{\prime}\in E_{\ell^{\prime}}\setminus E_{\ell^{\prime}+1}$
between $\pi_{\ell}^{-b}(x)$ and $\pi_{\ell}^{b}(x)$ for
$\ell<\ell^{\prime}\leq r$. If there is $k$ such that $x^{\prime}$ is in the
range around $m_{k}$, then $x^{\prime}>m_{k}>m$ and the lemma follows.
Otherwise, observe that $x^{\prime}$ belongs to the same gap as $x$ (see
Figure 7 for more detailed explanation why) so we can apply the same reasoning
for $x^{\prime}$ instead of $x$. Because the considered values are always
decreasing and each gap contains only finite number of elements, finally we
obtain a value in one of the ranges around $m_{k}$ and conclude that $x$ is
larger than one of the $m_{k}$ and also than $m$. Hence, $m$ is the smallest
element in $\pi_{r}^{-b}(m)\ldots\pi_{r}^{b}(m)$. ∎

The lemma enables us to check if an element $m$ is a $b$-local minimum on
level $r$ without knowing which of the elements in
$\pi_{r}^{-b}(m)\ldots\pi_{r}^{b}(m)$ belong to the level $r$.

Fich et al. develop the procedure $\textsc{Next}(r)$ which computes, for an
element on $E_{r}$, its successor on $\pi_{r}$. We start with extending their
idea to work with larger values of the parameter $b$. For $b=\lceil
n^{\epsilon}\rceil$, the number of elements to compare with is no longer
constant. We define a recursive pointer Ptr with the following fields:

  * •

$r$ – the level of the pointer,

  * •

$e$ – an element of $E_{r}$ pointed at by the pointer,

  * •

$x$ – Ptr of level $r-1$ pointing to $e$ (or NULL if $r=1$),

  * •

$y$ and $z$ – Ptrs of level $r-1$ both pointing to $\pi_{r-1}^{b}(e)$ (or NULL
if $r=1$).

Ptr has the Advance method which moves the pointer from $e$ to $\pi_{r}(e)$
and updates $x$, $y$ and $z$ accordingly. See Figure 2. Before and after
calling Advance, $y$ is equal to $z$, but during the execution they are
different. In fact, it is enough to only store $e$, $x$ and $z$ in every Ptr
and keep a local $y$ reused between every call to Advance method.

Figure 2:  A sketch of Ptr structure for $b=3$. On the bottom there is
$\textsc{Ptr}^{\prime}$, the result of executing the Advance method on Ptr.
The gray dots are not part of pointer, they only show the alignment between
Ptr and $\textsc{Ptr}^{\prime}$.

1:function $\textsc{Ptr}::\textsc{Advance}$

2: if $\textsf{this}.r=1$ then

3: if $\pi(\textsf{this}.e)=\perp$ then abort

4: $\textsf{this}.e\leftarrow\pi(\textsf{this}.e)$

5: return

6: for $j=1..b$ do $\textsf{this}.z.\textsc{Advance}()$

7: while
$\textsf{this}.y\neq\textsc{MinRange}(\textsf{this}.x.e,\textsf{this}.y.e,\textsf{this}.z.e)$
do

8: $\textsf{this}.x.\textsc{Advance}()$

9: $\textsf{this}.y.\textsc{Advance}()$

10: $\textsf{this}.z.\textsc{Advance}()$

11: $\textsf{this}.x\leftarrow\textsf{this}.y$

12: $\textsf{this}.e\leftarrow\textsf{this}.x.e$

13: $\textsf{this}.y\leftarrow\textsf{this}.z$

Algorithm 3 Implementation of the Advance method in the Ptr structure. It
moves the Ptr object onto the next element on the same level.

We now analyse $\textsc{Ptr}::\textsc{Advance}$ implemented in Algorithm 3 for
a pointer of level $r$. At the end of the function, $e$ is updated to point to
the element $x.e\in E_{r}$. As we have to also deal with paths, we add the
check for $\perp$ in line 3. For $r\geq 2$, $z$ is moved forward $b$ times
along $\pi_{r-1}$, so after line 6, $y$ and $z$ point to $\pi_{r-1}^{b}(x.e)$
and $\pi_{r-1}^{2b}(x.e)$, respectively. In line 7 we compare $y.e$ with all
elements between $\pi_{r-1}^{-b}(y.e)$ and $\pi_{r-1}^{b}(y.e)$ and all three
pointers are simultaneously advanced to the next elements along $\pi_{r-1}$
until $y$ points to a $b$-local minimum on level $r$. By Lemma 3.8 this is
equivalent to checking if $y.e$ is a $b$-local minimum on level $r-1$ as long
as $|E_{r-1}|>b$.

1:function BestbStaircase($i$)

2: $p\leftarrow\textsc{Ptr}(e\leftarrow i,~{}r\leftarrow
1,~{}x\leftarrow\texttt{NULL},~{}y\leftarrow\texttt{NULL},~{}z\leftarrow\texttt{NULL})$

3: $x\leftarrow i$

4: for $j=1..b$ do

5: $x\leftarrow\pi(x)$

6: if $x\in\\{\perp,i\\}$ then return $p$

7: while true do

8: $g\leftarrow p$

9: $m_{e}\leftarrow p.e$

10: for $j=1..2b$ do

11: try $p.\textsc{Advance}()$ catch /abort/ return $g$

12: if $j\leq b\textbf{ and }p.e=g.e$ then return $g$

13: if $j=b$ then $m_{p}\leftarrow p$

14: if $p.e<m_{e}$ then $m_{e}\leftarrow p.e$

15: if $m_{p}.e=m_{e}$ then $p\leftarrow\textsc{Ptr}(e\leftarrow
m_{p}.e,~{}r\leftarrow p.r+1,~{}x\leftarrow m_{p},~{}y\leftarrow
p,~{}z\leftarrow p)$

16: else return NULL

Algorithm 4 Constructs the best $b$-staircase from $i$ (if any).

In Algorithm 4 we implement $\textsc{Best}\textit{b}\textsc{Staircase}(i)$
that constructs the best $b$-staircase from $i$ returning Ptr structure
pointing to the middle of the staircase. Before running the main loop, the
algorithm checks if $|E_{1}|>b$, to make sure it is allowed to execute Advance
method on $p$. We start with a $b$-staircase of size $0$. Each iteration of
the main loop starts with $p$ of level $r$ representing the right part of the
$b$-staircase of size $r-1$ from $i$. The invariant $|E_{r}|>b$ is preserved
in the main loop. During each iteration, $p$ is subject to change and the
updated $p$ may not represent a (proper) $b$-staircase, so at the beginning of
the iteration, it is stored in $g$. Then, Advance method is called $2b$ times
on $p$ and enumerates the elements from the set $S=\\{\pi_{r}^{k}(e)$ :
$k\in\\{1,\dots,2b\\}\\}$. The pointer $m_{p}$ is stored after the $b$-th
Advance so it points to $\pi_{r}^{b}(e)$, that is the middle of the almost
staircase of size $r$. If $m_{p}.e$ is not the smallest in $S$, then the best
$b$-staircase from $i$ does not exist and we terminate in line 16. However, if
any of $\pi_{r}^{k}(e)$ for $k\in\\{1,\dots,b\\}$ is equal to $e$, then
$|S|\leq b$, so there is no proper almost staircase of size $r$ from $i$ (both
left and right part would self-overlap) and we return $g$ as the best
staircase. The same happens for paths in case any Advance call aborts. Only
when $|E_{r}|>b$ and the new middle $m_{e}$ is less than all $b$ pairwise-
distinct left and $b$ pairwise-distinct right neighbours on $E_{r}$, the
algorithm extends the $b$-staircase to size $r$ and proceeds to the next
iteration with $p$ of level $r+1$.

We are ready to provide an algorithm for the cycle leaders problem. We proceed
as in Algorithm 1, but we alter the Process function to work with the new
definition of leader, see Algorithm 5.

1:function Process($i$)

2: $p\leftarrow\textsc{Best}\textit{b}\textsc{Staircase}(i)$

3: if $p\neq\texttt{NULL}\textbf{ and }\textsc{MinRange}(i,i)=p.e$ then Report
that $i$ is the leader

Algorithm 5 Modified function for checking if $i$ is the leader of its cycle.

$\textsc{Best}\textit{b}\textsc{Staircase}(i)$ returns Ptr representing the
right part of the best $b$-staircase from $i$. Its middle can be read from the
field $e$ of the returned Ptr.

######  Theorem 3.9.

For every $\varepsilon>0$, there exists an algorithm for reporting leaders of
a permutation $\pi$ on $n$ elements in
$\mathcal{O}_{\varepsilon}(n^{1+\epsilon})$ time using
$\mathcal{O}_{\varepsilon}(\log n)$ additional bits of space.

###### Proof.

We analyse Algorithm 1 with implementation of Process provided in Algorithm 5.
Each Ptr of level $r$ has three Ptrs on level $r-1$, so there are
$\sum_{k=0}^{t}3^{k}=\mathcal{O}(3^{t})$ pointers in total. As
$t\leq\frac{1}{\epsilon}$, our algorithm uses
$\mathcal{O}(3^{\frac{1}{\epsilon}}\cdot\log n)=\mathcal{O}_{\varepsilon}(\log
n)$ extra bits of space.

The total time for reporting leaders is dominated by the time spent in
$\textsc{Ptr}::\textsc{Advance}$. We sum up (for all created pointers) just
the time inside Advance call of each Ptr without recursive calls. The time for
recursive calls will be accounted to the descendant pointers. Inside Advance,
the time is dominated by MinRange executions. As each advanced position is
covered by at most $2b+1$ MinRanges, if a pointer $p$ proceeds $k$ steps along
$\pi$ (starting with $p.x.e=s$ and ending with $p.z.e=\pi^{k}(s)$) during
Advance, the total time spent on executions of MinRange for the call is
$\mathcal{O}(kb)$.

Now we count the total length of traversals for all created pointers. This,
multiplied by $\mathcal{O}(b)$, is the final complexity of the algorithm.
Recall that for every element, we check if it is possible to create the best
$b$-staircase from it by constructing proper almost $b$-staircases and
validating if these are $b$-staircases. Thus, if it is possible to construct a
$b$-staircase of size $r$ and not $r+1$ from $i$, every pointer traverses (in
the worst possible case) all elements of the almost $b$-staircase of size
$r+1$ from $i$. We charge the traversed range to the pair $(r,m)$, where $m\in
E_{r+1}\setminus E_{r+2}$ is the middle of the $b$-staircase of size $r$ from
$i$. Observe that $i$ is between $\pi_{r+1}^{-1}(m)$ and $m$ and the execution
of $\textsc{Best}\textit{b}\textsc{Staircase}(i)$ finishes before reaching
$\pi_{r+1}^{2b+1}(m)$, see Figure 3. Thus, for each $r$, every element belongs
to $\mathcal{O}(b)$ ranges charged to the elements from $E_{r+1}\setminus
E_{r+2}$. The total length of all such ranges is therefore $\mathcal{O}(nb)$.
Recall that there are
$\mathcal{O}(3^{r})=\mathcal{O}(3^{t})=\mathcal{O}_{\epsilon}(1)$ pointers on
each level $r$, so summing over all $r\leq t$ we obtain that the running time
of Algorithm 5 is $\mathcal{O}(\frac{1}{\epsilon}\cdot 3^{t}\cdot
nb^{2})=\mathcal{O}_{\epsilon}(n^{1+2\epsilon})$. By adjusting $\epsilon$, the
running time becomes $\mathcal{O}_{\epsilon}(n^{1+\epsilon})$. ∎

Figure 3:  The maximum potential traversal range for a middle $m$ of a
$b$-staircase ($b=3$) of size $r$. The $b$-staircase of size $r$ with the
middle element $m$ is drawn with a bold line and the almost $b$-staircase of
size $r+1$ with new middle $m_{2}$ is drawn with a solid line.

##  4 Inverting permutation in smaller space

In this section, we extend the results of Section 3 to obtain an
$\mathcal{O}(n^{1+\epsilon})$-time algorithm for inverting permutations using
$\mathcal{O}_{\varepsilon}(\log n)$ bits. As this builds on the algorithm
given by El-Zein et al. [10], the reader unfamiliar with their work is
encouraged to first read Appendix B where we describe its simpler version.

The natural idea is to invert each cycle upon reaching its leader.
Unfortunately, after inverting a cycle for its leader $i$ we might obtain a
cycle with leader $i^{\prime}$ which might be greater than $i$ and we do not
want to invert this cycle again.

After inverting a cycle, the middle of the best $b$-staircase remains the same
and the only best $b$-staircase on the inverted cycle is exactly the reverse
of the previous best $b$-staircase. We can compute the end $i^{\prime}$ of the
largest $b$-staircase constructed from $i$ by implementing GetEnd method of
Ptr returning the end of the staircase as follows:
$p.\textsc{GetEnd}()=p.z.\textsc{GetEnd}()$ if $p.z\neq\texttt{NULL}$ and
$p.\textsc{GetEnd}()=p.e$ otherwise.

######  Definition 4.1.

A cycle $C$ of $\pi$ is  _hard_ if for the best $b$-staircase
$(i,i_{2},i_{3},\dots,i_{r},m,j_{r},\dots,j_{3},j_{2},i^{\prime})$ we have
$i^{\prime}>i$. Otherwise, $C$ is _easy_.

For $x$ on a cycle and $y=\pi(x)$, by setting $\pi(x)\leftarrow\perp$ we
obtain a path $P$ with $y$ as its first element and $x$ as the last element.
We call this operation _cutting before $y$_. For hard cycles, we are going to
cut the inverted cycle before its new leader and store null at the end of the
path. As in [10], we use multiple types of nulls that encode some additional
information. They can be efficiently simulated in our model using the idea of
El-Zein et al. [10]. For completeness, a proof can be also found in Appendix
B.

######  Lemma 4.2 ([10]).

For any $k\in[n]$, it is possible to simulate an extension of the range of
stored values of $\pi$ from $[n]$ to $[n]\cup\\{\perp_{1},\ldots,\perp_{k}\\}$
with each value from $[n]$ occurring at most $c$ times in $\pi$ using
$\mathcal{O}(ck\log n)$ bits with $\mathcal{O}(c)$-time overhead.

######  Definition 4.3.

_Sigma_ is a function $\pi:C\rightarrow C$, such that there is at least one
element $y\in C$ with $\\{\pi^{k}(y)\ :\ k\in\\{0,1,2,\dots\\}\\}=C$. We call
sigma _proper_ if it is not a cycle.

Depending on the number of times $k$ an element that looks like a possible
leader was found for a cycle, we can be in one of the following states:

  * •

not inverted cycle (for $k=0$),

  * •

inverted path (for $k=1$ and only if the cycle was hard),

  * •

inverted sigma (for easy cycles if $k=1$ and for hard cycles if $k\geq 2$).

We use the name _component_ for both paths and proper sigmas. In our
algorithm, we always have $\pi$ consisting only cycles and components. For a
path we call the element without the predecessor the  _start_ of the path and
the element pointing to null the  _end_ of the path. Similarly, in a proper
sigma we call element $y_{1}$ without predecessor the  _start_ of the sigma
and among the two elements $x_{1}$, $x_{2}$ such that
$\pi(x_{1})=\pi(x_{2})=y_{2}$ satisfying
$\ell(y_{1},x_{1})<\ell(y_{1},x_{2})$, $x_{2}$ is called the  _end_ and
$y_{2}$ the _intersection_ of the sigma. A part of sigma before the
intersection (from $y_{1}$ to $x_{1}$) is called the  _tail_ and the rest (a
cycle with $y_{2}$ and $x_{2}$) is the  _loop_ of sigma.

Notice that if we point the end of a component to its start, then it becomes a
cycle. We call such operation _fixing_ a component and the component is
_fixed_.

As we observed earlier, $b$-staircases constructed on cycles may be self-
overlapping, but staircases constructed on paths may not. For sigmas, the
situation is not that simple:

  * •

from the perspective of an element on the loop of a sigma, it is not easy to
recognise if it belongs to a cycle or to the loop of a sigma, and so we allow
self-overlapping staircases in this case (as in any cycle),

  * •

from the perspective of an element on the tail of a sigma, it is possible to
access the intersection of sigma (we show how later in this section), and we
disallow traversing any element twice by pretending that the connection from
the end to the intersection of the sigma points to a null, effectively being
the end of a path.

######  Definition 4.4.

The _leader_ of a component is the element that would be the leader in its
fixed component.

######  Definition 4.5.

The _rank_ of element $i$ on a path or on a tail of a sigma in $\pi$ is the
size of the best $b$-staircase from $i$. If there is no best $b$-staircase
from $i$ then its rank is undefined.

######  Definition 4.6.

An element $i$ is _outstanding_ if has the largest rank among the elements on
its component.

Our algorithm follows the left-to-right framework of Algorithm 1. It maintains
the following invariants:

  1. 1.

the start of a component is its leader (and is outstanding),

  2. 2.

the intersection of a sigma is the only element from which there is a best
staircase on the loop of the sigma (and is already processed).

The implementation of the procedure inverting permutations is provided in
Algorithm 6. Intuitively, the algorithm acts differently depending if the
element $i$ is on a cycle, a path or the tail of a sigma. It would be
convenient to detect it at the beginning of processing the element $i$, but
this would take too much time. However, all the cases start with computing
$\textsc{Best}\textit{b}\textsc{Staircase}(i)$ and terminate if the
computation failed or aborted. As we can only find the best $b$-staircase
after processing the whole cycle or component, we can augment this procedure
to (if the best $b$-staircase from $i$ exists) also return the element $a$
which is either predecessor of $i$ (for $i$ on the cycle) or the end of the
component (for $i$ on a path or the tail of a proper sigma). This is not
obvious only for proper sigmas and we use the following lemma:

######  Lemma 4.7.

Given an element $i$ on a sigma, it is possible to find the intersection of
the sigma or report that $i$ is on the loop in $\mathcal{O}(\ell+p)$ time,
where $\ell$ and $p$ are lengths of loop and tail of the sigma, respectively.

This was described by El-Zein et al. [10], and for completeness, we provide
the proof and implementation of FindIntersection in Appendix C. We assume that
FindIntersection can be also run on paths and might abort during the
evaluation of $\pi$. In this case, it returns $a$ for which $\pi(a)=\perp$. If
we started from the tail of a sigma, we can find its the end by using Lemma
4.7 and traversing the loop once more to find the predecessor on the loop. Now
we describe how the algorithm handles all the cases mentioned earlier.

When the leader $i$ of a cycle is found for the first time, the algorithm
finds the end $i^{\prime}$ of the corresponding $b$-staircase and inverts the
cycle, so $i^{\prime}$ becomes the leader of the inverted cycle. If
$i^{\prime}>i$, then the cycle is hard, and we change it into a path by
cutting before $i^{\prime}$. The rank of $i^{\prime}$ on the path is stored in
the type of the null.

The path remains in this state at least until we consider one of its
outstanding elements. To check if $i$ on the path is outstanding, we first
check if it is possible to create the best $b$-staircase from $i$. When the
best $b$-staircase is found on the path, we check if the rank of $i$ matches
the one saved in the null and if $i$ is the leader on the loop of sigma
created by pointing the end of the path to $i$. If this is the case, we
preserve the change, otherwise undo.

If the construction of $b$-staircase starts from an element $i$ on the loop of
a proper sigma, there is no easy way to distinguish it from a cycle. Thus, it
is not clear if we can use Algorithm 4 to verify if an element is outstanding.
Fortunately, the rank of any outstanding element on the tail of sigma equals
the rank of the leader of the proper sigma.

If the algorithm finds an outstanding element $i$, it creates a temporary,
larger sigma, by pointing the end of the sigma to $i$, then checks if there is
the best $b$-staircase from $i$ on the loop of sigma. If so, the change is in
effect or is reverted otherwise. Because of this check, we have no other
elements than $i$ with the best staircase on the loop of sigma. See Figure 4.

Figure 4: Lifecycle of a hard cycle during the execution of the algorithm
(chronologically from left to right). Circles are the elements from which
there is a best staircase, squares are outstanding elements of each component
and large nodes are elements that triggered the component update.

Let $c$ be the intersection of the sigma. From the invariants of our algorithm
we have that $c$ was an outstanding element in the component before its last
update and its rank $t$ in the previous component was equal to the rank of the
leader. We can compute $t$ by running
$\textsc{Best}\textit{b}\textsc{Staircase}(c)$ and then we can treat the sigma
as if it was a path by assuming that the end of the sigma points to
$\perp_{t}$ instead of $c$.

Notice that if we were always trying to find the intersection of sigma, this
could take much more time than the execution of
$\textsc{Best}\textit{b}\textsc{Staircase}(i)$, which often terminates early.
We also need to ensure that successful call of
$\textsc{Best}\textit{b}\textsc{Staircase}(i)$ never reaches the intersection
of the sigma from the end (it needs to be earlier updated to $\perp_{t}$). We
execute procedures $\textsc{Best}\textit{b}\textsc{Staircase}(i)$ and
$\textsc{FindIntersection}(i)$ in parallel in such a way that for every step
of the former procedure, we execute a constant number of steps of the latter.
Additional time spent on finding intersections is bounded by a constant
multiple of the time of $\textsc{Best}\textit{b}\textsc{Staircase}(i)$ and can
be omitted in the complexity analysis.

1:function Process($i$)

2: $(p,a)\leftarrow\textsc{Best}\textit{b}\textsc{Staircase}(i)$

3: if $p\neq\texttt{NULL}$ then

4: if $\pi(a)=i\textbf{ and }\textsc{MinRange}(i,p.e,a)=p.e$ then
$\triangleright$ $i$ is on a cycle.

5: $i^{\prime}\leftarrow p.\textsc{GetEnd}()$

6: $a^{\prime}\leftarrow\pi(i^{\prime})$ $\triangleright$ $a^{\prime}$ is the
predecessor of the new leader in the inverted cycle.

7: $\textsc{InvertCycle}(i)$

8: if $i^{\prime}>i$ then

9: $\pi(a^{\prime})\leftarrow\perp_{?}$

10:
$(p^{\prime},\\_)\leftarrow\textsc{Best}\textit{b}\textsc{Staircase}(i^{\prime})$

11: $r^{\prime}\leftarrow p^{\prime}.r$ $\triangleright$ $r^{\prime}$ is the
rank of the new leader in the path.

12: $\pi(a^{\prime})\leftarrow\perp_{r^{\prime}}$

13: else

14: if $\pi(a)\in[n]$ then $\triangleright$ $i$ is on a tail of sigma.

15:
$(p^{\prime},\\_)\leftarrow\textsc{Best}\textit{b}\textsc{Staircase}(\pi(a))$

16: $w\leftarrow\perp_{p^{\prime}.r}$

17: else$\triangleright$ $i$ is on a path.

18: $w\leftarrow\pi(a)$

19: if $\perp_{p.r}=w$ then

20: $s_{a}\leftarrow\pi(a)$

21: $\pi(a)\leftarrow i$

22:
$(p^{\prime\prime},\\_)\leftarrow\textsc{Best}\textit{b}\textsc{Staircase}(i)$

23: if $p^{\prime\prime}=\texttt{NULL}\textbf{ or }\textsc{MinRange}(i,i)\neq
p^{\prime\prime}.e$ then $\pi(a)\leftarrow s_{a}$

Algorithm 6 Final version of the function to process an element in order to
invert a permutation.

The correctness of the algorithm follows from the two invariants listed
earlier. Each cycle is inverted exactly once when the leader of the cycle is
found. If the cycle was easy, processing elements on the inverted cycle will
not find any leaders. If the cycle was hard, it is replaced with a path
starting at the leader of the inverted cycle (invariant 1 is satisfied). On a
path, there might be several outstanding elements, any might potentially
trigger the replacement of the path into a sigma. The proper sigma starts with
the same element as the path from which it was constructed and after enlarging
a proper sigma to another proper one, its start does not change, so invariant
1 holds. Because created intersections are always chosen to be outstanding
elements on the tail of sigma and we later check if they allow creating the
best staircase on the loop of the enlarged sigma, invariant 2 also holds.
Sigma can be enlarged many times, but it becomes a cycle when its start is
processed (this follows immediately from invariants 1 and 2). The resulting
cycle is the same as it was just after inverting and before cutting it into
the path, so there are no more leaders to be found. Note that elements can
become outstanding only when a path is created and every element on the loop
of sigma is not outstanding, so the number of outstanding elements always
strictly decreases whenever a new sigma is constructed. To estimate the
running time, we state the following property:

######  Lemma 4.8.

There are $\mathcal{O}(b)$ outstanding elements on every path.

###### Proof.

Assume there are (at least) $2b+2$ outstanding elements, denoted
$i_{1},i_{2},\dots,i_{2b+2}$ in this order on the path, each of rank $t$. Let
$m_{k}$ be the middle of $b$-staircase from $i_{k}$. $m_{k}$s are pairwise-
distinct, and it can be verified that the elements appear in the following
order on the path: $i_{1},m_{1},i_{2},m_{2},\dots,i_{2b+2},m_{2b+2}$.
Consequently, we can construct a proper almost $b$-staircase of size $t+1$
from $i_{1}$, with the middle $m_{b+1}$ and ending before $m_{2b+2}$ on the
path. This contradicts the assumption that $i_{1}$ is of rank $t$, as either
it is of rank at least $t+1$ or there is no best $b$-staircase from $i_{1}$. ∎

######  Theorem 4.9.

For every $\varepsilon>0$, there exists an algorithm for inverting a
permutation $\pi$ on $n$ elements in
$\mathcal{O}_{\varepsilon}(n^{1+\epsilon})$ time using
$\mathcal{O}_{\varepsilon}(\log n)$ additional bits of space.

###### Proof.

We estimate the running time of our algorithm. Any cycle is transformed
$\mathcal{O}(b)$ times to intermediate components until it becomes a cycle
with its leader already considered by earlier Process call (from Lemma 4.8).

We bound the running time in each cycle and intermediate component separately:
the total time spent on checking for all elements of the structure if there is
a best $b$-staircase from each of these elements (line 2 of Algorithm 6) is
always no larger than the time it would take in the fixed component. MinRange
and InvertCycle are executed only for elements for which a cycle was already
traversed, so they do not influence the time complexity. An additional run of
BestbStaircase (line 10) is executed only once for a cycle, but for a start of
best $b$-staircase on a tail of sigma (lines 15 and 22) may happen many times.
These additional checks are only recomputing the work already done for the
previous component, as the only elements reached are on the loop of the sigma.
Overall, the time complexity is $\mathcal{O}_{\varepsilon}(n^{1+\epsilon})$
for appropriate $\epsilon$. The amount of additional space follows from the
proof of Theorem 3.9. ∎

## References

  * [1] Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.  Elements of Programming Interviews in Java: The Insiders‘ Guide.  CreateSpace Independent Publishing Platform, USA, 2015.
  * [2] Paul Beame.  A general sequential time-space tradeoff for finding unique elements.  SIAM J. Comput., 20(2):270–277, 1991.
  * [3] Or Birenzwige, Shay Golan, and Ely Porat.  Locally consistent parsing for text indexing in small space.  In 31st SODA, pages 607–626. SIAM, 2020.
  * [4] Allan Borodin and Stephen A. Cook.  A time-space tradeoff for sorting on a general sequential model of computation.  SIAM J. Comput., 11(2):287–297, 1982.
  * [5] Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, and Martin Tompa.  A time-space tradeoff for sorting on non-oblivious machines.  J. Comput. Syst. Sci., 22(3):351–364, 1981.
  * [6] Timothy M. Chan.  Comparison-based time-space lower bounds for selection.  ACM Trans. Algorithms, 6(2):26:1–26:16, 2010.
  * [7] Timothy M. Chan, J. Ian Munro, and Venkatesh Raman.  Finding median in read-only memory on integer input.  Theor. Comput. Sci., 583:51–56, 2015.
  * [8] Omar Darwish and Amr Elmasry.  Optimal time-space tradeoff for the 2D convex-hull problem.  In 22nd ESA, volume 8737 of Lecture Notes in Computer Science, pages 284–295. Springer, 2014.
  * [9] Danny Dolev, Maria M. Klawe, and Michael Rodeh.  An ${O}(n\log n)$ unidirectional distributed algorithm for extrema finding in a circle.  J. Algorithms, 3(3):245–260, 1982.
  * [10] Hicham El-Zein, J. Ian Munro, and Matthew Robertson.  Raising permutations to powers in place.  In 27th ISAAC, volume 64 of LIPIcs, pages 29:1–29:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.
  * [11] John A. Ellis, Tobias Krahn, and Hongbing Fan.  Computing the cycles in the perfect shuffle permutation.  Inf. Process. Lett., 75(5):217–224, 2000.
  * [12] Faith E. Fich, J. Ian Munro, and Patricio V. Poblete.  Permuting in place.  SIAM J. Comput., 24(2):266–278, 1995.
  * [13] Johannes Fischer, Travis Gagie, Paweł Gawrychowski, and Tomasz Kociumaka.  Approximating LZ77 via small-space multiple-pattern matching.  In 12th ESA, volume 9294 of Lecture Notes in Computer Science, pages 533–544. Springer, 2015.
  * [14] Johannes Fischer, Tomohiro I, Dominik Köppl, and Kunihiko Sadakane.  Lempel-ziv factorization powered by space efficient suffix trees.  Algorithmica, 80(7):2048–2081, 2018.
  * [15] Wm. Randolph Franklin.  On an improved algorithm for decentralized extrema finding in circular configurations of processors.  Commun. ACM, 25(5):336–337, 1982.
  * [16] Greg N. Frederickson.  Upper bounds for time-space trade-offs in sorting and selection.  J. Comput. Syst. Sci., 34(1):19–26, 1987.
  * [17] Paweł Gawrychowski and Tomasz Kociumaka.  Sparse suffix tree construction in optimal time and space.  In 28th SODA, pages 425–439. SIAM, 2017.
  * [18] Alexander Golynski.  Cell probe lower bounds for succinct data structures.  In 20th SODA, pages 625–634. SIAM, 2009.
  * [19] Grzegorz Guśpiel.  An in-place, subquadratic algorithm for permutation inversion.  CoRR, abs/1901.01926, 2019.
  * [20] Daniel S. Hirschberg and James B. Sinclair.  Decentralized extrema-finding in circular configurations of processors.  Commun. ACM, 23(11):627–628, 1980.
  * [21] Alon Itai and Michael Rodeh.  Symmetry breaking in distributed networks.  Inf. Comput., 88(1):60–87, 1990.
  * [22] Donald E. Knuth.  Mathematical analysis of algorithms.  In IFIP Congress (1), pages 19–27, 1971.
  * [23] Donald E. Knuth.  The art of computer programming, Volume I: Fundamental Algorithms, 3rd Edition.  Addison-Wesley, 1997.
  * [24] J. Ian Munro and Mike Paterson.  Selection and sorting with limited storage.  Theor. Comput. Sci., 12:315–323, 1980.
  * [25] J. Ian Munro and Venkatesh Raman.  Selection from read-only memory and sorting with minimum data movement.  Theor. Comput. Sci., 165(2):311–323, 1996.
  * [26] Jakob Pagter and Theis Rauhe.  Optimal time-space trade-offs for sorting.  In 39th FOCS, pages 264–268. IEEE Computer Society, 1998.
  * [27] Gary L. Peterson.  An ${O}(n\log n)$ unidirectional algorithm for the circular extrema problem.  ACM Trans. Program. Lang. Syst., 4(4):758–762, 1982.
  * [28] Venkatesh Raman and Sarnath Ramnath.  Improved upper bounds for time-space trade-offs for selection.  Nord. J. Comput., 6(2):162–180, 1999.

##  Appendix A Leader election by Fich et al.

In this section, we describe an algorithm of cycle leader problem by Fich et
al. [12]. Compared to the original description, we introduce new notation and
change some details to make further algorithms easier to describe. We stress
that this should not be considered as new material and is provided only for
convenience.

Fich et al. [12] consider sets of local minima on the cycles of $\pi$. Let
$E_{1}=[n]$ and $\pi_{1}=\pi$. For $r>1$, $E_{r}\subset E_{r-1}$ is defined
inductively as the set of local minima in $E_{r-1}$ following the order of
permutation $\pi_{r-1}$, that is $E_{r}=\\{i\in
E_{r-1}:\pi_{r-1}^{-1}(i)>i<\pi_{r-1}(i)\\}$. Similarly,
$\pi_{r}:E_{r}\rightarrow E_{r}$ is the permutation that maps each element of
$E_{r}$ to the next element of $E_{r}$ that is encountered when following the
permutation $\pi_{r-1}$. Note that at most every second element of $E_{r-1}$
can belong to $E_{r}$ and hence $|E_{r}|\leq|E_{r-1}|/2$. For a cycle $C$ of
$\pi$, there exists $t\leq\lceil\log n\rceil$, such that $E_{t+1}\cap
C=\\{x\\}$, where $x$ is the minimum element on $C$. Of course, $E_{t+2}\cap
C=\emptyset$.

Figure 5:  Example of a single cycle of $\pi$. The number of circles around
each vertex indicates the set $E_{1}$, $E_{2}$, $E_{3}$ or $E_{4}$ the vertex
belongs to. Dashed edges denote $\pi_{2}$ and dotted edges denote $\pi_{3}$.

To simplify the presentation, we always restrict our analysis to a single
cycle. It generalizes easily to the original problem, as all presented
algorithms in this paper follow the pattern of Algorithm 1 and during
execution of $\textsc{Process}(i)$, we consider only the elements on the cycle
containing $i$. Let us proceed even further and also assume that we are
dealing with paths. This will be needed in sections about inverting
permutations.

######  Definition A.1.

A _path_ of $\pi$ is a partial function that can be obtained from a cycle $C$
of $\pi$ by replacing exactly one value of $\pi(x)$ to $\perp$ (for $x\in C$).

On a path, $\pi_{r}$ is undefined for the last element $\ell_{r}\in E_{r}$.
When deciding if an element is a local minimum on a path, we disregard
comparisons with undefined elements and we assume that $\pi_{r}(\perp)=\perp$
for every $r$.

Because it is easy to compute $\pi_{r}(i)$ but difficult to compute
$\pi_{r}^{-1}(i)$, we define the leader of a cycle to be the element $i$ such
that $m=\pi_{t}(\pi_{t-1}(\dots(\pi_{2}(\pi_{1}(i)))\dots))\in E_{t+1}$ for
$t$ such that $|E_{t+1}|=1$ and where $m$ is the minimum on the cycle.

In other words, to check if $i$ is the leader, we need to inspect elements
$i$, $\pi_{1}(i)$, $\pi_{2}(\pi_{1}(i))$, $\dots$,
$m=\pi_{t}(\pi_{t-1}(\dots(\pi_{2}(\pi_{1}(i)))\dots))$ and check if they
belong to $E_{1}$, $E_{2}$, $E_{3}$, $\dots$, $E_{t+1}$ respectively.
Intuitively, the leader $i$ is the witness that $m$ is the minimum of its
cycle.

We illustrate the definition on the example cycle in Figure 5 with $t=3$. We
can quickly find that 13 is not the leader, because
$\pi_{2}(\pi_{1}(13))=7\not\in E_{3}$. The leader of the cycle is 12 as
$\pi_{1}(12)=10\in E_{2}$, $\pi_{2}(10)=4\in E_{3}$ and $\pi_{3}(4)=3\in
E_{4}$.

######  Definition A.2.

A _staircase_ of size $r$ from $i$ is a sequence of elements
$(i=i_{1},i_{2},\ldots,i_{r+1}=m=j_{r+1},j_{r},j_{r-1},\ldots,j_{1}=i^{\prime})$
such that $i_{k},j_{k}\in E_{k}$, for $k\in[r+1]$ and $i_{k+1}=\pi_{k}(i_{k})$
and $j_{k}=\pi_{k}(j_{k+1})$ for $k\in[r]$. Elements $i$, $m$ and $i^{\prime}$
are called _the start_ , _the middle_ and _the end_ of the staircase,
respectively. Part of the staircase from the start to the middle is called
_left part_ of the staircase. Similarly, _right part_ of the staircase is the
part from the middle to the end of the staircase.

In the example from Figure 5, the staircase of size $3$ from $12$ is the
sequence $(i=12,10,4,m=3,4,7,i^{\prime}=9)$. See Figure 6 for a larger
example.

The algorithm constructs staircases of the largest possible size from each
element. It might happen that the constructed staircase is longer than a full
cycle, because it visits some elements twice (once before and once after
reaching the middle of the staircase). However, we notice that all elements
occur at most once in each part (left or right) of the staircase. This is the
case for the staircase of size 3 from 12 in Figure 5, where the part of cycle
between 12 and 9 was visited twice. As we may have to work on a path, we avoid
constructing staircases with undefined elements. Of course, for paths, it is
not possible to traverse any of its elements more than once.

Figure 6:  A staircase of size 3 from $9$ to $19$ with the middle element $1$
is marked bold. Curves of increasing heights represent $\pi_{1}$, $\pi_{2}$
and $\pi_{3}$ respectively.

As staircases are crucial objects that we use in all the presented algorithms,
we summarize their definition and naming in the more concise form:

$\begin{array}[]{rcccccccccccccccl}\rotatebox[origin={c}]{75.0}{$\in
E_{1}~{}~{}$}&&\rotatebox[origin={c}]{75.0}{$\in
E_{2}~{}~{}$}&&&&~{}\rotatebox[origin={c}]{75.0}{$\in
E_{r+1}$}&&\rotatebox[origin={c}]{75.0}{$\in
E_{r}~{}~{}$}&&\rotatebox[origin={c}]{75.0}{$\in
E_{r-1}$}&&&&\rotatebox[origin={c}]{75.0}{$\in
E_{2}~{}~{}$}&&\rotatebox[origin={c}]{75.0}{$\in E_{1}~{}~{}$}\\\
i=i_{1}&\overset{\pi_{1}}{\longrightarrow}&i_{2}&\overset{\pi_{2}}{\longrightarrow}&\cdots&\overset{\pi_{r}}{\longrightarrow}&i_{r+1}=m=j_{r+1}&\overset{\pi_{r}}{\longrightarrow}&j_{r}&\overset{\pi_{r-1}}{\longrightarrow}&j_{r-1}&\overset{\pi_{r-2}}{\longrightarrow}&\cdots&\overset{\pi_{2}}{\longrightarrow}&j_{2}&\overset{\pi_{1}}{\longrightarrow}&j_{1}=i^{\prime}\\\
\textrm{start}&&&&&&\textrm{middle}&&&&&&&&&&\textrm{end}\\\ \end{array}$

The heart of the algorithm of Fich et al. is the procedure $\textsc{Next}(r)$,
which computes the successive elements of $\pi_{r}$ recursively, using the
successive elements of $\pi_{r-1}$. It operates on table $elbow$ consisting of
elements from the cycle and changes it during the execution. The algorithm is
presented in Algorithm 7, with the only our modification in Line 3, which
aborts when attempting to pass the end of the path. Before we describe the
procedure in detail, we start with presenting the properties of the table
$elbow$ that are satisfied before and after execution of $\textsc{Next}(r)$.

1:function Next($r$)

2: if $r=1$ then

3: if $\pi(elbow[1])=\perp$ then abort

4: $elbow[0]\leftarrow\pi(elbow[1])$

5: return

6: while $elbow[r-1]<elbow[r-2]$ do

7: $elbow[r-1]\leftarrow elbow[r-2]$

8: $\textsc{Next}(r-1)$

9: while $elbow[r-1]>elbow[r-2]$ do

10: $elbow[r-1]\leftarrow elbow[r-2]$

11: $\textsc{Next}(r-1)$

Algorithm 7 A recursive procedure that rearranges the $elbow$ array and
computes $\pi_{r}(elbow[r])$.

The procedure operates on table elbow which prior to calling
$\textsc{Next}(r)$ satisfies:

$E_{r}\ni
elbow[r]=elbow[r-1]\overset{\pi_{r-1}}{\longrightarrow}elbow[r-2]\overset{\pi_{r-2}}{\longrightarrow}\cdots\overset{\pi_{2}}{\longrightarrow}elbow[1]\overset{\pi_{1}}{\longrightarrow}elbow[0]$
(1)

which is a shorthand for $elbow[r-1]=elbow[r]\in E_{r}$ and
$elbow[k-1]=\pi_{k}(elbow[k])$ for $1\leq k\leq r-1$. Immediately after
termination of $\textsc{Next}(r)$ the table $elbow$ satisfies:

$E_{r}\ni
elbow[r]\overset{\pi_{r}}{\longrightarrow}elbow[r-1]\overset{\pi_{r-1}}{\longrightarrow}elbow[r-2]\overset{\pi_{r-2}}{\longrightarrow}\cdots\overset{\pi_{2}}{\longrightarrow}elbow[1]\overset{\pi_{1}}{\longrightarrow}elbow[0]$
(2)

Notice that only the element $elbow[r]$ remains unchanged during the execution
of $\textsc{Next}(r)$. The main output of the function, $\pi_{r}(elbow[r])$,
is stored in $elbow[r-1]$. Observe that the $elbow$ array contains exactly the
right part of the staircase of size $r$ with the middle element $elbow[r]$:
$elbow[k]=j_{k+1}$ for $k\in[r]$. We use 0-based indexing for the $elbow$
array to be consistent with the algorithm of Fich et al.

Due to the condition (1), $elbow[r]\in E_{r}$ and hence all the subsequent
elements of $elbow$ satisfying the condition (2) are well-defined, as
$elbow[k]\in E_{k+1}\subset E_{k}$ for $k\in[r-1]$. Furthermore, it is not
possible to calculate the values in the left part of the staircase based only
on the $elbow$ array, so we need to ensure that upon calling
$\textsc{Next}(r)$, condition (1) is satisfied.

In the first while loop in Algorithm 7, the procedure iterates over
$\pi_{r-1}$ as long as the corresponding values on the cycle are increasing.
As the cycle is nontrivial, the loop terminates when $elbow[r-1]>elbow[r-2]$.
Similarly, the second while loop iterates over decreasing values on $E_{r-1}$
and terminates when $elbow[r-1]<elbow[r-2]$. Then $elbow[r-1]$ is the next
local minimum on $\pi_{r-1}$ after $elbow[r]$, and hence
$elbow[r-1]=\pi_{r}(elbow[r])$.

Observe that elbows create a nested structure, that is for each $m$ and $r$
such that $m\in E_{r+1}$, the element
$\pi_{1}(\pi_{2}(\dots(\pi_{r}(m))\dots))$ appears before $\pi_{r+1}(m)$ on
the cycle. This follows by induction. Similarly, we can say that
$\pi_{r}(\pi_{r-1}(\dots(\pi_{1}(i))\dots))$ appears earlier than
$\pi_{r+1}(i)$ on the cycle. See Figure 7 for an example.

Figure 7: Nested structure of elbows. Each $\pi_{r+1}(m)$ is $\pi_{r}^{p}(m)$
for some $p\geq 2$ and appears after
$\pi_{1}(\pi_{2}(\dots(\pi_{r}(m))\dots))$ when traversing from $m$. The
entries of the $elbow$ table before(after) the execution of
$\textsc{Next}(r+1)$ procedure are marked with a bold(solid) line.

Now we introduce more definitions and properties of the staircases.

######  Definition A.3.

An _almost staircase_ of size $r$ from $i$ is a sequence of elements
$(i=i_{1},i_{2},\ldots,i_{r+1}=m=j_{r+1},j_{r},j_{r-1},\ldots,j_{1}=i^{\prime})$,
such that $i_{k},j_{k}\in E_{k}$, for $k\in[r]$ and $i_{k+1}=\pi_{k}(i_{k})$
and $j_{k}=\pi_{k}(j_{k+1})$ for $k\in[r]$.

Notice the difference between staircase and almost staircase is that in the
latter we do not require its middle element $m$ to belong to $E_{r+1}$. This
might happen due to $m=\pi_{r}(i_{r})$ implying that $m\in E_{r}$, but not
necessarily $m\in E_{r+1}$.

######  Definition A.4.

An almost staircase
$(i=i_{1},i_{2},\ldots,i_{r+1}=m=j_{r+1},j_{r},j_{r-1},\ldots,j_{1}=i^{\prime})$
is called _proper_ if $i_{r}\neq m$ (which is equivalent to $m\neq j_{r}$).

On a cycle, it is always possible to extend a given staircase of size $r$ from
$i$ with the middle $m$, to an almost staircase of size $r+1$ from $i$. If the
extension is not proper, then $i_{r}=m$, so $m$ is the only element on
$E_{r}$. In this case, the staircase is the largest possible from $i$ and $m$
is the minimum of the cycle.

On a path, it might be not possible to extend a given staircase of size $r$
from $i$ with the middle $m$ to an almost staircase from $i$ of size $r+1$,
because of reaching $\perp$. If the extension to the almost staircase of size
$r+1$ from $i$ was not possible, the staircase of size $r$ is the largest
possible from $i$. Notice that every almost staircase on a path is proper.

######  Definition A.5.

Consider a staircase from $i$ of size $t$. We call it the _best staircase_
from $i$ if there is no proper almost staircase of size $t+1$ from $i$.

In the example cycle from Figure 5, it is possible to construct the best
staircase from 12: $(12,10,4,3,4,7,9)$, but the staircase $(14,7,3,6,12)$ is
not a best staircase, as it is possible to construct a proper almost staircase
$(14,7,3,4,3,6,12)$, which is not a staircase.

1:function BestStaircase($i$)

2: $elbow[0]\leftarrow elbow[1]\leftarrow i$

3: for $r=1..$ do

4: $m\leftarrow elbow[r]$

5: if Next($r$) aborted then

6: return $m$ $\triangleright$ Best staircase of the path is found.

7: $m^{\prime}\leftarrow elbow[r]\leftarrow elbow[r-1]$

8: if Next($r$) aborted then

9: return $m$$\triangleright$ Best staircase of the path is found.

10: $m^{\prime\prime}\leftarrow elbow[r-1]$

11: if $m^{\prime}=m$ then

12: return $m$ $\triangleright$ Best staircase of the cycle is found.

13: if $m^{\prime}<m$ and $m^{\prime}<m^{\prime\prime}$ then

14: $elbow[r+1]\leftarrow elbow[r]$ $\triangleright$ Constructed proper almost
staircase is a staircase.

15: else

16: return NULL$\triangleright$ Constructed proper almost staircase is not a
staircase.

Algorithm 8 Constructs the best staircase from $i$ (if any).

Algorithm 8 constructs the best staircase from $i$ or returns NULL if there is
no best staircase from $i$. It constructs almost staircases of increasing
sizes in subsequent iterations, checks if these are staircases (line 13) and
if so, updates the $elbow$ table. The algorithm succeeds upon finding that
there are no larger almost staircases, in such a case the middle of the
staircase is returned. The checks in line 5 and 8 are our modifications of
original algorithm to make it working also for paths.

For example, procedure $\textsc{BestStaircase}(9)$ executed on the part of the
cycle from Figure 6, constructs the following staircases in the subsequent
iterations of the main loop: $(9)$, $(9,4,10)$, $(9,4,2,7,12)$ and
$(9,4,2,1,3,8,19)$.

######  Lemma A.6.

For every cycle $C$ of permutation $\pi$ there is exactly one element $x\in
C$, from which there is a best staircase.

###### Proof.

On cycles there is no $\perp$, so Next will never abort. This means that the
only way for Algorithm 8 to return the best staircase is in line 12, when the
constructed almost staircase from $i$ is not proper, so $m$ is the only
element on $E_{t+1}$, thus the minimum on the cycle. Indeed, there is the best
staircase from $i=\pi^{-1}_{1}(\pi^{-1}_{2}(\dots(\pi^{-1}_{t}(m))\dots))$.

Notice that on a cycle, every best staircase has middle in $m$. There cannot
be two best staircases with the same middle $m$ and different sizes, as the
smaller could have been extended to a proper almost staircase and thus is not
best. This concludes the proof of the lemma. ∎

######  Definition A.7.

An element $i$ is the leader of its cycle if there exists the best staircase
from $i$.

There can be more than one element on a path from which there is a best
staircase. We will define leaders for paths in Appendix B.

Intuitively, our notion of a leader allows us to elect it efficiently because
we can terminate $\textsc{BestStaircase}(i)$ as soon as we encounter the first
$r$ such that $\pi_{r}(\pi_{r-1}(\dots(\pi_{1}(i))\dots))\not\in E_{r}$. Using
this definition, we can simply check if there is the best staircase from $i$
and if so, return $i$ as the leader of the cycle, see Algorithm 9.

1:function Process($i$)

2: $m\leftarrow\textsc{BestStaircase}(i)$

3: if $m\neq\texttt{NULL}$ then

4: Report that $i$ is the leader

Algorithm 9 Checks if $i$ is the leader of its cycle.

######  Theorem A.8.

There exists an algorithm for reporting leaders of a permutation $\pi$ on $n$
elements in $\mathcal{O}(n\log n)$ time using $\mathcal{O}(\log^{2}n)$
additional bits of space.

###### Proof.

The correctness of the algorithm follows immediately from Lemma A.6. The cost
of BestStaircase is proportional to the total number of calls to the Next
function, which is asymptotically the number of accesses to the input
permutation $\pi$. Observe that during the execution of
$\textsc{BestStaircase}(i)$ for a particular $i$, every call to
$\textsc{Next}(1)$ that accesses the permutation $\pi$, proceeds along the
cycle, so the execution of $\textsc{Process}(i)$ and testing if $i$ is the
leader involves $k$ steps along the cycle, from $i$ to $\pi^{k}(i)$ for some
$k$. Now we need to bound the total number of steps performed for all starting
elements $i$.

Figure 8: An almost staircase of size $r+1$ from $i$. $m$ is the middle
element of a staircase of size $r$ from $i$.

Consider an element $i$. Suppose the largest staircase created during
execution of $\textsc{BestStaircase}(i)$ have size $r$ and middle $m$. We do
not distinguish the reason why there is no staircase of larger size. From the
nested structure of elbows, $i$ is between $\pi_{r+1}^{-1}(m)$ and $m$ on the
cycle and construction of a larger almost staircase terminated between $m$ and
$\pi_{r+1}^{3}(m)$. See Figure 8. Hence the traversed part of the cycle while
running $\textsc{Process}(i)$ is bounded by the part of the cycle between
$\pi_{r+1}^{-1}(m)$ and $\pi_{r+1}^{3}(m)$ and we say that $i$ charges the
time of $\textsc{BestStaircase}(i)$ to $m$ at level $r$. As for a fixed
element $m$ and level $r$ there is at most one $i$ charging to $m$ at level
$r$, the total time for processing all elements is bounded by:

$\sum_{r=1}^{\lceil\log n\rceil}\sum_{m\in
E_{r}}\left(\ell(\pi_{r+1}^{-1}(m),m)+\ell(m,\pi_{r+1}(m))+\ell(\pi_{r+1}(m),\pi_{r+1}^{2}(m))+\ell(\pi_{r+1}^{2}(m),\pi_{r+1}^{3}(m))\right).$

where we split interval $\pi_{r+1}^{-1}(m)\cdots\pi_{r+1}^{3}(m)$ into four
terms in order to cover also the case when $|E_{r+1}|<4$. As the inner sum is
bounded by $4n$, the overall running time is $\mathcal{O}(n\log n)$.

The list of elbows consists of $\mathcal{O}(\log n)$ words of
$\mathcal{O}(\log n)$ bits and the depth of the recursion is $\mathcal{O}(\log
n)$, so the space complexity is $\mathcal{O}(\log^{2}n)$ bits. ∎

##  Appendix B Inverting permutation

To invert a cycle of a permutation, we use the following procedure of El-Zein
et al. [10]:

1:function InvertCycle($i$)

2: $p\leftarrow i$

3: $x\leftarrow\pi(i)$

4: while $x\neq i$ do

5: $n\leftarrow\pi(x)$

6: $\pi(x)\leftarrow p$

7: $p\leftarrow x$

8: $x\leftarrow n$

9: $\pi(x)\leftarrow p$

Algorithm 10 Invert the cycle with element $i$.

In each iteration of the while loop in Algorithm 10, $x$ is the position to
update and before executing line 6 of the algorithm we have $p=\pi^{-1}(x)$
and $n=\pi(x)$. We obtain $\mathcal{O}(1)$-space, $\mathcal{O}(n^{2})$-time
algorithm which computes $\pi^{-1}$ from $\pi$ by combining Algorithms 2 and
10: instead of reporting leaders, one should just invert the cycle.

The natural idea is to invert each cycle upon reaching its leader. This works
for the algorithm electing as leader the minimum of the cycle, as the leader
does not change after inverting the cycle. Unfortunately, the definition of
leader given in previous section is sensitive to cycle inversion. This is
exactly why simply executing Algorithm 9 instead of Algorithm 2 is not a
solution, because we need to ensure that we do not invert a cycle twice, but
we cannot mark that a cycle is already inverted.

More precisely, consider a cycle $C$ with the leader $i$ and the minimum
element $m$. When Algorithm 9 inverts $C$, it might happen that the leader $j$
of the inverted cycle is greater than $i$ and in this case, the already
inverted cycle $C$ gets inverted again while considering $j$. This explains
why our algorithm (and the algorithm of Fich et al.) cannot be applied
directly for inverting permutations.

To overcome this difficulty, our algorithm (similar to [10]) will mark such
difficult cycles by converting them to paths. Later, before terminating the
whole algorithm, each path has to be repaired to a cycle. At a high level,
this is a simplification of [10], because instead of having four different
scans running simultaneously, we have only one, corresponding to $\mathscr{F}$
there. Moreover, in our algorithm, because we store extended ranks, each hard
cycle is fixed only once, exactly when needed. This makes both the algorithm
and analysis simpler.

Observe that using the approach from the previous section, we can compute $j$
as the end of the largest staircase constructed from $i$ which we can read
from $elbow[0]$. Indeed, after inverting a cycle, the middle of the best
staircase remains the same, so the best staircase of the inverted cycle is
$(i^{\prime},j_{2},j_{3},\dots,j_{r},m,i_{r},\dots,i_{3},i_{2},i)$, exactly
the reverse of the previous best staircase.

######  Definition B.1.

A cycle $C$ of $\pi$ is  _hard_ if its best staircase
$(i,i_{2},i_{3},\dots,i_{r},m,j_{r},\dots,j_{3},j_{2},i^{\prime})$ satisfies
$i^{\prime}>i$. Otherwise, $C$ is _easy_.

At a high level, to compute $\pi^{-1}$ we invert cycles when processing their
leaders. If the cycle is hard we need to avoid inverting it again while
processing the leader of the inverted cycle. For this purpose we replace one
value of $\pi$ on the cycle with $\perp$ and the cycle becomes a path. The
path will be transformed to the cycle again while processing the leader of the
inverted cycle. Then the cycle will be never modified again.

On a path, while processing an element $i$, we are unable to visit its
preceding elements and so we cannot check if an element is minimum on the path
as in Algorithm 9. In order to be able to recognise this situation, we store
some additional information in each $\perp$.

Recall that in our model, we can only replace $\pi(i)$ with some value from
$[n]$. El-Zein et al. [10] introduce an approach which, using some additional
space, allows to virtually extend the set of possible values stored in $\pi$,
so that we can design algorithms in which
$\pi(i)\in[n]\cup\\{\perp_{1},\perp_{2},\ldots,\perp_{k}\\}$. $\perp_{i}$ is
the $i$-th _null_ character and it is possible to retrieve the value of $i$
from $\perp_{i}$. In our application, each value from $[n]$ appears at most
$c$ times in $\pi$, but for any $i$ there can be many elements $j$ such that
$\pi(j)=\perp_{i}$.

######  Lemma B.2 ([10]).

For any $k\in[n]$, it is possible to simulate an extension of the range of
stored values of $\pi$ from $[n]$ to $[n]\cup\\{\perp_{1},\ldots,\perp_{k}\\}$
with each value from $[n]$ occurring at most $c$ times in $\pi$ using
$\mathcal{O}(ck\log n)$ bits with $\mathcal{O}(c)$-time overhead.

###### Proof.

We store $\pi$ as an array $A$ with values from $[n]$ of size $n$ and an array
$B$ of $k$ lists, each of length at most $c$. The $k$-th list $B[k]$ stores
all values $i$ such that $\pi(i)=x$. We update the value of $\pi$ in the
following way:

  * •

for the update $\pi(i)\leftarrow x\in[n]$, we set $A[i]\leftarrow x$ and if
$x\leq k$ insert $i$ into the list $B[x]$,

  * •

for the update $\pi(i)\leftarrow\perp_{x}$, we set $A[i]\leftarrow x$.

If before the update held $\pi(i)=x\in[k]$, we first remove $i$ from $B[x]$.
To retrieve the value of $\pi(i)$, we return $A[i]$ if it is larger than $k$.
Otherwise, $A[i]=x\leq k$ and $\pi(i)$ is either $x$ or $\perp_{x}$. To
distinguish between these cases, we check the list $B[x]$ and return $x$ if
$i\in B[x]$ or $\perp_{x}$ otherwise. ∎

When the exact value stored in $\perp$ is not relevant, we will use the symbol
$\perp$ denoting $\perp_{k}$ for any $k$.

######  Definition B.3.

A _half staircase_ of size $r$ from $i$ is a sequence of elements
$(i=i_{1},i_{2},\ldots,i_{r+1}=m=j_{r},j_{r-1},j_{r-2},\ldots,j_{1}=i^{\prime})$
such that $i_{k},j_{\ell}\in E_{k}$, for $k\in[r]$, $\ell\in[r-1]$ and
$i_{k+1}=\pi_{k}(i_{k})$ for $k\in[r]$ and $j_{\ell}=\pi_{\ell}(j_{\ell+1})$
for $\ell\in[r-1]$.

Intuitively, a half staircase of size $r+1$ is the intermediate state between
the staircase of size $r$ and an almost staircase of size $r+1$. See Figure 9
for reference.

Figure 9:  A staircase of size $r$, a half staircase of size $r+1$ and an
almost staircase of size $r+1$.

Now we modify procedure $\textsc{BestStaircase}(i)$ to return a tuple
$(m,i^{\prime},t,h)$ where $m$ is the middle of the constructed best staircase
from $i$, $i^{\prime}$ is its end, $t$ is its size and $h$ is a Boolean value
denoting if an abort occurred after constructing a half staircase of size
$t+1$ from $i$.

1:function BestStaircase($i$)

2: $elbow[0]\leftarrow elbow[1]\leftarrow i$

3: for $r=1..$ do

4: $pi^{\prime}\leftarrow elbow[0]$

5: $m\leftarrow elbow[r]$

6: if Next($r$) aborted then

7: return $(m,pi^{\prime},r-1,\textsc{false})$

8: $m^{\prime}\leftarrow elbow[r]\leftarrow elbow[r-1]$

9: if Next($r$) aborted then

10: return $(m,pi^{\prime},r-1,\textsc{true})$

11: $m^{\prime\prime}\leftarrow elbow[r-1]$

12: if $m=m^{\prime}$ then

13: return $(m,pi^{\prime},r-1,\textsc{true})$

14: if $m^{\prime}<m$ and $m^{\prime}<m^{\prime\prime}$ then

15: $elbow[r+1]\leftarrow elbow[r]$

16: else

17: return NULL

Algorithm 11 Modified function that constructs the best staircase from $i$ (if
any).

Algorithm 11 implements the lifecycle of staircase extension. We try to extend
the staircase by constructing a half staircase of bigger size, then almost
staircase and then checking if the almost staircase is a staircase. See Figure
9. More precisely, the $r$-th iteration of the main loop starts with the
already constructed staircase of size $r-1$. In line 8, a half staircase of
size $r$ is constructed and then, in line 11 the algorithm extends it to an
almost staircase of size $r$. If an abort occurred while constructing an
almost staircase of size $r$ (in line 6 or 9) or if the constructed almost
staircase is not proper (line 12), then the staircase of size $r-1$ from the
beginning of iteration is the best staircase from $i$. If a proper almost
staircase of size $r$ is successfully created, the algorithm checks if it is a
staircase of size $r$ and either proceeds to next iteration or returns NULL.

######  Definition B.4.

The _rank_ of element $i$ on a path of $\pi$ is the size of the best staircase
from $i$. If there is no best staircase from $i$ then the rank of $i$ is
undefined.

######  Definition B.5.

The _extended rank_ of element $i$ on a path of $\pi$ is pair $(t,h)$, where
$t$ is the rank of $i$ and $h$ denotes if it is possible to construct the half
staircase of size $t+1$ from $i$. If $t$ is undefined then the extended rank
of $i$ is also undefined.

Extended ranks are compared lexicographically. The concept of rank is similar
to _limited depth_ in [10]. Our contribution is the idea of half staircases
and extended ranks. To see why it makes further considerations easier, we show
the following fact:

######  Lemma B.6.

For any path $P$ of $\pi$ there is a unique element of $P$ with the maximum
extended rank.

###### Proof.

First, observe that the extended rank $(t,h)$ and the middle $m\in E_{t+1}$
uniquely determines the start of the (half) staircase, which is
$\pi_{1}^{-1}(\pi_{2}^{-1}(\dots(\pi_{t}^{-1}(m))\dots))$ if
$h=\textsf{false}$ and
$\pi_{1}^{-1}(\pi_{2}^{-1}(\dots(\pi_{t+1}^{-1}(m))\dots))$ if
$h=\textsf{true}$. See Figure 9.

Suppose that there are two distinct elements $i$ and $j$ with the same maximum
extended rank $(t,h)$ and let $x$ be an element of $\pi$ such that
$\pi(x)=\perp$. Without loss of generality, assume that $\ell(i,x)>\ell(j,x)$,
that is $i$ is before $j$ on the path. Let $m_{i}$ and $m_{j}$ be the middle
of the best staircase of size $t$ starting from $i$ and $j$, respectively. By
definition, both $m_{i}$ and $m_{j}$ belong to $E_{t+1}$. From the nested
structure of staircases, $\pi_{t+1}(m_{i})$ is not later than $m_{j}$ on the
path. Consider first the case when $h=\textsf{false}$. Then it is possible to
construct a half staircase of size $t+1$ from $i$, because
$\pi_{1}(\pi_{2}(\ldots(\pi_{t+1}(m_{i}))\ldots))$ is not later than
$\pi_{1}(\pi_{2}(\ldots(\pi_{t}(m_{j}))\ldots))$ on the path and thus we can
increase the extended rank of $i$. For $h=\textsf{true}$, in a similar way we
can construct an almost staircase of size $t+1$ from $i$ which contradicts
that there is a best staircase of size $t$ from $i$. See Figure 10. ∎

Figure 10:  Two cases from the proof: on the top of the picture $i$ and $j$
have the extended rank $(t,0)$ and on the bottom they have extended rank
$(t,1)$. For the first case, we show that $i$ has the extended rank $(t,1)$,
because the half staircase of size $t+1$ from $i$ has its end not later than
$j^{\prime}$. Similarly, for the second case, we show that $i$ has extended
rank $(t+1,0)$. In the figure, it is assumed that $j$ is later on the path
than $m_{i}$ (which actually is always true), but the proof does not use this
assumption.

In fact, by a simple induction and applying the same reasoning as in the proof
of Lemma B.6 in every inductive step, we can prove even stronger property:

######  Observation B.7.

Let $(e_{1},e_{2},\dots,e_{k})$ be all the elements on a path $P$ of $\pi$
with defined extended rank, listed in the natural order. The sequence of their
corresponding extended ranks is strictly decreasing.

We note that from Lemma B.6 it follows that on every path there are at most
two elements of the maximum rank and this fact was also used in [10].

######  Definition B.8.

The  _leader_ of path $P$ of $\pi$ is the element of $P$ with the largest
extended rank.

Clearly, by Lemma B.6, there is a unique leader on every path. For a cycle $C$
and any $x\in C$ and $y=\pi(x)$, by setting $\pi(x)\leftarrow\perp$ we obtain
a path $P$ with $y$ as its first element and $x$ as the last element. We call
this operation _cutting before $y$_.

######  Proposition B.9.

If a cycle $C$ of $\pi$ with best staircase from $i$ is cut before $i$, then
the best staircase from $i$ in $P$ exists.

###### Proof.

Let $S_{1}$ be the sequence of staircases created during construction of the
best staircase from $i$ in $C$ and let $S_{2}$ be the sequence of staircases
created during construction of the best staircase from $i$ in $P$. $S_{2}$ is
a prefix of $S_{1}$, so the construction of best staircase from $i$ in $P$
never fails due to the fact that proper almost staircase is not a staircase,
but only because of an abort during the construction of almost staircase of
larger size. ∎

Notice that if a cycle with leader $i$ is cut before $i$ then, by Proposition
B.9, the rank of $i$ is still defined, although it can be less than the size
of the best staircase from $i$ before cutting the cycle. From Observation B.7
we obtain:

######  Corollary B.10.

For a cycle $C$ and the best staircase from $i$ ending in $i^{\prime}$, after
inverting the cycle and cutting it before $i^{\prime}$, we obtain a path $P$
starting with $i^{\prime}$ being its leader.

We now describe the new procedure Process for inverting permutations. During
the execution of the algorithm, each cycle of the permutation can be in one of
three following states:

  * •

the leader of the cycle has not been processed yet,

  * •

the leader of the cycle has been processed, the cycle is inverted, but the
leader of the inverted cycle has not been processed,

  * •

the cycle is inverted and the leader of the inverted cycle has been already
processed.

The second case applies only to hard cycles. In this case, after inverting the
cycle we cut it before $i^{\prime}$ where $i^{\prime}$ is the leader of the
inverted cycle.

Figure 11:  Lifecycle of a hard cycle: before execution of
$\textsc{Process}(9)$, after $\textsc{Process}(9)$ but before execution of
$\textsc{Process}(12)$ and the final cycle after execution of
$\textsc{Process}(12)$, respectively. Leaders of cycles/paths are denoted with
squares.

1:function Process($i$)

2: $(m,i^{\prime},r,h)\leftarrow\textsc{BestStaircase}(i)$

3: if $m\neq\texttt{NULL}$ then

4: $a\leftarrow\textsc{PathEnd}(i)$

5: if $a=\texttt{NULL}$ and  $\textsc{MinRange}(i,i)=m$ then

6: $b\leftarrow\pi(i^{\prime})$

7: $\textsc{InvertCycle}(i)$

8: if $i^{\prime}>i$ then

9: $\pi(b)\leftarrow\perp_{?}$ $\triangleright$ The value in the null is yet
to be determined.

10:
$(\\_,\\_,r^{\prime},h^{\prime})\leftarrow\textsc{BestStaircase}(i^{\prime})$

11: $\pi(b)\leftarrow\perp_{2r^{\prime}+h^{\prime}}$ $\triangleright$ Actual
extended rank on the path is computed.

12: if $a\in[n]\textbf{ and }\pi(a)=\perp_{2r+h}$ then

13: $\pi(a)\leftarrow i$

Algorithm 12 New version of the function to process an element in order to
invert a permutation.

The final approach for processing $i$ is described in Algorithm 12 where
PathEnd is a procedure which naively traverses the cycle from $i$ and either
returns NULL if the cycle was fully traversed or returns an element $a$, such
that $\pi(a)=\perp$. If a Boolean value appears in any arithmetic operation,
false is evaluated to $0$ and true to $1$.

$\textsc{Process}(i)$ first checks if a best staircase can be constructed from
$i$. If not, the execution for $i$ ends. Let $i^{\prime}$ be the end of the
constructed best staircase. If the algorithm is processing a cycle, we invert
it. If the cycle is hard, we cut the inverted cycle before $i^{\prime}$,
compute the extended rank of $i^{\prime}$ on the path and then store it in the
value of null for the predecessor of $i^{\prime}$ in the inverted cycle, which
is now the end of the path. Later, for the path, there might be multiple
elements from which we can create best staircases, but $i^{\prime}$ is the
only element with the largest extended rank. For every element with the best
staircase, we compare its extended rank with the one stored in null. If they
are equal, this means that we found the leader of the path and we fix the path
into the cycle by setting $\pi(a)=i$, where $a$ is end of the path. Then, the
currently processed element $i$ is the leader of the created cycle and no
element in the future will be the leader of this cycle. Hence, till the end of
the execution of the whole algorithm, the cycle will remain unchanged.

######  Theorem B.11.

There exists an algorithm for inverting permutation on $n$ elements in
$\mathcal{O}(n\log n)$ time using $\mathcal{O}(\log^{2}n)$ additional bits of
space.

###### Proof.

The algorithm calls $\textsc{Process}(i)$ from Algorithm 12 for all
$i=1,2,...,n$. Until reaching the leader, it operates on the original cycle
and the total time is $\mathcal{O}(n\log n)$ as in Theorem A.8. After
inverting the cycle, the time for processing an element on the path does not
exceed the time for processing this element on the inverted cycle, so the
total time spent by the algorithm after inverting the cycle is upper bounded
by processing the whole inverted cycle, which is also $\mathcal{O}(n\log n)$
by the same argument.

As we use $k=2\lceil\log n\rceil$ types of nulls to store extended ranks of
leaders, we bound the additional number of bits using Lemma B.2 for $c=1$ and
$k=2\lceil\log n\rceil$. Recursion in Next has depth $O(\log n)$ and each
level of recursion requires only $O(\log n)$ space. Thus, in total we use
$O(\log^{2}n)$ additional bits of space. ∎

##  Appendix C Tortoise and hare algorithm

######  Lemma C.1.

Given an element $i$ on a sigma, it is possible to find the intersection of
the sigma or report that $i$ is on the loop in $\mathcal{O}(\ell+p)$ time,
where $\ell$ and $p$ are lengths respectively of loop and path of the sigma.

###### Proof.

Consider a sigma $\sigma$. We can use the classic Floyd‘s cycle-finding
algorithm called tortoise and hare. In this algorithm we maintain two
pointers, initially set to $i$. In each iteration both pointers proceed along
the sigma, where tortoise does one step per iteration and hare does two.
Eventually, after at most $\ell+p$ of steps they will meet in a common point
of $\sigma$ and the point belongs to the loop of $\sigma$.

Then we make the tortoise move from the meeting point to traverse the whole
loop, obtaining the length $\ell$ of the loop of sigma. If the tortoise visits
element $i$, then we return that $i$ belongs to the loop. Otherwise, we can
use two tortoises which move one step per iteration from the starting point
$i$. One of them first does $\ell$ steps and then they simultaneously move by
one step. Clearly, they will meet in the intersection of the sigma. See
Algorithm 13. Then the total number of steps made by procedure
$\textsc{FindIntersection}(i)$ is bounded by $3\ell+2p=\mathcal{O}(\ell+p)$. ∎

1:function FindIntersection($i$)

2: $k\leftarrow 0$, $t\leftarrow i$, $h\leftarrow i$

3: repeat

4: if $\pi(h)=\perp\textbf{ or }\pi(\pi(h))=\perp$ then abort

5: $t\leftarrow\pi(t)$, $h\leftarrow\pi(\pi(h))$

6: $k\leftarrow k+1$

7: until $t=h$

8: $\ell\leftarrow 0$, $t_{0}\leftarrow t$

9: repeat

10: if $t_{0}=i$ then return ’’$i$ is on the loop‘‘

11: $t_{0}\leftarrow\pi(t_{0})$

12: $\ell\leftarrow\ell+1$

13: until $t_{0}=t$

14: $t_{1}\leftarrow i$, $t_{2}\leftarrow i$

15: for $j=1..\ell$ do

16: $t_{1}\leftarrow\pi(t_{1})$

17: while $t_{1}\neq t_{2}$ do

18: $t_{1}\leftarrow\pi(t_{1})$, $t_{2}\leftarrow\pi(t_{2})$

19: return ’’$t_{1}$ is the intersection‘‘

Algorithm 13 Implementation of tortoise and hare technique to find the
intersection of sigma.