Return to Question

It is summer and my apartment building has experienced yet another blackout, my computer is a desktop and I can't even boot my computer to test the code. I was out before and now my phone is running out of juice, I don't know how long the blackout will last so there is a chance I won't be able to award the bounty.

I edited the code that generates the samples to address bugs in the logic.

The code generates invalid input because the numbers are required to be unique, [(0, 1, 'A'), (0, 1, 'B')] is invalid, but cases like this can be generated by my code.

I first thought random.choices guarantees the choices to be unique if sample size is less than population size, I was wrong, it is just highly likely.

I fixed the code so that all numbers are guaranteed to be unique, and invalid test cases won't generated.

I edited the code but I haven't tested the functions thoroughly yet, my edit was immediately rolled back, though I would argue the edited code isn't what I wanted reviewed, this is an error by the one who made the reversion, though I won't edit the code again lest it be rolled back again.

And yes, the input is guaranteed to be sorted in ascending order, as I mentioned in my question multiple times and demonstrated with the code that generates test cases.

Lastly I am experiencing some "technical difficulties", more specifically my computer doesn't have internet connections right now because I just broke my modem (I just bought a new one online), and I am using my phone right now (which doesn't have reliable VPN connection now and in China Stack Exchange is throttled to nearly inaccessible), so updates will be much less frequent as of now.

But I will try to award the bounty within the bounty grace period if I found a bounty-worthy answer (if new answers are posted) or if I determined @booboo's method to be correct. That is, if I managed to visit this site at all, of course.

import random
def make_sample(num, lim, dat):
 num *= 2
 if num > lim:
 lim = num * random.randrange(1, 6)
 numbers = range(lim)
 choices = set(random.choices(numbers, k=num))
 remaining = list(set(numbers) - choices)
 while len(choices) != num:
 choice = random.choice(remaining)
 remaining.remove(choice) choices.add(choice)
 stack = [sorted(choices)]
 ranges = []
 while stack:
 top = stack.pop(0)
 l = len(top)
 if l == 2:
 ranges.append(top)
 elif l == 4:
 ranges.extend([top[:2], top[2:]])
 else:
 choice = random.randrange(3)
 if not choice:
 ranges.append([top[0], top[-1]])
 stack.append(top[1:-1])
 elif choice == 1:
 i = l//3
 i += i % 2
 index = random.randrange(i, 2*i, 2)
 ranges.append(top[index:index+2])
 stack.extend([top[:index], top[index+2:]])
 else:
 index = random.randrange(2, l - 2, 2)
 stack.extend([top[:index], top[index:]])
 ranges.sort(key=lambda x: (x[0], -x[1]))
 return [(a, b, random.randrange(dat)) for a, b in ranges]

Edit:

It is my bad, all ranges are required to have unique end points, so [(0, 1, 'A'), (0, 1, 'B')] is not valid input.

My code that generates tests cases failed the uniqueness constraint, I thought random.choices guarantees the numbers to be unique if the sample size is less than the population size, I was wrong, now the numbers are guaranteed to be unique.

I still need to test the functions.

import random
def make_sample(num, lim, dat):
 if num * 2 > lim:
 lim = num * 2 + random.randrange(num)
 
 stack = [sorted(random.choices(range(lim), k=2*num))]
 ranges = []
 while stack:
 top = stack.pop(0)
 l = len(top)
 if l == 2:
 ranges.append(top)
 elif l == 4:
 ranges.extend([top[:2], top[2:]])
 else:
 choice = random.randrange(3)
 if not choice:
 ranges.append([top[0], top[-1]])
 stack.append(top[1:-1])
 elif choice == 1:
 i = l//3
 i += i % 2
 index = random.randrange(i, 2*i, 2)
 ranges.append(top[index:index+2])
 stack.extend([top[:index], top[index+2:]])
 else:
 index = random.randrange(2, l - 2, 2)
 stack.extend([top[:index], top[index:]])
 ranges.sort(key=lambda x: (x[0], -x[1]))
 return [(a, b, random.randrange(dat)) for a, b in ranges]