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.
What about ranges with only 1 number, like {2,2}? That seems something you would want to have in your stress test.
Great question! It's quite awkward to incorporate single element ranges into the original generator. I found two hacky workarounds though:
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.
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.
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.