2
$\begingroup$

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, SPT(Gamma(S,Q)) where the root of the tree represents the identity permutation.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Want to mention that you are using the inverted permutations of $Q$. $\endgroup$ – andre Apr 6 at 21:21
  • $\begingroup$ I am using the permutations $Q$. what does "inverted permutation" mean? $\endgroup$ – antkam Apr 6 at 21:40
  • $\begingroup$ I have edited the problem text and added another example of your algorithm. $\endgroup$ – andre Apr 6 at 21:47
  • $\begingroup$ I have added some information and an image how your algorithm links to my shortest path tree idea. $\endgroup$ – andre Apr 8 at 19:21
  • $\begingroup$ @andre - ah, i see, thanks. yeah, if you "get lucky" with the initial segment, you can use $< d$ permutations. $\endgroup$ – antkam Apr 9 at 17:22
1
$\begingroup$

Basically you have a set of generator permutations, together they generate a group of permutations, and you want to be able to decompose any element of that group into a product of those generators.

The Schreier Sims algorithm does that. It generates the group, and in the process builds up a data structure that allows you to factorise any element as a product of generators.

Unfortunately, this often leads to really long products. There are various techniques to shorten the average lengths, but in general it can be really hard to find short generator sequences, let alone optimally short ones. If we could do that, we could solve any permutation puzzle like a Rubik's Cube optimally.

Thankfully, your particular case is a relatively easy.

You could use just two of the generators. If you pick two of them that generate the whole group (all $10!$ permutations), then you can also write any permutation as a product of those two generators. All your generators are cycles, so you can pick any two generators provided that (1) every digit 0-9 gets moved by at least one of them, (2) at least one digit gets moved by both of them, (3) at least one of the generators has odd permutation parity. On my web page Rotational Puzzles on Graphs you can find a proof of that. However for most permutations this also will still result in a very long product.

In your case you have so many generators, and they are of a particularly nice structure, that it is quite straightforward to get relatively short products. It is easiest to think of this as a permutation puzzle. You have ten items that are in a random order, and using the moves (given by the generators) you want to solve the puzzle by putting the items in sorted order. I will actually only use the first subset of generators:

$$a=\quad [8,0,1,2,3,4,5,6,7,9],\\ b=\quad [8,1,0,2,3,4,5,6,7,9],\\ c=\quad [8,1,2,0,3,4,5,6,7,9],\\ d=\quad [8,1,2,3,0,4,5,6,7,9],\\ e=\quad [8,1,2,3,4,0,5,6,7,9],\\ f=\quad [8,1,2,3,4,5,0,6,7,9],\\ g=\quad [8,1,2,3,4,5,6,0,7,9],\\ h=\quad [8,1,2,3,4,5,6,7,0,9],\\ i=\quad [8,1,2,3,4,5,6,7,9,0]$$

All of them keep location $9$ undisturbed except $i$, so solve item $\#9$ first. Do this by applying $a$ however often you need to bring the item $\#9$ into location $0$ (i.e. at the left of the row) and then apply $i$ to bring item $\#9$ into location $9$ where it belongs. The rest will be solved without using $i$, and so $9$ will remain in place.

The rest is simpler. At each stage you have one generator that cycles all the remaining unsolved items, and there is one location unaffected by all the other generators.

Next solve item $\#1$. Simply apply $a$ until it is in location $1$ where it belongs.
Next solve item $\#2$. Simply apply $b$ until it is in location $2$ where it belongs.
Next solve item $\#3$. Simply apply $c$ until it is in location $3$ where it belongs.
Next solve item $\#4$. Simply apply $d$ until it is in location $4$ where it belongs.
Next solve item $\#5$. Simply apply $e$ until it is in location $5$ where it belongs.
Next solve item $\#6$. Simply apply $f$ until it is in location $6$ where it belongs.
Next solve item $\#7$. Simply apply $g$ until it is in location $7$ where it belongs.
Lastly solve item $\#8$. Simply apply $h$ until it is in location $8$ where it belongs.
Item $\#0$ should now be in location $0$, since it has nowhere else it can be.

The above gives you a product of generators that undoes the permutation, so strictly speaking it is the inverse of the original permutation.

This method generalises to any value of $d$. For most permutations there are likely to be shorter ways of writing it as products of generators, especially since I have not used the other $d+1$ generators that are available, but it is really hard to find optimal solutions, even with such nice generators as these.

$\endgroup$
  • $\begingroup$ +1, from me, so we have here an algorithm which needs always $\mathcal{O}(d^2)$ permutations, the cost model I haven't mentioned yet almost longs for the shortest products. I'll update my question. $\endgroup$ – andre Mar 18 at 20:28
  • $\begingroup$ I haven't checked the Schreier Sims Algorithm yet, but it does look like I would have to implement it for my numerical analysis program or use a tabularized version of it, which feels like overkill at the moment. $\endgroup$ – andre Mar 18 at 20:36
  • $\begingroup$ @andre Don't bother with Schreier Sims - wonderful and useful as it is, it is not the tool for short solutions. The GAP software system uses it, together with clever ransomised ways of shortening the solutions. If you let it solve a random Rubik's Cube, it takes about 80-120 moves I think, compared to the optimal solution of <=20. $\endgroup$ – Jaap Scherphuis Mar 19 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.