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)