Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question
4  
You are likely looking for combinations. –  MichaelT 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

2 Answers 2

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...

share|improve this answer
1  
Go ahead and accept your answer. You get a shiny badge for it. –  World Engineer Jul 8 '13 at 9:52
    
You probably would need an efficient algorithm to generate the combinations if the gap size can be large. –  Monster Truck Jul 8 '13 at 10:35

There's a simpler way, given your no-gap constraint.

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}.

You generate those as

FOR ( BEGIN = 0 TO LENGTH)
  FOR (END = 0 TO MINIMUM(MAXCHARS, LENGTH-BEGIN) )
    PRINT BEGIN, END
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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