Given an array of n bits, how to generate every permutation with i 1's and n-i 0's?

Question

It's simple enough to brute force a collection of strings and then filter for every occurrence with the required count of 1's.

As n increases the number of possible permutations becomes very large, very quickly, however, and due to speed and space considerations, I'm trying to find a more sophisticated method -- ideally, one that doesn't involve excessive string processing.

Answer 1

You can slice up the problem in subprocess (pseudocode):

array[] GetArrays(j, n)
    if(n = 0)
        return one empty array
    if(j = 0)
        return one array of n zeroes
    array[] zero = map(prepend 0,  GetArrays(j, n-1)) 
    array[] one = map(prepend 1,  GetArrays(j - 1, n - 1))
    return concat(zero, one)

Answer 2

Pick an arbitrary algorithm for generating all combinations of i elements from n. See this former SO post, for example, or the 75 examples in different programming languages at Rosetta Code. Then use it to generate all combinations of i elements from the set {0,1,2,...,n-1} and assign each result R=(r1,r2,...,r_i) a string of length n of zeros and ones where the positions of the ones are the values in R.