1

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

Improve this question
2
  • 4
    You are likely looking for combinations. Commented Mar 10, 2013 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. Commented Mar 10, 2013 at 8:29

2 Answers 2

Reset to default
1

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

Improve this answer
1
  • You probably would need an efficient algorithm to generate the combinations if the gap size can be large. Commented Jul 8, 2013 at 10:35
0

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
Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.