What is the order of this algorithm?

Question

I was messing around with a method of manipulating strings in Java when I came across this algorithm. For a string of length n:

$$\{1, 2, ... ,n - 1, n\}$$

rearrange it such that the first character goes in the first position, the last character goes in the second position, the second character goes in the third position, the second-to-last character goes in the fourth position, etc:

$$\{1, n, ..., \frac n2 - 1, \frac n2\}$$

Demonstrating on an actual string, for example the string "test":

"test" → "ttes" → "tste" → "test".

Through messing around with some strings of longer length, I discovered the following:

• The number of applications of the algorithm (hereafter referred to as "iterations") needed to "cycle around" a string of length n does not seem to follow a pattern at all. Following is a graph of the first 5000 values of the number of iterations needed to "cycle around" a string of length n vs n.

• If the individual characters in a string are examined as the string is iterated, a pattern emerges of how the characters move. For example, consider the string "0a0000000000000". If the algorithm is applied to "0a0000000000000" and the position of 'a' is tracked, the following cycle emerges:

  

  This cycle of character positions remains constant (just shifted), no matter what the starting position of the character is:

  

  No matter what the starting position is, for a string of length 15 (as this one is), the cycle will be

$$1 → 2 → 4 → 8 → 13 → 3 → 6 → 12 → 5 → 10 → 9 → 11 → 7 → 14 → 1 → … $$

All of these things considered, I have two questions about this algorithm. Is it possible to determine what the length of the cycle will be given the length of the string? And is it possible to determine the position of a character after an iteration is applied given the current position and the length of the string? I can provide additional data and/or programs to calculate this data if it is needed.

Answer 1

The first element stays in position $0$, obviously. So let us just consider what happens to the remaining $m=n-1$ elements. Those move around positions $1,2,...,m$ in some patterns depending on the value of $m$.

• If $i\leq m/2$ we have $i\mapsto 2i$
• If $i>m/2$ we have $i\mapsto 2(m-i)+1$

So for instance for $n=8$ thus $m=7$ we have your algorithm as the permutation: $$ \sigma=\begin{pmatrix} 0&1&2&3&4&5&6&7\\ 0&2&4&6&7&5&3&1 \end{pmatrix}=(1\ 2\ 4\ 7)(3\ 6) $$ which has order $\operatorname{lcm}(4,2)=4$. We see how the even numbers less than $m$ appear in order in the left half of the bottom row whereas the odd numbers appear in reversed order in the right half.

---

Right now I do not know the reason for the cycle lengths in the cycle decomposition of those permutations, but maybe I will get back to it later on.

---

From what I have tested so far, the order of this permutation for a given $n$ appears to equal the order of the cycle containing $1$. BTW if $n=2^k$ or $2^k+1$ the order of this cycle is always $k$, which is not hard to prove.

Answer 2

We use the concept of symmetric groups (in the case when all characters are distinct).

If the string is $n$ characters long, we use the symmetric group $S_n$.

Each operation on the string is some element $\sigma\in S_n$, which only depends on $n$. This element can be computed in linear time.

Finding how many times required before getting the original string is the same as finding the order of $\sigma$, which can be done in linear time. It is possible to get the order by taking the lowest common multiple of the disjoint cycles.

For example, when $n=4$, $$\sigma=(2, 3, 4)$$ and the order is 3.

If we store $\sigma$ as such:

$$\sigma=\left(\begin{matrix}1&2&3&4\\1&3&4&2\end{matrix}\right)$$

we can directly get the next position of the current character.

There seems to be an interesting thing your graph is showing: that the order of this permutation is at most $n-1$.