1

I'd like to directly use a rank-number to calculate the Lehmer code that corresponds to an nPk permutation. My goal is to subdivide the ranking-space for purposes of a parallel search. My background in combinatorics-theory is presently very light.

I've found that I can convert the rank-number to a factoradic-number for the purpose of extracting the first k symbols using the Lehmer code, but I have found no proof that this is a reliable way to go. To do this I'm using the formula:

$\text {factoradic} = \text{rank} * ( n - k )! + ( n! - k! ) * ( k - 1 )!$

For smaller nPk my results seem ok but for larger nPk it is difficult to check.

Is there a proof that this (or some other) formula actually works to convert from rank to a factoradic?

Edit1

Apologies for some terminology that may be incorrect and / or a confusing question.

Any links or insights into enumerating lexiographic arrangements of nPk would be most welcome.

Edit2

Perhaps my question is a duplicate.

Community
  • 1
  • 1
    In addition to NP2P's answer, I'll note that volume 4 of Knuth's Art of Computer Programming covers this in detail; in particular, chapter 7.2.1.2 is devoted specifically to generating all permutations (and includes efficient algorithms for conversion given an index). – Steven Stadnicki Sep 27 '16 at 17:11
  • @steven-stadnicki: Thanks for the tip. I don't own that book - but I did find a pre-print version of that chapter online. However, it seems that the chapter focuses on 'complete permutations' of n-tuples - with emphasis on permuting lexiographic orderings. There doesn't seem to be material on using or calculating rank number of a partial permutation... Is there a specific section in that chapter I should be examining more closely? –  Sep 28 '16 at 20:43

0 Answers0