quixote@athena.mit.edu (Daniel Tunkelang) (11/15/90)
Perhaps this has been answered here once before, but is there a known lower bound on generating the kth permutation in lexicograhic order of the numbers 1..n. I.E. the permutations of 1..3 in order are: (1 2 3), (1 3 2), (2 1 3), (2 3 1), (3 1 2), (3 2 1), so the 4th of these would be (2 3 1). I don't care whether you want to label these 0 through (n! - 1) or 1 through n!; what I want to know is if the upper bound of O (n log n) that I have found (using rank-ordered trees) to solve this problem is in fa ct a lower bound. I am equally curious to know a lower bound for the inverse problem: given n and a permutation, what is the permutation's rank. I know how to solve both in O (n log n) time, but cannot prove a nontrivial lower bound on either problem. Please post or reply to quixote@athena.mit.edu. Thanks, -- Daniel Tunkelang (quixote@athena.mit.edu)