Search code examples
performancealgorithmpermutationcombinatoricsfactorial

Calculating a Permutation with Repetitions of Lexigraphic

I have a question concerning combinatorics, specifically permutations and lexigraphic indexing. I have calculated a permutation of a set given a lexigraphic index in the past, but these were permutations without repetition.

Now I would like to calculate the permutation of given lexigraphic index with repetitions. My problem is I don't know how to approach the lexigraphic indexing of permutations with repetition.

Suppose I have the following set of elements" {A,B,C,D,E,F,G,H}

I would like to calculate the permutation of 20 of these elements with lexigraphic index of n; n being 64 bit number. How do I determine the lexigraphic indexing? Can I still use a factorial base approach?

Solution

  • Suppose you have 8 elements (like in your example), which means you need 3 bits for index. To define permutation of length 20 you need 3*20=60 bits.

    So integer values v from [0,2^60) will define all permutations with repeats, where v & 7 will be the index of first item in the permutation, (v & (7 << 3) >> 3) - index on the second element, and so forth ...