# Finding the possible combinations of x switches out of y being true

I am working on an algorithm to find possible fills for gaps in text. My function will receive as input: (example)

``````[false,"o",false,"b",false,"r"]
``````

representing the string "foobar" with some values cut out. My function should find opportunies for the possible ways to fill the gaps given a set maximum characters (and a minimum of one blank filled). so, given a maximum of 2 it should return:

``````[
[true,"o",false,"b",false,"r"],
[false,"o",true,"b",false,"r"],
[false,"o",false,"b",true,"r"],
[true,"o",true,"b",false,"r"],
[true,"o",false,"b",true,"r"],
[false,"o",true,"b",true,"r"]
]
``````

Can anyone give me a shove in the right direction?

Oh, and I planned to run the results through another function to sort these out, but if I can NOT get results where there is a false between the blanks (ie, from the above, `[true,"o",false,"b",true,"r"]`) it would be a huge bonus.

This is in a javascript/jQuery environment

-
You are likely looking for combinations. – user40980 Mar 10 '13 at 5:54
That's correct, and I looked at that page and some others on it for a while. I ended up doing it in a slightly convoluted way because I had that extra requirement of not leaving gaps, but I think it made it slightly simpler (to me anyway). You definitely got me thinking on the track to my answer though, so thanks. – Chris O'Kelly Mar 10 '13 at 8:29

Found my own answer, it was particularly curious to my own solution, I don't really have a code example of a more general solution (like what MichaelT linked in comments) but in pseudocode it was essentially:

``````/*
Find the free(false) cells in the array and create an array of their indices
check the array is not empty
if it is return false (if there's no free space you cannot fill anything)
(now check the combinations...)
for n=1..the maximum number of fills (for each possible number of fills)
for each of the free cells (for each possible first fill)
check the number of free cells after this one
if it is less than n-1 break (no room for this many fills)
for 1..n-1 (for each fill left after the first)
fill this spot
add the result to the list of results
*/
``````

as I said, fairly specified to my solution of only replacing in line, I think some serious nested for's would be required to do it the other way round.

Anywho, I'll mark mine correct as it's how I solved mine, but it's probably not relevant to many people...

-
There are two relevant positions, `first_true` and `last_true`. These cannot be further apart than `max_chars-1`. Your 6 solutions can thus be summarized as {0,0}, {1,1}, {2,2}, {0,1}, {0,2} and {1,2}.
``````FOR ( BEGIN = 0 TO LENGTH)