Finding all possible segment tilings in a fixed capacity

Question

I am looking for an efficient (more efficient than my combinatorial search) algorithm to tile segments of strings.

I am given two things:

Length of the "area" to cover;
Set of segments (a segment is defined by starting and ending index, as well as a label)

Example: The total length of area is 5. The given segments are:

- [(0,2), "A B"]
 - [(1,3), "B C"]
 - [(1,4), "B C D"]
 - [(3,5), "D E"]

I am using Python notation to denote segment e.g. (0,2) and its label "A B" a string.

There are 3 ways how one could populate the "area" of size 5 with the given segments with no overlap:

 1. ("A B"), ("D E")
 2. ("B C"), ("D E")
 3. ("B C D")

Other tilings are not possible as an additional segment will overlap with one of the existing tiles already sitting in the "area".

My current approach is to start with one segment and see how many combinations of non-overlapping segments I get. Then two segments and so on till 4. Each combination validity is checked if any of remaining segments cannot be added. If any of remaining segments can be inserted, the whole combination is rejected as invalid. This works pretty well when there are not many segments and there is little overlap/combinations.

Is there a simple yet efficient algorithm to find these "tilings"?

mcdowella mcdowella · Accepted Answer · 2017-11-23T05:23:48

There is a dynamic programming approach in which you work from left to right along the area to be covered, and at each point work out the number of tilings which finish neatly at that point. To calculate this, look at the segments which cover that point and end at that point. For each of these segments the number of tilings which end with that segment is the number of tilings which end just before that segment starts, and you have already calculated this. So add up these numbers to get the number of tilings which cover that point and end at that point. The answer you want is the number of tilings which cover the end point in the area to be covered and end at that point (assuming want to end neatly or will be forced to).

If you just want one of the possible tilings, you don't need to count the number of tilings terminating at each point, you just want a flag to tell whether there are any tilings terminating at that point or not. It makes it easier to retrieve a possible tiling later if you also note down, at each point where there is a tiling terminating, the tile that terminates at that point for one of the tilings.

Now you can work out a possible tiling that tiles the whole line. Look at the entry for the last character in the string. This gives you the segment that ends that tiling. Given that segment, you know the its length. If it is of length three, and the last offset was offset ten, there must be a valid tiling that terminates at offset seven. You will have noted the segment that terminates at offset seven, which gives you the second last segment in the tiling you need. By looking at the length of that segment, you can work out where to look for a note of the segment just before that, and so on, until you have recovered the entire tiling, from right to left.

Finding all possible segment tilings in a fixed capacity

1 Answers