# Finding non-overlapping combinations of spans/bitarrays

My first post here so please correct me if my terms are off or needs clarification.

Suppose I have several sets of lists of spans. I define a span as a pair of indexes: begin and end index in a string. You can also think of a span as a consecutive sequence of 1's in a bitarray. e.g. 00111 is a span of (2,5).

I will have up to 10 sets of lists of spans. Each set will have on the order of 30 spans in each list. In case it's important, a span can have no more than 20 bits but spans will likely be small, spanning on average 5 bits.

I have to pick one (or none) span from each set such that there are no overlapping bits among them.

Let's suppose 2 sets of lists of spans for a moment.

The first set has the following list of spans:

• (0,5) or 11111
• (0,3) or 11100
• (1,4) or 01110

The second set has the following list of spans:

• (2,4) or 00110
• (3,5) or 00011
• (4,5) or 00001

The valid combinations are [(0,3),(3,5)], [(0,3),(4,5)], and [(1,4),(4,5)].

I could try all combinations, but with 10 sets of 30 spans, that's 30^10 combinations!

Is there some bit manipulation magic I could use? Or could I sort the spans and eliminate many of the combos? e.g. when considering (0,3), I can sort the next list of spans by the beginIndex and rule out everything that starts with 2 or less.

This is similar to this problem: Finding a pair of non-overlapping bit vectors But in mine, the bits are consecutive so there must be a way to take advantage of the beginning and ending boundaries

• Does your task come from real life? If possible at all, please credit the source of your task in the question. What are the general pattern of lengths of each full string? Do you imply they are the same in all sets? For your typical 10 sets of 30 spans, can you give a rough estimate of how many valid combinations there are? Anyway, $30^{10}$ initial combinations does NOT sound out of reach at all to me unless you will do it for hundreds or millions of time. Will you? In the end, do you need the list of all valid combinations or just the count of them? – John L. Sep 29 '18 at 1:21
• This is proprietary company data I'm working with. yes, the length of string is the same for all sets. 30^10 is just for one calculation. I have to do this many times, on the order of thousands for my experiment, but potentially hundreds in real-time. I actually need a list of all combinations, not just a count. – kane Sep 29 '18 at 4:25
• I come from a record linkage background and we frequently use a technique called blocking to reduce the search space. One idea I was considering is indexing the 1's in each span bitarray to do a quick lookup of which candidate spans might fit into the remaining 0's of a bitarray that is a union of of all valid bitarrays so far found. – kane Sep 29 '18 at 4:28
• The other two questions? The general pattern of lengths and rough estimates. Can you post sample 10 sets of 30 spans in a webpage such as pastebin.com? – John L. Sep 29 '18 at 4:39
• Here is an example of 2 sets (I don't have more at the moment). The length is 20 and I guess the typical span is pretty short. pastebin.com/A9qpPuku – kane Sep 30 '18 at 20:37