Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!csun!nic.csu.net!csus.edu!wuarchive!zaphod.mps.ohio-state.edu!think.com!snorkelwacker.mit.edu!bloom-beacon!athena.mit.edu!quixote
From: quixote@athena.mit.edu (Daniel Tunkelang)
Newsgroups: comp.theory
Subject: <None>
Message-ID: <1990Nov16.020656.5100@athena.mit.edu>
Date: 16 Nov 90 02:06:56 GMT
Sender: daemon@athena.mit.edu (Mr Background)
Reply-To: quixote@athena.mit.edu (Daniel Tunkelang)
Organization: Massachusetts Institute of Technology
Lines: 16

I want to know if there is a non-trivial lower bound on the number of arithmetic
(NOT bit) operation needed to do either of the following:

1)  Given a positive integer n and an integer k between 1 and n!, find the kth
permutation in lexicographic order of the numbers 1 to n.

2)  Given a positive integer n and a permutation of the numbers 1 to n, find the
lexicographic rank k of that permutation.

I can do both in O (n log n) arithemetic operations, where each operation acts
on numbers of size O (log n) bits, and both have trivial lower bounds of Omega
(n).

Is there a better algorithm or a tighter lower bound?

-- Daniel Tunkelang (quixote@athena.mit.edu)