Find X contiguous segments in a range of integers

Question

I've been struggling with the following problem: how do I find all possible sub-ranges in a range of integers where each segment is at least length 1, and I specify the total number of segments? A couple examples:

segments=2, range=(0,5)
> [0,1],[2,5]
> [0,2],[3,5]
> [0,3],[4,5]

segments=3, range=(0,8)
> [0,1],[2,3],[4,8]
> [0,1],[2,4],[5,8]
> [0,1],[2,5],[6,8]
> [0,1],[2,6],[7,8]
> [0,2],[3,4],[5,8]
> [0,2],[3,5],[6,8]
> [0,2],[3,6],[7,8]
> [0,3],[4,5],[6,8]
> [0,3],[4,6],[7,8]
> [0,4],[5,6],[7,8]

This feels like a recursion problem because I need to iterate over a varible number of for-loops, but I don't see how to make it work.

Answer 1

Here's a quick piece of pseudo-code off the top of my head.

Given maximum value m and number of non-empty segments n, do so:

Call Helper(Empty List [passed by reference], Empty List [copied before passing or passed by copy], 0, m, n)

The helper function takes as input:

1. a reference to the output list of lists,

2. a list of segments to append more segments to

3. the lower bound or starting value

4. the upper bound or stopping value

5. the number of segments

   function Helper(L, S, l, u, n):
     If n = 1 then append to L the list S.append(l, u)
     Else:
       For each t from l+1 up to u-n *inclusive*:
         Make a copy of S into S'
         Append to S' the pair (s, t)
         Call Helper(L, S', t+1, u, n-1)
   

As you can see, the only "trick" was perhaps just figuring that out you should use a helper function with more arguments to aid the recursion. Of course, different solutions may be possible.

A note here. It should be possible to change the implementation above slightly (e.g., using return values as opposed to passing L by reference) that one can memoize the result of each call for a given triple (l, u, n). Such a DP approach seems to me like it may make the program be significantly faster on large input. I assume this sort of problem has much sharing to be exploited using a DP approach.

Answer 2

Hint 1. Splitting a range into $k$ segments is the same as selecting the $k-1$ break-points between segments.

Hint 2. As you proceed through the list of elements, the next element is either part of the current segment or part of the next one.