Trick to randomly generate disjoint ranges

Revision en1, by heavylightdecomp, 2023-01-13 06:32:31

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.

Tags python, ranges, generator, stress testing

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English heavylightdecomp 2023-01-13 06:32:31 1137 Initial revision (published)