Extended Josephus permutations generated by keyword

Question

The (well known) generalized Josephus algorithm consists in starting from the ordered set $Z_n=\{1,2,...,n\}$, and choosing and removing cyclically from left to right each m-th element until the set is exhausted. This produces a new ordered set $Z_n(m)= \{a1,a2, ... an\}$ which is a permutation of $Z_n$.

I am facing an extension of this algorithm where m is not constant but taken cyclically from a set of k values M = $\{m_1,m_2,...,m_k\}$ with $0 < m_i \le n$.
M is the keyword.
The resulting permutation is used in a cipher encryption scheme.
In my case, n = 26 and k = |M| = 7.
This means that $m_1$ to $m_5$ are used 4 times, $m_6$ and $m_7$ are used 3 times.

I have Googled the Josephus problem but could not find any paper about such an "extension".

Clearly the number of permutations that can be built is $n^k = 26^7$ (in theory).

However, I wonder if any of these questions may have an answer:

1. Can two different keywords produce the same permutation ? (in other words, is the "key-space" really equal to $26^7$, or smaller ?)
2. How can I assess that a given permutation among the 26! of $Z_{26}$ has been built with this algorithm ?

3. Suppose I know 7 elements of the resulting permutation, one in each of the 7 'columns' obtained by writing the permutation from left to right across 7 columns:

   . x . . . . x  
   . . . x x . .  
   . . x . . x .  
   x . . . .  
   

   where the dot is an unknown element of the permutation, and x is a known element.

   Is it possible to find/calculate the missing elements and build the complete permutation ?

Thank you for your advice.

Answer 1

1.

For your particular values of $n=26,k=7$: each distinct set $M$ will produce a distinct permutation. Let $M=\{m_1,\ldots,m_7\},\;N=\{n_1,\ldots,n_7\},\;$ be two distinct "keys". For them to produce the same permutation, we need:

\begin{align} n_1 &= m_1 \\ n_2 &\equiv m_2\pmod{n-1} \qquad\qquad\text{(i.e. $n_1=m_1$ OR $m_1=1,n_1=26$ OR $m_1=26,n_1=1$)} \\ n_3 &\equiv m_3\pmod{n-2} \\ n_4 &\equiv m_4\pmod{n-3} \\ n_5 &\equiv m_5\pmod{n-4} \\ n_6 &\equiv m_6\pmod{n-5} \\ n_7 &\equiv m_7\pmod{n-6} \\ & \\ n_1 &\equiv m_1\pmod{n-7} \\ n_2 &\equiv m_2\pmod{n-8} \\ n_3 &\equiv m_3\pmod{n-9} \\ n_4 &\equiv m_4\pmod{n-10} \\ n_5 &\equiv m_5\pmod{n-11} \\ n_6 &\equiv m_6\pmod{n-12} \\ n_7 &\equiv m_7\pmod{n-13}. \end{align}

It's clear that for $n=26,\;k=7$, this is not possible. For other settings it will be possible, moreso when $k$ is closer to $n$ so that each $m_i$ is not re-used so much (or at all if $k=n$).

2.

This can be done by testing each item in the resultant permutation in turn. It may be best to show via specific example. Say our key is $M=\{m_1,\ldots,m_7\}$ and our permutation is $\{5,6,19,21,8,11,22,1,13,4,18,12,16,7,\ldots\}$. Then,

\begin{align} a_1=5 &\implies m_1=5 \\ a_2=6 &\implies m_2\in\{1,26\} \text{ then } a_8=1,a_9=13\implies m_2=26 \\ & \qquad \text{(walk around $26$ steps jumping over $5,6,19,21,8,11,22,1$ gets us to $13$)} \\ a_3=19 &\implies m_3=13 \\ a_4=21 &\implies m_4\in\{2,25\} \text{ then } a_{10}=4,a_{11}=18\implies m_4=25 \\ & \qquad \text{(walk around $25$ steps jumping over $5,6,19,21,8,11,22,1,13,4$ gets us to $18$)} \\ a_5=8 &\implies m_5=11 \\ a_6=11 &\implies m_6=3 \\ a_7=22 &\implies m_7=9. \end{align}

If at any step you get a contradiction so that no such $m_i$ value works, for any $i=2,\ldots,7$, then you know the given permutation is not producible.

Once you establish all of $M$, then check that it does in fact produce all the remaining items in the given permutation.

3.

This is not always possible. A counter-example: if we know the very first $7$ values to be $\{5,6,8,11,15,20,26\}$ then $M$ could be any of the following:

\begin{align} & \{5,1,2,3,4,5,6\} \\ & \{5,26,2,3,4,5,6\} \\ & \{5,1,26,3,4,5,6\} \\ & \{5,26,26,3,4,5,6\} \\ & \text{etc.} \\ \end{align}