Algorithm for finding numerical permutation given lexicographic index
I am looking for an algorithm that given a set of numbers (for example 1 2 3) and an index (for example 2) will get me the second permutation of those numbers according to a lexicographic order. For example in this case the algorithm will return 1 3 2.
Solution 1:
Here is a sample solution in Scala, which I will explain in detail:
/**
example: index:=15, list:=(1, 2, 3, 4)
*/
def permutationIndex (index: Int, list: List [Int]) : List [Int] =
if (list.isEmpty) list else {
val len = list.size // len = 4
val max = fac (len) // max = 24
val divisor = max / len // divisor = 6
val i = index / divisor // i = 2
val el = list (i)
el :: permutationIndex (index - divisor * i, list.filter (_ != el)) }
Since Scala isn't that well known, I think I have to explain the last line of the algorithm, which is, apart from that, pretty self explanatory.
el :: elist
constructs a new list from an element el and an list elist. Elist is a recursive call.
list.filter (_ != el)
is just the list without the element el.
Test it exhaustively with a small List:
(0 to fac (4) - 1).map (permutationIndex (_, List (1, 2, 3, 4))).mkString ("\n")
Test the speed of a bigger List with 2 examples:
scala> permutationIndex (123456789, (1 to 12).toList)
res45: List[Int] = List(4, 2, 1, 5, 12, 7, 10, 8, 11, 6, 9, 3)
scala> permutationIndex (123456790, (1 to 12).toList)
res46: List[Int] = List(4, 2, 1, 5, 12, 7, 10, 8, 11, 9, 3, 6)
The result appears immediately on a 5 years old laptop. There are 479 001 600 permutations for a List of 12 elements, but with 100 or 1000 elements, this solution should still work fast - you just would need to use BigInt as Index.
How does it work? I made a graphic, to visualize the example, a List of (1, 2, 3, 4) and an index of 15:
A List of 4 Elements produces 4! permutations (=24). We choose an arbitrary index from 0 to 4!-1, let's say 15.
We can visualize all permutations in a tree, with the first node from 1..4. We divide 4! by 4 and see, that every first-node leads to 6 subtrees. If we divide our index 15 by 6, the result is 2, and the value in our zero-based List with index 2 is 3. So the first Node is 3, and the rest of our List is (1, 2, 4). Here is a table, showing how 15 leads to the element with index 2 in the Array/List/whatever:
0 1 2 3 4 5 | 6 ... 11 | 12 13 14 15 16 17 | 18 ... 23
0 | 1 | 2 | 3
| | 0 1 2 3 4 5 |
We now subtract 12, the first element of the cell (12...17) for the last 3 elements, which have 6 possible permutations, and see, how 15 maps to 3. Number 3 leads to the array index 1 now, which was element 2, so the result so far is List (3, 2, ...).
| 0 1 | 2 3 | 4 5 |
| 0 | 1 | 3 |
| 0 1 |
Again, we subtract 2, and end in 2 remaining elements with 2 permutations, and index (0, 3), mapping to the values (1, 4). We see, that the second element, belonging to the 15 from top, maps to value 3, and the remaining element for the last step is the other one:
| 0 | 1 |
| 0 | 3 |
| 3 | 0 |
Our result is List(3, 2, 4, 1) or the indexes (2, 1, 3, 0). Testing all indexes in order shows, that they yield all permutations in order.
Solution 2:
Here is a simple solution:
from math import factorial # python math library
i = 5 # i is the lexicographic index (counting starts from 0)
n = 3 # n is the length of the permutation
p = range(1, n + 1) # p is a list from 1 to n
for k in range(1, n + 1): # k goes from 1 to n
f = factorial(n - k) # compute factorial once per iteration
d = i // f # use integer division (like division + floor)
print(p[d]), # print permuted number with trailing space
p.remove(p[d]) # delete p[d] from p
i = i % f # reduce i to its remainder
Output:
3 2 1
The time complexity is O(n^2) if p is a list, and O(n) amortized if p is a hash table and factorial is precomputed.
Solution 3:
Link to article mentioned: http://penguin.ewu.edu/~trolfe/#Shuffle
/* Converting permutation index into a permutation
* From code accompanying "Algorithm Alley: Randomized Shuffling",
* Dr. Dobb’s Journal, Vol. 25, No. 1 (January 2000)
* http://penguin.ewu.edu/~trolfe/#Shuffle
*
* Author: Tim Rolfe
* [email protected]
* http://penguin.ewu.edu/~trolfe/
*/
#include <stdio.h>
#include <stdlib.h>
// http://stackoverflow.com/questions/8940470/algorithm-for-finding-numerical-permutation-given-lexicographic-index
// Invert the permutation index --- generate what would be
// the subscripts in the N-dimensional array with dimensions
// [N][N-1][N-2]...[2][1]
void IndexInvert(int J[], int N, int Idx)
{ int M, K;
for (M=1, K=N-1; K > 1; K--) // Generate (N-1)!
M *= K;
for ( K = 0; M > 1; K++ )
{ J[K] = Idx / M; // Offset in dimension K
Idx = Idx % M; // Remove K contribution
M /= --N; // next lower factorial
}
J[K] = Idx; // Right-most index
}
// Generate a permutation based on its index / subscript set.
// To generate the lexicographic order, this involves _shifting_
// characters around rather than swapping. Right-hand side must
// remain in lexicographic order
void Permute (char Line[], char first, int N, int Jdx[])
{ int Limit;
Line[0] = first;
for (Limit = 1; Limit < N; Limit++)
Line[Limit] = (char)(1+Line[Limit-1]);
for (Limit = 0; Limit < N; Limit++)
{ char Hold;
int Idx = Limit + Jdx[Limit];
Hold = Line[Idx];
while (Idx > Limit)
{ Line[Idx] = Line[Idx-1];
Idx--;
}
Line[Idx] = Hold;
}
}
// Note: hard-coded to generate permutation in the set [abc...
int main(int argc, char** argv)
{ int N = argc > 1 ? atoi(argv[1]) : 4;
char *Perm = (char*) calloc(N+1, sizeof *Perm);
int *Jdx = (int*) calloc(N, sizeof *Jdx);
int Index = argc > 2 ? atoi(argv[2]) : 23;
int K, Validate;
for (K = Validate = 1; K <= N; K++)
Validate *= K;
if (Index < 0 || Index >= Validate)
{ printf("Invalid index %d: %d! is %d\n", Index, N, Validate);
return -1; // Error return
}
IndexInvert(Jdx, N, Index);
Permute (Perm, 'a', N, Jdx);
printf("For N = %d, permutation %d in [0..%d] is %s\n",
N, Index, Validate-1, Perm);
return 0; // Success return
}