I'm wondering if there are well known sorting techniques for the following problem.
Problem:
Suppose you would like to sort a list of integer numbers $0, 1, 2, \ldots, d$.
If one is only allowed to use swaps of adjacent positions the major part
of programmers would choose a bubble sort type algorithm.
The $d$ sized set of adjacent swaps $P^d_{\text{adj}}$ can be interpreted as the permutations, e.g. for $d=9$
$P^9_{\text{adj}} = \{\\
\quad [1,0,2,3,4,5,6,7,8,9],\\
\quad [0,2,1,3,4,5,6,7,8,9],\\
\quad [0,1,3,2,4,5,6,7,8,9],\\
\quad [0,1,2,4,3,5,6,7,8,9],\\
\quad [0,1,2,3,5,4,6,7,8,9],\\
\quad [0,1,2,3,4,6,5,7,8,9],\\
\quad [0,1,2,3,4,5,7,6,8,9],\\
\quad [0,1,2,3,4,5,6,8,7,9],\\
\quad [0,1,2,3,4,5,6,7,9,8]\\
\}.$
Question: Are there sorting techniques for other sets of permutations?
I would like to use the following $1+d+d$ sized set, e.g. for $d=9$
$P^9 = \{\\
\quad [0,1,2,3,4,5,6,7,9,8],\\
\quad\\
\quad [8,0,1,2,3,4,5,6,7,9],\\
\quad [8,1,0,2,3,4,5,6,7,9],\\
\quad [8,1,2,0,3,4,5,6,7,9],\\
\quad [8,1,2,3,0,4,5,6,7,9],\\
\quad [8,1,2,3,4,0,5,6,7,9],\\
\quad [8,1,2,3,4,5,0,6,7,9],\\
\quad [8,1,2,3,4,5,6,0,7,9],\\
\quad [8,1,2,3,4,5,6,7,0,9],\\
\quad [8,1,2,3,4,5,6,7,9,0],\\
\quad\\
\quad [9,0,1,2,3,4,5,6,7,8],\\
\quad [9,1,0,2,3,4,5,6,7,8],\\
\quad [9,1,2,0,3,4,5,6,7,8],\\
\quad [9,1,2,3,0,4,5,6,7,8],\\
\quad [9,1,2,3,4,0,5,6,7,8],\\
\quad [9,1,2,3,4,5,0,6,7,8],\\
\quad [9,1,2,3,4,5,6,0,7,8],\\
\quad [9,1,2,3,4,5,6,7,0,8],\\
\quad [9,1,2,3,4,5,6,7,8,0]\\
\}.$
For general $P^d$, the first permutation swaps $d-1$ with $d$.
The 1st subset of $d$ permutations start with $d-1$ and the
zero is moving to the right.
The 2nd subset of $d$ permutations start with $d$ and the
zero is moving to the right.
This set of permutations comes from an integral decomposition problem.
Additional question:
Can the sorting be done in $d$ steps with the given set $P^d$?
Edit 2019-03-18:
@Jaap I will accept your answer if no other more sophisticated algorithm will be given.
Now that we have at least an algorithm which uses $\mathcal{O}(d^2)$ permutations
I would like to tighten some constraints and give more information.
- Every permutation used will result in an inverse matrix multiplication
for my numerical analysis program, which will worsen the numerical error, thus I would like to have a better upper bound. - Instead of $P^d$ one is allowed to use $P^{-d} := \{ \pi^{-1} : \pi \in P^d\}$.
- Algorithms which recognize some/all of the permutations get a bonus.
- Algorithms which use a specific permutation repeatedly do NOT get a bonus.
- Algorithms which only work for odd permutations but have a
somehow nice twist get a bonus.
Edit 2019-03-21:
I wrote a small C++ program, which calculates the height of a shortest path tree (SPT) of the cayley graph $\Gamma = \Gamma(S_{d+1},P^d)$
with the root node of the tree placed at the identity permutation.
This gives for $3 \le d \le 9$
-
$height(SPT(\Gamma)) = d$.
-
If one removes the 1st subset we have
$height(SPT(\Gamma)) = d$. -
If one removes the 2nd subset we have
$height(SPT(\Gamma)) = d+1$.
Edit 2019-04-04:
Numerical evidence suggests that for $d \ge 4$
the only SPT being invariant under edge completion (EC)
is the one coming from the subset $Q \subseteq P^d$
consisting of the 2nd subset of permutations, i.e.
$
Q = \{\\
\quad [9,0,1,2,3,4,5,6,7,8],\\
\quad [9,1,0,2,3,4,5,6,7,8],\\
\quad [9,1,2,0,3,4,5,6,7,8],\\
\quad [9,1,2,3,0,4,5,6,7,8],\\
\quad [9,1,2,3,4,0,5,6,7,8],\\
\quad [9,1,2,3,4,5,0,6,7,8],\\
\quad [9,1,2,3,4,5,6,0,7,8],\\
\quad [9,1,2,3,4,5,6,7,0,8],\\
\quad [9,1,2,3,4,5,6,7,8,0]\\
\}.$
Where edge completion (EC) means adding an edge
iff two nodes of tree depth k and k+1
can be connected with a valid generator/permutation.
Edit 2019-04-06: (Additional information)
We have an accepted answer now.
There are similar more difficult problems,
where one has faster growing sets $P^{d,m}$ of valid permutations
and one expects to do the sorting in $d-m$ steps.
Numerical evidence suggests there might be a relation to
http://oeis.org/A130477
where e.g. for $d=4$, the row $1, 4, 15, 40, 60$ would tell us,
there is 1 permutation of $S_{d+1}$ which can be sorted in $0$ steps.
there are 4 permutations of $S_{d+1}$ which can be sorted in $1$ step.
there are 15 permutations of $S_{d+1}$ which can be sorted in $2$ steps.
there are 40 permutations of $S_{d+1}$ which can be sorted in $3$ steps.
there are 60 permutations of $S_{d+1}$ which can be sorted in $4$ steps.
Edit 2019-04-06: (Example of antkam's algorithm)
If one uses the "right-first" convention for multiplying two permutations,
antkam's solution uses the inverted permutations of $Q$.
As can be seen with the following example
$[0,\color{red}{4},3,1,2]
\rightarrow [2,\color{red}{4,0},3,1]
\rightarrow [1,\color{red}{2,4,0},3]
\rightarrow [3,\color{red}{1,2,4,0}]
\rightarrow [\color{red}{0,1,2,3,4}].
$
And as decomposition with inverted permutations from $Q$:
$
\begin{align}
&[0,\color{red}{4},3,1,2]\\
=&[2,\color{red}{4,0},3,1][2,1,3,4,0]\\
=&[1,\color{red}{2,4,0},3][1,2,3,4,0][2,1,3,4,0]\\
=&[3,\color{red}{1,2,4,0}][1,2,3,4,0][1,2,3,4,0][2,1,3,4,0]\\
=&[4,1,2,0,3]^{-1}[4,0,1,2,3]^{-1}[4,0,1,2,3]^{-1}[4,1,0,2,3]^{-1}.
\end{align}
$
Edit 2019-04-08: (Example of improved algorithm)
There is an obvious improvement to antkam's algorithm,
where one simply keeps the red run (ascending numbers) as large as possible.
Antkam's algorithm would give for $[0,2,3,4,1]$
$[0,\color{red}{2},3,4,1]
\rightarrow [1,\color{red}{2,0},3,4]
\rightarrow [4,\color{red}{1,2,0},3]
\rightarrow [3,\color{red}{1,2,4,0}]
\rightarrow [\color{red}{0,1,2,3,4}].
$
Whereas the improved algorithm would give for $[0,2,3,4,1]$
$[0,\color{red}{2,3,4},1]
\rightarrow [1,\color{red}{2,3,4,0}]
\rightarrow [\color{red}{0,1,2,3,4}].
$
It looks like the transition graph of the improved algorithm
is isomorphic to the tree graph $SPT(\Gamma(S_{d+1},Q)$ discussed earlier.
I have added an image for $d=4$ with the tree graph,
where the root of the tree represents the identity permutation.
Best Answer
Here is an algorithm that can sort in exactly $d$ steps ($d$ permutations). It uses only the so-called $2$nd subset, where all operations bring the last entry (the $d$) to the front, while allowing you to "shoot" the front entry (the $0$) anywhere.
My key idea is that, the power to move $0$ anywhere makes this similar to how one can sort a hand of cards. I.e. maintain a sorted sub-sequence, and at every step take a new card and insert it into the right place in the sorted sub-sequence, growing the sorted sub-sequence by one card. After inserting $d$ cards you'd be done. It took me a few tries to get all the details right, to map this onto the $2$nd subset.
Here is my first attempt:
Initialization: Color the $2$nd entry (i.e. position $1$ in your numbering scheme) in the input array red. (This step is conceptual - no permutation is actually done.)
Invariant: In between turns, the red entries will always start at the second position (position $1$), be contiguous, and be sorted.
Every turn: Pick the $1$st entry (position $0$), which will be not red. Color it red, and insert it into the existing red sub-array at the right place.
Here is an example: We will sort $FCBDGEA$.
$$ \begin{align} FCBDGEA & = F\color{red}{C}BDGEA \, \, \, \, \, \, \text{(initialization)}\\ & \rightarrow A\color{red}{CF}BDGE \\ & \rightarrow E\color{red}{ACF}BDG \\ & \rightarrow G\color{red}{ACEF}BD \\ & \rightarrow D\color{red}{ACEFG}B \\ & \rightarrow B\color{red}{ACDEFG} \\ & \rightarrow \color{red}{GABCDEF} \\ \end{align} $$
Clearly (e.g. by the invariant), after $d$ turns (i.e. $d$ permutations) we end up with the sorted array, but starting at the $2$nd position. I.e., the result is one left-shift from the desired answer. Left-shift is not allowed, but right-shift is in the $2$nd subset, so we can do $d$ more right-shifts and arrive at the desired answer $ABCDEFG$. Therefore this first-attempt runs in $2d$ steps.
My second attempt fixes the "bug" by declaring that the minimum element (here, $A$) be treated as the maximum. Except for this modified sort order, the algorithm is identical to the first attempt. The same example:
$$ \begin{align} FCBDGEA & = F\color{red}{C}BDGEA \, \, \, \, \, \, \text{(initialization)}\\ & \rightarrow A\color{red}{CF}BDGE \\ & \rightarrow E\color{red}{CFA}BDG \, \, \, \, \, \, \text{(treat $A$ as maximum)}\\ & \rightarrow G\color{red}{CEFA}BD \\ & \rightarrow D\color{red}{CEFGA}B \\ & \rightarrow B\color{red}{CDEFGA} \\ & \rightarrow \color{red}{ABCDEFG} \\ \end{align} $$
Just like in the first attempt, after $d$ steps (permutations) we end up with the "sorted" array starting at the $2$nd position - except now "sorted" means according to the "modified" sort order, i.e. $BCDEFGA$. Clearly, this means the array starting at the front will be sorted according to the unmodified order. I.e. this second attempt algorithm sorts the array in exactly $d$ steps (permutations), as claimed.