Let us say the `space = [0, 100]`

and there are a number of intervals given.

These intervals are fragments of the space, and possibly overlap.

```
[0, 30], [0, 20], [10, 40], [30, 50], [50, 90], [70, 100]
```

is a set of intervals.

An example of a set of intervals that span the entire space chosen from the above set is:

```
[0, 30], [10, 40], [30, 50], [50, 90], [70, 100]
```

Another example is

```
[0, 30], [30, 50], [50, 90], [70, 100]
```

which is the set in the previous example without `[10, 40]`

.

I want to find all combinations of such sets of intervals to calculate cost for each interval and find the one with the lowest cost.

```
from operator import itemgetter
import collections
tmp = [(0, 30), (0, 20), (10, 40), (30, 50), (50, 90), (70, 100), ]
aa = sorted(tmp, key=itemgetter(1)) # sort with respect to 1st elem
a = set(aa)
space = 100
d_conn = 15
RTT = d_conn*2
bandwidth = 10
def get_marginal_cost(fragment):
return RTT + (fragment[1] - fragment[0])/bandwidth
def dfs(a, start, path=None):
if path is None:
path = [start, ]
if start[1] == space:
yield path
for frgmt in a - set(path):
l = frgmt[0]
r = frgmt[1]
if start[0] < l <= start[1] <= r:
# if l <= start[1] <= r:
yield dfs(a, frgmt, path + [frgmt, ])
for z in a:
if z[0] == 0:
for output in list(dfs(a, z)):
for outpu in list(output):
for outp in list(outpu):
for out in list(outp):
for ou in list(out):
print list(ou)
```

This is my attempt so far, but I could not finish.

Particularly, I am looking to finish this without use of `yield`

functionality in Python, because I am not familiar with it and I probably want to implement this in C++.

Can anyone help me write a working program that solves this problem?

Thank you.