Chariphuk - 9 months ago 56

C++ Question

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:

- 00011
- 00101
- 00110
- 01001
- 01010
- 01100
- 10001
- 10010
- 10100
- 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.)