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:
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
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
n1, and decrement
(n0+n1-1)Cn1; otherwise, we output a
0 and decrement
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.)