C#: Algorithm for creating random evenly distributed potentially overlapping ranges

Question

Was thinking I could test the various answers I got in my question about an algorithm for collapsing ranges. So I was thinking I should create a method that creates a whole bunch of ranges and see how the various methods handles it.

But when it comes to generating random stuff I am not very good. I created something like this:

    private static IEnumerable<Range<int>> GenerateRanges()
    {
        var r = new Random();
        var n = 10000;
        while(--n >= 0)
        {
            var start = r.Next(10000);
            var end = r.Next(10000);
            if (end < start)
                Swap(ref start, ref end);
            yield return Range.Create(start, end);
        }
    }

This creates a lot of ranges of course, but they do not give particularly interesting results since I always end up with only one range after collapsing them. How can I create more interesting ranges?

Answer 1

Make sure you also add specific tests for corner cases, like this:

• Empty list of ranges
• Two identical ranges
• Two ranges that overlap partially
• Two ranges that overlap partially, but specified in the opposite order (ie. change which one is added to the list first)
• Two ranges that does not overlap, and check both ways
• Two ranges that touch (ie. 1-10 and 11-20) integer-wise, but they should perhaps not be combined

Problem with random tests is that typically you also have to duplicate the code that performs the calculation in the test itself, otherwise, what are you going to test against? How would you know that the random data was processed correctly, except for doing the job once more and comparing?

Answer 2

You could try this:

• start from smaller n's - that should give you at some point some non-overlapping regions

• use a fixed seed for random (that you can set to different values), so that you get reproducible results

Other idea would be to use several loops for generating, and each loop having it's own set of min - max values:

var start = r.Next(5000);
var end = start + r.Next(1000);

var start = 6500 + r.Next(1000);
var end = start + r.Next(1000);

This should always give you in the end at least two non-overlapping regions (approx. maximum 0-6000 and 6500-8500)

Answer 3

private static IEnumerable<Range<int>> GenerateRanges(int amount, int max, float density, int seed)
{
    var r = new Random(seed);
    var commonLength = max * density / amount; // edited
    var maxLength = commonLength * 2;
    while(--amount >= 0)
    {
        var length = r.Next(maxLength);
        var start = r.Next(10000 - length);
        var end = start + length;
        yield return Range.Create(start, end);
    }
}

Usage could be: GenerateRanges(1000, 10000, 1.0, someTestSeed) or could be: GenerateRanges(1000, 10000, .5, someTestSeed) for less overlaps

Answer 4

If you pick a start and end point, the ranges will not be evenly distributed but concentrated at the center. 50% of the ranges will overlap the center point.

First pick a size for the range, then position it somewhere between the lower and upper limits, i.e. from 0 to 10000-size:

private static IEnumerable<Range<int>> GenerateRanges(int minSize, int maxSize) {
   Random r = new Random();
   for (int n = 0; n < 10000; n++) {
      int size = r.Next(minSize, maxSize);
      int start = r.Next(10000 - size);
      yield return Range.Create(start, start + size);
   }
}

You can use different values for minSize and maxSize to control how likely it is to get overlapping ranges.