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 create LehmerCode() 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
|
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:
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 factoradicsystem.
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 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
Tidak ada komentar:
Posting Komentar