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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.