In combinatorics and computer science, the task of converting between permutations and integers represents a fundamental operation. This topic covers fast algorithms for mapping permutations to numbers and vice versa, useful in applications like combinatorial enumeration, cryptographic systems, and efficient data storage. This article delves into the technical underpinnings of these algorithms, providing examples and a summary table for clarity.

Permutations and Factorial Number System

A permutation of a set is a rearrangement of its elements. For a set $S = {1, 2, ..., n}$, there are $n!$ (n factorial) possible permutations. The factorial number system or factoradics provides a powerful framework for mapping permutations to numbers.

Factorial Number System

In the factorial number system, numbers are expressed in terms of factorials. For a number $X$ in the base-$n!$ system:

$X = a_{n-1} \cdot (n-1)! + a_{n-2} \cdot (n-2)! + \ldots + a_1 \cdot 1! + a_0 \cdot 0!$

where $0 \leq a_i \leq i$. This representation is unique, just like binary or decimal systems, but it is based on factorials rather than powers of a base.

Permutation -> Number Mapping

Algorithmically, converting a permutation to a number requires determining the factoradic representation. Suppose we have a permutation $\pi = [\pi_1, \pi_2, \ldots, \pi_n]$.

Here's an example with $n = 4$, $\pi = [3, 1, 4, 2]$:

1. Determine the Position: For each element $\pi_i$, count the number of elements in the remaining list that are smaller. This count gives you the corresponding factoradic digit.
   • For $\pi_1 = 3$: there are 2 fewer elements ${1, 2}$; hence $d_1 = 2$.
   • For $\pi_2 = 1$: there are 0 fewer elements; hence $d_2 = 0$.
   • For $\pi_3 = 4$: there is 1 fewer element ${2}$; hence $d_3 = 1$.
   • For $\pi_4 = 2$: there are 0 fewer elements; hence $d_4 = 0$.
2. Calculate the Factoradic: Use these $d_i$ values:
   • $\text{Number} = 2 \cdot 3! + 0 \cdot 2! + 1 \cdot 1! + 0 \cdot 0! = 12 + 0 + 1 + 0 = 13$

Number -> Permutation Mapping

To convert a number back to a permutation, reverse the process using successive divisions:

1. Initialize: Take number $N$ and for set ${1, 2, ..., n}$, iteratively determine each position.
2. Determine Factoradic Digits: For each factorial term $k!$, determine $a_k = \lfloor \frac{N}{k!} \rfloor$ and update $N \leftarrow N \bmod k!$.
3. Construct Permutation: Starting with a sorted list of $n$ numbers, choose elements based on factoradic digits $a_k$, removing each chosen element from the list.

Using $13$ as an example:

1. $13 \div 3! = 2$ R $1$ (choose 3rd smallest, remove ${3}$, result ${1, 2, 4}$)
2. $1 \div 2! = 0$ R $1$ (choose 1st smallest, remove ${1}$, result ${2, 4}$)
3. $1 \div 1! = 1$ R $0$ (choose 2nd smallest, remove ${4}$, result ${2}$)
4. ${2}$ remains

Permutation $\pi = [3, 1, 4, 2]$.

Key Takeaways

To summarize the mapping operations from permutations to numbers and numbers to permutations efficiently:

Applications and Further Considerations

Fast permutation-number mapping algorithms are crucial in generating permutations efficiently, which is essential in simulation models, combinatorial game theory, and cryptographic systems. This representation enables easy ranking and unranking of permutations, extending their utility significantly.

These algorithms also enable memory-efficient data types in programming environments, with numerous libraries implementing them. Utilizing these allows for significant performance improvements in situations where handling and manipulating large datasets of permutations is necessary.

By mastering these conversions between numeric and permutation representations, developers can harness the full power of combinatorial operations in efficient and elegant ways.