2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Hint 1 is slightly wrong (should be $k - 1$ break-points) and Hint 2 is slightly vague (imo). Also it might be better to mention that the two hints correspond to two different ways of solving the problem ... $\endgroup$ – WhatsUp Jun 20 '17 at 11:57
  • $\begingroup$ @WhatsUp Wow, I made the very archetype of off-by-one errors! :-) Thanks for spotting it. I take your point about the second one being a bit vague but I'm trying not to just give the whole answer -- maybe I went too far the other way. In my mind, the two hints were aimed at the same method but I don't think it's a problem if they move people in different ways. $\endgroup$ – David Richerby Jun 20 '17 at 13:34

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.