[comp.theory] <None>

quixote@athena.mit.edu (Daniel Tunkelang) (11/16/90)

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)

cip@umiami.ir.miami.edu (06/14/91)

Hi. 
I need an efficient algorithm to generate all (n-1)! cyclic permutations
of first n integers. I would appreciate any information on references or
ideas. Thanks in advance.
Zeynep Serifsoy (zserifso@coegld.eng.miami.edu)