Chariphuk Chariphuk - 9 months ago 56
C++ Question

Kth permutation with specific number of value repetition

I'm looking for an algorithm which will return kth permutation of bool vector containing specific number of true and false values. And do so without generating all previous permutations like using c++ next_permutation(...).
For example I have 00011 and want 5th lexicographical permutation (01010).

Is there even any way to do so?

Full list of permutations containing 2x true and 3x false:

  1. 00011

  2. 00101

  3. 00110

  4. 01001

  5. 01010

  6. 01100

  7. 10001

  8. 10010

  9. 10100

  10. 11000

I googled a lot different algorithms for generating permutations, but none for kth permutation with specific number of repeated elements.

Thank you for any advice :)

Answer Source

It's easy to produce the bits one at a time, if you have a source of binomial coefficients. (Since the numbers involved are small -- we know k fits into an unsigned integer type -- the possible binomial coefficients could be precomputed.)

Now, consider the case where we need to produce n0 zeros and n1 ones. The number of possible valid bit sequences is (n0+n1)Cn1 (where nCk is the binomial coefficient), since there are n0 + n1 positions at which the n1 one-bits could be placed. Of those, (n0+n1-1)Cn1 start with a 0, and the remaining (n0+n1-1)C(n1-1) start with a 1. So if k is greater than or equal to (n0+n1-1)Cn1, we output a 1, decrement n1, and decrement k by (n0+n1-1)Cn1; otherwise, we output a 0 and decrement n0.

When both n0 and n1 reach 0, we're done. (An actual implementation which builds up the return value by or'ing a bit mask when necessary could stop when n1 reaches 0, saving a few steps.)