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.
Permutations
A permutation of an array is an array that contains the same
elements, but possibly in a different order. For example, given the array
[ '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' ]
Computing a permutation: a naive solution
In order to motivate the Lehmer code, let’s first implement
a naive algorithm for computing a permutation of an array. Given the following
array arr.
var arr = [ 'a', 'b', 'c' ];
A simple way of computing a random permutation of arr is:
- 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.
In order to
implement the above algorithm, we need a function to compute a random integer
in a range starting at 0, up to and excluding an upper bound upper. The following function
performs that duty.
/**
* @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 arr, which means that we need
a function that non-destructively removes an element:
/**
* @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: createPermutation()
could be implemented more efficiently, but the current implementation expresses
our intentions very clearly.
Encoding permutations as integers
An alternative to the above algorithm is to find a way to
map single integers to permutations. We can then simply compute a random
integer and map it to a permutation.
The naive algorithm in two steps
As a first step towards this new approach, lets first split
up the previous algorithm into two steps:
- Compute the indices for the (continually shrinking) array arr.
- Turn the indices into a permutation.
The
following function performs step 1. We don’t need to know anything about arr, except for its length len. The first index of the
returned array is in the range [0,len), the second in the range [0,len−1), etc.
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' ]
Mapping integers to Lehmer codes
The next step is to replace createLehmerCode() by a function that maps an
integer to a Lehmer code. Afterwards, we compute that integer randomly and not
the code itself, any more. To that end, lets look at ways of encoding sequences
of digits (e.g. indices) as single integers. If each of the digits has the same
range, we can use a positional
system whose radix is the (excluded) upper bound of the range.
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 = 102
|
10 = 101
|
1 = 100
|
Radix
|
10
|
10
|
10
|
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
|
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 int
by the position’s multiplier. Afterwards the remainder of that division becomes
the new int and we
continue with the next position.
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);
}
}
Putting everything together
We now have all the pieces to compute a permutation as
originally planned:
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,arr.length).
That is an indication that the mapping between integers and permutations is
really bijective, because arr
has arr.length!
permutations,
Practically useful?
Is the Lehmer code practically useful? It is if you need to
encode permutations as integers. There are two additional use cases for it:
Computing a random permutation and enumerating all permutations. For both use
cases, Lehmer codes give you convenient solutions, but not efficient ones. If
you want efficiency, consider the following two algorithms:
- Computing a random permutation: the Fisher–Yates shuffle
- Enumerating all permutations: the Steinhaus–Johnson–Trotter algorithm
0 komentar:
Post a Comment