heavylightdecomp's blog

By heavylightdecomp, history, 14 months ago, In English

Recently, I was solving a problem that involved disjoint ranges. And while stress testing my solution I found a simple trick to fairly and efficiently generate such ranges.

Let us first examine a set of $$$N = 3$$$ disjoint ranges: [{2,3}, {6, 7}, {4, 5}]. If we list their endpoints in order, we get a sequence of $$$2 \times N$$$ integers, where adjacent integers are paired together to form a range: [2,3, 4,5, 6,7]

It follows from this observation that you can generate N disjoint ranges by first generating $$$2 \times N$$$ unique integers (duplicates will affect the disjoint condition), and then "matching" adjacent integers together.

Here is some Python code:

click me

As an additional advantage, the output is sorted.

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
14 months ago, # |
  Vote: I like it +7 Vote: I do not like it

What about ranges with only 1 number, like {2,2}? That seems something you would want to have in your stress test.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Great question! It's quite awkward to incorporate single element ranges into the original generator. I found two hacky workarounds though:

    1. Assume the ranges are inclusive-exclusive, so {1,2} by the generator is actually [1,1]. This has the additional perk of ensuring your ranges don't touch at endpoints.

    2. Separately add your single-element ranges at the end of the generator algorithm, making sure their endpoints don't already exist in your set. This is what I would probably do if the original generator couldn't find a breaking case.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    If you want to select $$$K$$$ disjoint ranges from $$$[1, N]$$$, you can randomly select $$$2K$$$ distinct integers from $$$[1, N + K]$$$. Let the numbers be $$$a_1 < a_2 < \dots < a_{2K}$$$ in sorted order. Define $$$b_i = a_i - \lfloor \frac{i}{2} \rfloor$$$. Then we can take ranges $$$(b_1, b_2), (b_3, b_4), \dots, (b_{2K-1}, b_{2K})$$$. This includes ranges with size 1 as well.