2
$\begingroup$

I have to design an algorithm to do the next task:

I have one array of booleans. For example:

Array: [0 1 0 0 1 0 1 1]

I want to obtain all the existing combinations of 1's, having in mind that it is allowed only a maximum of one 0 between 1's. For example, in the previous case, we would have the outputs (I am using the indices now): [1] and [4,5,6,7].

But also it should include [4], [6], [7], [4,5,6], [6,7].

Another example:

Array: [0 1 0 1 0 1 0 0 1]

The output would be: [1], [3], [5]. [8], [1,2,3], [1,2,3,4,5], [3,4,5].

Can you imagine any approach to solve this? The combination explosion could be quite big.

Thank you very much in advance.

$\endgroup$
  • $\begingroup$ just enumerate them & throw out those that dont match the criteria. hey, you didnt say it had to be non brute force... something more advanced? how about encoding the rules into SAT & using a SAT solver? :p $\endgroup$ – vzn Jun 18 '15 at 20:13
  • 1
    $\begingroup$ 1. Please explain what you mean by "combination of 1's". Do they have to be consecutive indices? 2. What have you tried? Do you have any algorithm, even an inefficient one? We expect you to make a significant effort on your own to solve your own problem before posting here, and to show us what you've tried. We want to help you understand concepts, not solve your exercise for you (that wouldn't help you or anyone else). 3. Can you tell us the context in which you ran across this, or the motivation/application? $\endgroup$ – D.W. Jun 19 '15 at 4:01
2
$\begingroup$

The pattern you're trying to match is regular and can be matched by the regular expression 1(0?1)*. A good strategy would be to convert the binary array to a string and do regular expression matches over substrings of it.

There aren't an exponential number of bit strings to check. For a string of length $n$, you only have to check 1 string of that length. You then check 2 strings of length $n - 1$, 3 strings of length $n - 2$ and so on. In total there are $n(n+1)/2$ strings to check.

$\endgroup$
  • $\begingroup$ A better way may be to build a substring matching automaton from the regular expression. After preprocessing, that would allow linear-time processing. $\endgroup$ – Raphael Jun 18 '15 at 10:24
  • $\begingroup$ Note that quadratic runtime in string length is prohibitive in some applications, e.g. bioinformatics (where regularly $n \gg 10^6$). Well, here the output set itself can be as large, so there's probably not much to be done (if you want to full set, not only an iterator). $\endgroup$ – Raphael Jun 18 '15 at 10:29
2
$\begingroup$

Simple $O(n^2)$ solution -

def combs(A):
    n=len(A)
    for i in range(n): # Primary loop, i loops over possible starting points
        if A[i]==1:    # Wherever we see a 1...
            yield [i]  # Yield the location and
            prev=i     # Store position as last see index of 1, and
            for j in range(i+1,n):  # Start secondary loop
                if A[j]==0:         # If we see a 0
                    if j-prev>1:    # Break if this and last are both 0s
                        break
                else:               # If we see a 1
                    prev=j          # Store this as last seen index of 1
                    yield list(range(i,j+1))  # Yield the from start till this location

Then you get -

list(combs([0,1,0,0,1,0,1,1]))
# [[1], [4], [4, 5, 6], [4, 5, 6, 7], [6], [6, 7], [7]]
$\endgroup$
  • 2
    $\begingroup$ What is the idea here? Why is it correct? $\endgroup$ – Raphael Jun 19 '15 at 11:09
  • $\begingroup$ Edited to add the motivation. $\endgroup$ – KalEl Jun 19 '15 at 19:40
  • $\begingroup$ FYI, if you're not super-familiar with this site, this is not a coding site (e.g., we're not Stack Overflow). We're not particularly looking for code; we're more about ideas, concepts, science, etc. Generally, an answer that contains only code (or primarily code) might not be the best choice on this site. I suspect that a description of the idea, the algorithm, etc. would be more useful. Just a tip that might be helpful in the future. $\endgroup$ – D.W. Jun 19 '15 at 23:45
  • $\begingroup$ DW, for simple problems like this I often find a short code to be the best way to express the idea. $\endgroup$ – KalEl Jun 20 '15 at 12:41
1
$\begingroup$

It seems to me that your main problem is stating what you want. The following is inferred from what you say and the examples you give.

Essentially, you have a string $w\in \{0,1\}^*$, which you call an array of booleans.

What you want is list all substrings that begin and end with a $1$ such that they do not contain two consecutive $0$.

This is a pretty standard problem that you can solve with a finite state control, and some extras, depending on how you wish to express the result. Here is simply a direct pseudo-code solution.

First, you should not be afraid of a combinatorial explosion. Given a string of length $n$, indexed from $1$ to $n$, there are $n$ ways of choosing the first index $i$ of a substring, and for each choice of $i$, there are $i$ ways of choosing the last index of the substring. So that make a total of $\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$ substrings, which is only quadratic, and not too combiatorial.

The answers you are looking for are only a subset of the set of substring, so there is not too much to be afraid of.

Then the algorithm goes as follow:

Start from beginning of the string.
loop
  Look for the index i of the first 1
  Scan the string while you do not see two consecutive 0, or the end
    of string
  let j be the index of the last encountered 1
  list correct-substrings (i,j)
  Exit loop if end of string has been reached

Subprogram correct-substrings (i,j)
  for all k in [i,j] such that w[k]=1 do
    for all h in [k,j] such that w[h]=1 do
      output substring(k,h)

The subprogram substring(k,h) produces the list of indexes from k to h.
$\endgroup$
  • $\begingroup$ @PowersThatBe I am sick and tired of the way posts to be reviewed are presented. The system should provide some minimum information, such as the number of answers a question already has. Trying to send suggestions to powers that be is just an incredible waste of time. It is very well to ask for volontary contributions, but making our lives easier is a minimum one can ask. $\endgroup$ – babou Jun 20 '15 at 10:54

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.