Mapping from $\{1,\ldots,n!\}$ to the symmetric group $S_n$

Question

Is there an easy known bijective mapping formula between the set $\{1,\ldots,n!\}$ and the symmetric group $S_n$? I want to pick a number $k \in \{1,\ldots ,n!\}$ and assign a unique permutation of $(1,\ldots, n)$ to it.

Numbering the transpositions generating $S_n$ doesn't help, since they can occur multiple times and don't commute. Maybe the permutation matrices (in every column and row exactly one 1 and 0 elsewhere) could give a hint, but I don't see the solution.

Context: I want to simulate a certain probability distribution on the symmetric group. It's easy to pick random integer numbers. So easy mapping a random number to a permutation is left.

Answer 1

Yes there is an easy and well known such bijection, although as happens so often (that I don't understand why people don't just get into the habit) it becomes easier if one starts counting at $0$, so that one is looking for a bijection between permutations of the set $[n]=\{\,i\in\Bbb Z \mid 0\leq i<n\,\}$ and the (similar) set $[n!]$. Using the factorial number system, a number of the latter set is represented as an $n$-tuple $[d_n,\ldots,d_1]$ with $d_i\in[i]$ (as is conventional the least significant digit it as the right), and this sequence can be mapped to a permutation using the Lehmer code. Both conversions are straightforward and easily computed in both directions, and combining them numbers the permutations in lexicographic ordering. Nonetheless the one between a permutation and its Lehmer code not quite as easily computed as one should like (it is not even $O(n\lg n)$ using any obvious data structure), which makes use of this mapping loose out against direct methods when it comes to efficient enumeration of permutations in lexicographic order. However, it would still be a method of choice if you want to store information about permutations in a tight linear array, and need to be able to look up the information associated to a given permutation rapidly.

Answer 2

See Generating all permutations by Donald E. Knuth.

Answer 3

Since we know that $S_{n}$ has $n!$ elements, you are really asking for a "natural" ordering on the the permutations in $S_{n}.$ Possibly the simplest way to do this is lexicographic ordering: given distinct permutations $\sigma$ and $\tau,$ set $\sigma > \tau$ if for some $i \leq n,$ we have $\sigma (i) > \tau(i)$ but $\sigma(j) = \tau(j)$ whenever $j <i.$ This lists the elements of $S_{n}$ in a strictly increasing order, with the identity permutation being the "smallest". The $i$-th permutation in the list should be assigned the number $i.$

Answer 4

For the sake of simplicity, I am providing a mapping from $\{0 \cdots (n! - 1)\}$ to the set of permutations of $\{0, 1, \cdots, (n-1)\}$. Please offset by 1 where required.

First of all, note that $n! = \sum_{i=1}^{n-1}i.i! + 1$ (can be easily proved by induction).

So for any number k in the range you provided, k - 1 can be written in the form

$k - 1 = \sum_{i=1}^{n-1}a_{i}i!$, where in each case $a_i$ is an integer from $[0, i]$.

Associate with k the permutation $p_{1}p_2p_3\cdots p_{n-1}p_n$ where $p_1$ = $a_1$, $p_2$ is the $a_2$th element in $\{0, 1, \ldots, {p_1-1}, {p_1+1}, \ldots (n-1)\}$, and so on.

You can easily see that a unique permutation is associated with each $k$ here.

EDIT: I went ahead and wrote the code. See this:

#!/usr/bin/python import sys def get_perm(n, k): """get permutation corressponding to random number. k < n!""" used = [False] * n fact_arr = [0] * n this_fact = 1 perm = [] for i in range(n): this_fact *= (i + 1) fact_arr[i] = this_fact k1 = k for i in range(n - 1): this_fact = fact_arr[n - 2 - i] p = k1 / this_fact k1 = k1 % this_fact p1 = p idx = 0 while p1 > 0 or used[idx]: if not used[idx]: p1 -= 1 idx += 1 perm.append(idx + 1) used[idx] = True for i in range(n): if not used[i]: perm.append(i + 1) break return perm def main(): perm = get_perm(int(sys.argv[1]), int(sys.argv[2]) - 1) print perm if __name__ == '__main__': main()

Now if I run, eg.

for i in \$(seq 1 6); do ./permutations.py 3 \$i; done

The output is:

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

Answer 5

Here's one way to define such a bijection by recursion on $n$:

• If $n=1$, use the only possible bijection.
• Let's say you've done it for $n$ and you want to move on to $n+1$. You've listed all $n!$ permutations of the first $n$ letters of the alphabet. Let's say $n=1\text{ gazillion}$ and the first $n$ letters of the alphabet are $A,\ldots, K$, and the $(n+1)$th letter is $L$. Write the first permutation on your list as the first $n$ letters in some order, thus: $$\bullet\bullet\bullet\cdots\bullet\bullet\bullet$$ and then make a list of $n+1$ new permutations by putting $L$ in each of the $n+1$ positions: $$\begin{array}{c} \bullet\bullet\bullet\cdots\bullet\bullet\bullet L \\ \bullet\bullet\bullet\cdots\bullet\bullet L \bullet \\ \bullet\bullet\bullet\cdots\bullet L\bullet\bullet \\ \bullet\bullet\bullet\cdots L\bullet\bullet\bullet \\ \vdots \\ \vdots \\ \bullet\bullet\bullet L\cdots\bullet\bullet\bullet \\ \bullet\bullet L\bullet\cdots\bullet\bullet\bullet \\ \bullet L\bullet\bullet\cdots\bullet\bullet\bullet \\ L\bullet\bullet\bullet\cdots\bullet\bullet\bullet \end{array}$$ Then do this with $\bullet\bullet\bullet\cdots\bullet\bullet\bullet$ as the second permutation of the $n$ letters (except this time let $L$ move from left to right), then with $\bullet\bullet\bullet\cdots\bullet\bullet\bullet$ as the third (with $L$ going from right to left), and so on. This method always goes from one permutation to the next by interchanging two adjacent letters.

  Concrete example: $$\begin{array}{l} \begin{array}{c} A \end{array} \\[12pt] \begin{array}{c} AB \\ BA \end{array} \\[12pt] \begin{array}{c} ABC \\ ACB \\ CAB \\ CBA \\ BCA \\ BAC \end{array} \\[12pt] \begin{array}{c} ABC\,D \\ AB\,D\,C \\ A\,D\,BC \\ D\,ABC \\[6pt] D\,ACB \\ A\,D\,CB \\ AC\,D\,B \\ ACB\,D \\[6pt] CAB\,D \\ CA\,D\,B \\ C\,D\,AB \\ D\,CAB \\[6pt] D\,CBA \\ C\,D\,BA \\ CB\,D\,A \\ CBA\,D \\[6pt] BCA\,D \\ BC\,D\,A \\ B\,D\,AC \\ D\,BAC \\[6pt] D\,BAC \\ B\,D\,AC \\ BA\,D\,C \\ BAC\,D \end{array} \end{array}$$ I think this recursive method may bear a standard name, but I don't remember it.

There is also something called a de Bruijn sequence.