Black lives matter

(Ad, please don’t block)

This blog post explores the Lehmer code, a way of mapping integers to permutations. It can be used to compute a random permutation (by computing a random integer and mapping it to a permutation) and more.

[ 'a', 'b', 'c' ]All of its permutations are:

[ 'a', 'b', 'c' ] [ 'a', 'c', 'b' ] [ 'b', 'a', 'c' ] [ 'b', 'c', 'a' ] [ 'c', 'a', 'b' ] [ 'c', 'b', 'a' ]

var arr = [ 'a', 'b', 'c' ];A simple way of computing a random permutation of

- Compute a random number
`i`, 0 ≤`i`< 3.`arr[i]`is the first element of the permutation. Remove element`i`from`arr`. - Compute a random number
`i`, 0 ≤`i`< 2.`arr[i]`is the second element of the permutation. Remove element`i`from`arr`. - The remaining element of
`arr`is the last element of the permutation.

/** * @returns a number 0 <= n < upper */ function getRandomInteger(upper) { return Math.floor(Math.random() * upper); }Furthermore, we don’t want to change the input array

/** * @returns a fresh copy of arr, with the element at index removed */ function removeElement(arr, index) { return arr.slice(0, index).concat(arr.slice(index+1)); }The algorithm itself looks as follows:

function createPermutation(arr) { if (arr.length === 0) { return []; } var index = getRandomInteger(arr.length); return [arr[index]].concat( createPermutation( removeElement(arr, index))); }Interaction:

> createPermutation([ 'a', 'b', 'c' ]) [ 'a', 'c', 'b' ]Note:

- Compute the indices for the (continually shrinking) array
`arr`. - Turn the indices into a permutation.

function createLehmerCode(len) { var result = []; for(var i=len; i>0; i--) { result.push(getRandomInteger(i)); } return result; }Interaction:

> createLehmerCode(3) [ 0, 1, 0 ]The above way of encoding a permutation as a sequence of numbers is called a Lehmer code. Such a code can easily be converted into a permutation, via the following function (step 2):

function codeToPermutation(elements, code) { return code.map(function (index) { var elem = elements[index]; elements = removeElement(elements, index); return elem; }); }Interaction:

> codeToPermutation(['a','b','c'], [0,0,0]) [ 'a', 'b', 'c' ] > codeToPermutation(['a','b','c'], [2,1,0]) [ 'c', 'b', 'a' ]

**The decimal system.**
For example, if each digit is in the range 0–9 then we can use the fixed radix 10 and the decimal system. That is, each digit has the same radix. “Radix” is just another way of saying “upper bound of a digit”. The following table reminds us of the decimal system.

Digit position | 2 | 1 | 0 |

Digit range | 0–9 | 0–9 | 0–9 |

Multiplier | 100 = 10^{2} |
10 = 10^{1} |
1 = 10^{0} |

Radix | 10 | 10 | 10 |

The value of a position is the value of the digit multiplied by the multiplier. The value of a complete decimal number is the sum of the values of the positions.

Note that each multiplier is one plus the sum of all previous highest digits multiplied by their multipliers. For example:

100 = 1 + (9x10 + 9x1)

**The factoradic system.**
Encoding the digits of a Lehmer code into an integer is more complex, because each digit has a different radix. We want the mapping to be bijective (a one-to-one mapping without “holes”). The factoradic system is what we need, as explained via the following table. The digit ranges reflect the rules of the Lehmer code.

Digit position | 3 | 2 | 1 | 0 |

Digit range | 0–3 | 0–2 | 0–1 | 0 |

Multiplier | 6 = 3! | 2 = 2! | 1 = 1! | 1 = 0! |

Radix | 4 | 3 | 2 | 1 |

The last digit is always zero and often omitted. Again, a multiplier is one plus the highest value that you can achive via previous positions. For example:

6 = 1 + (2x2 + 1x1 + 0x1)The following function performs the mapping from integers to Lehmer codes.

function integerToCode(int, permSize) { if (permSize <= 1) { return [0]; } var multiplier = factorial(permSize-1); var digit = Math.floor(int / multiplier); return [digit].concat( integerToCode( int % multiplier, permSize-1)); }We start with the highest position. Its digit can be determined by dividing

`integerToCode()` uses the following function to compute the factorial of a number:

function factorial(n) { if (n <= 0) { return 1; } else { return n * factorial(n-1); } }

function createPermutation(arr) { var int = getRandomInteger(factorial(arr.length)); var code = integerToCode(int); return codeToPermutation(arr, code); }The range of the random integer representing a permutation is [0,

- Computing a random permutation: the Fisher–Yates shuffle
- Enumerating all permutations: the Steinhaus–Johnson–Trotter algorithm