patternMinor
Given a permutation of 0..N-1, determine the index of that permutation in the lexicographic ordering of all permutations of 0..N-1, in linear time
Viewed 0 times
indexlinearthelexicographicallorderingtimethatdeterminepermutation
Problem
There are various $\mathcal O(n \log n)$ or worse solutions, but I'm looking for one that runs in $\mathcal O(n)$, or a proof that none exist.
Solution
The 2007 paper Linear-time ranking of permutations gives a linear time ranking algorithm for the lexicographic order, assuming arithmetic on numbers of length $O(n\log n)$ takes constant time.
The 2001 paper Ranking and unranking permutations in linear time presents a linear time ranking algorithm not requiring fast arithmetic on large numbers, but not for the lexicographic order. Regarding the latter, it states
The whole problem of ranking permutations in lexicographic order seems inextricably intertwined with
the problem of computing the number of inversions
in a permutation, and it seems that a major breakthrough will be required to do that computation in linear time, if indeed it it possible at all.
On the other hand, it does mention an $O(n\log n/\log\log n)$ algorithm for ranking permutations in lexicographic order due to Dietz.
The 2001 paper Ranking and unranking permutations in linear time presents a linear time ranking algorithm not requiring fast arithmetic on large numbers, but not for the lexicographic order. Regarding the latter, it states
The whole problem of ranking permutations in lexicographic order seems inextricably intertwined with
the problem of computing the number of inversions
in a permutation, and it seems that a major breakthrough will be required to do that computation in linear time, if indeed it it possible at all.
On the other hand, it does mention an $O(n\log n/\log\log n)$ algorithm for ranking permutations in lexicographic order due to Dietz.
Context
StackExchange Computer Science Q#30274, answer score: 9
Revisions (0)
No revisions yet.