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

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.

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)
``````

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.