7
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Already given answer being good i wil add another (more recent) reference here:

A New Method for Generating Permutations in Lexicographic Order, by TING KUO (2009)

proposes a method to generate, rank and unrank permutations in lexicographic order, plus a few new features like generate a permutation which is a given distance away from another permutation.

Complexity is again of the $O(nlgn)$ order

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I don't understand how this answers the question. The question says the OP already knows of $O(n \lg n)$ time algorithms, and is asking about $O(n)$ algorithms. So, mentioning an $O(n \lg n)$ time algorithm is not answering the question. $\endgroup$ – D.W. Apr 8 '15 at 21:57
  • $\begingroup$ @D.W., the answer exactly answers your comment. it is added as extra (and newer) reference. Plus the already upvoted answer also gives O(nlgn) solution for lexicographic ordering. there is no known algorithm for linear time lexicographic ordering (at least up to now). So the OP can have access to approximations anmd newer apporoaches, hopefully jimself may develop such an algorithm. Kindly remove the downvote please $\endgroup$ – Nikos M. Apr 8 '15 at 22:04
  • $\begingroup$ I still don't see how it answers my comment. Assume the other answer didn't exist (as it is irrelevant for these purposes). How does your answer answer the question that was asked? Take a look at the question again, and then your answer. The question specifically says it does not want an $O(n \lg n)$ time algorithm (the author already knows of $O(n \lg n)$ time algorithms), so how does telling the OP about an $O(n \lg n)$ time algorithm answer the question? $\endgroup$ – D.W. Apr 9 '15 at 0:25
  • $\begingroup$ @D.W., too bad, it seems your reputation is wasted on you, already answered, in any case let OP dcide. Again a similar anser has been given and is upvoted several times. There is no known algorithm for linear time lexicographic ordering. These are approximations (under certain conditions) which the OP may use or even help her derive her own algorithm. This is science after all even good approximations can be very helpful and references to these solutions. i hope you grant me that right $\endgroup$ – Nikos M. Apr 9 '15 at 10:31
  • $\begingroup$ Stating that "There is no known linear time algorithm" would be an answer... but that's not present anywhere in your answer. One can only judge your answer based on what is written in it. (That said, I do recognize that that claim is already made in Yuval's answer, so it's not clear that it would contribute a lot to add another re-statement of that.) $\endgroup$ – D.W. Apr 9 '15 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.