• Check out Factoradic Numbers.
  • Look at Permutation Encoding in .Net
  • I need to read Computing Permutation Encodings
  • details below borrowed from Large-Scale Parallel Breadth-First Search
    Problems such as the sliding-tile puzzles and Rubik’s Cube are permutation problems, in that a state represents a permutation of elements. The simplest representation of a permutation is to list the position of each element. For example, a Fifteen Puzzle state can be represented as a 16-digit hexadecimal number, where each digit represents the position of one tile or the blank. This occupies 64 bits of storage.
    A more efficient encoding saves storage and reduces I/O time. Ideally, we would map a permutation of n elements to a unique integer from zero to n!􀀀1. For the Fifteen Puzzle, this requires only 45 bits. For example, we could map each permutation to its index in a lexicographic ordering of all such permutations. For permutations of three elements, this mapping is: 012–0, 021–1, 102–2, 120–3, 201–4, 210–5.
    An algorithm for this mapping starts with a sequence of positions, and maps it to a number in factorial base, of the form: dn􀀀1  (n􀀀1)!+dn􀀀2  (n􀀀2)!+  +d2  2!+d1  1! Digit di can range from 0 to i 􀀀 1, resulting in a unique representation of each integer. Given a permutation as a sequence of digits in factorial base, we perform the indicated arithmetic operations to compute the actual integer value.
    To map a permutation to a sequence of factorial digits, we subtract from each element the number of original elements to its left that are less than it. For example, the mapping from permutations of three elements to factorial base digits is: 012–000, 021–010, 102–100, 120–110, 201–200, 210–210. By reducing these factorial digits to an integer, we obtain the desired values: 012–000–0, 021–010–1, 102–100–2, 120–110–3, 201–200–4, 210–210–5.
    This algorithm takes O(n2) time to compute the digits in factorial base. Next we provide an O(n) algorithm.
    We scan the permutation from left to right, constructing a bit string of length n, indicating which elements of the permutation we’ve seen so far. Initially the string is all zeros. As each element of the permutation is encountered, we use it as an index into the bit string and set the corresponding bit to one. When we encounter element k in the permutation, to determine the number of elements less than k to its left, we need to know the number of ones in the first k bits of our bit string. We extract the first k bits by right shifting the string by n 􀀀 k. This reduces the problem to: given a bit string, count the number of one bits in it.
    We solve this problem in constant time by using the bit string as an index into a precomputed table, containing the number of ones in the binary representation of each index. For example, the initial entries of this table are: 0–0, 1–1, 2–1, 3–2, 4–1, 5–2, 6–2, 7–3. The size of this table is O(2n􀀀1) where n is the number of permutation elements. Such a table for the Fifteen Puzzle would contain 32768 entries.
    This gives us a linear-time algorithm for mapping permutations of n elements in lexicographic order to unique integers from zero to n!􀀀1. We implemented both the quadratic and linear algorithms above, and tested them by mapping all permutations of up to 14 elements. For 14 elements, the linear algorithm was seven times faster, and this ratio increases with increasing problem size, as expected.