Xref: utzoo sci.math:13436 comp.theory:1219 Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!mit-eddie!bloom-beacon!athena.mit.edu!quixote From: quixote@athena.mit.edu (Daniel Tunkelang) Newsgroups: sci.math,comp.theory Subject: Re: kth permutation Keywords: permutation, lexicographic order Message-ID: <1990Nov14.175544.27872@athena.mit.edu> Date: 14 Nov 90 17:55:44 GMT References: <12982@chaph.usc.edu> <1990Nov13.162429.3509@cunixf.cc.columbia.edu> <1990Nov13.165449.6440@cunixf.cc.columbia.edu> Sender: daemon@athena.mit.edu (Mr Background) Reply-To: quixote@athena.mit.edu (Daniel Tunkelang) Organization: Massachusetts Institute of Technology Lines: 9 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)