How to randomly generate a float between two values with a variable number of ranges excluded?

Question

For example, if I wanted to generate a random float between 0 - 100, but exclude the values 1.097 - 3. 346, 7.0001 - 8.9996, 14.5 - 38.6, 50 - 50.389, 75.648 - 88.8975, etc? I thought this would be a simple problem, but there doesn't even seem to be Range object in c#, and there is no RandWithExclusion() method.

I have seen all these questions,
How can I generate a random number within a range but exclude some?
https://gamedev.stackexchange.com/questions/124059/how-can-i-exclude-a-range-of-values-when-generating-random-numbers
How to get a random number from a range, excluding some values
none of them are even remotely useful. Is what I'm doing really such a rare problem?

How would I even go about doing this? (Without brute-forcing, please.)

Answer 1

1. Consider the ranges you do want to include R1, R2, ... Assume they are non-overlapping and in order.

2. Add up their total spans (end-start). You now have a contiguous range for your random number (zero to sum(spans)).

3. Generate a number in that range.

4. Now map that number back onto the non-contiguous ranges:

   1. If it's less than first range's span, add it to start of first range and return it.
   2. Otherwise, subtract first range's span from it, compare to second span etc.

Answer 2

I would do a little pre-processing before drawing the numbers to get a list of possible ranges. So let's assume we have a Range structure like so:

/// <summary> A possible range of values. </summary>
public struct Range
{
    /// <summary> Min value, inclusive. </summary>
    public readonly double Min;
    /// <summary> Max value, inclusive. </summary>
    public readonly double Max;
    public Range(double min, double max) { Min = min; Max = max; }
    /// <summary> Range length, distance between Min and Max. </summary>
    public double Length { get { return Max - Min; } }
}

And another structure RangeList which holds several ranges together. Range list also contains a cumulative length array of successive length sums of your Ranges, like so:

/// <summary> All possible ranges grouped together. </summary>
public struct RangeList
{
    /// <summary> Possible range. </summary>
    public readonly Range[] Ranges;
    /// <summary> Sum of each range length. </summary>
    public readonly double Length;
    /// <summary> Cumulative lengths values of each ranges. </summary>
    public readonly double[] CumulLengths;
    public RangeList(Range[] ranges)
    {
        Ranges = ranges;
        Length = 0;
        CumulLengths = new double[ranges.Length];
        for (var i = 0; i < ranges.Length; ++i)
        {
            Length += ranges[i].Length;
            CumulLengths[i] = Length;
        }
    }
}

We can then write easily a function that creates a RangeList from a given list of excluded ranges:

    /// <summary> Get possible ranges to draw from, considering exclusions. </summary>
    public static RangeList GetRangeList(Range range, params Range[] exclusions)
    {
        var ranges = new List<Range>();
        ranges.Add(range);
        if (exclusions != null)
        {
            foreach (var exclusion in exclusions)
            { // progressively eat latest range added to the list, cutting exclusions.
                var lastRange = ranges[ranges.Count - 1];
                if (exclusion.Min < lastRange.Max)
                {
                    ranges[ranges.Count - 1] = new Range(lastRange.Min, exclusion.Min);
                    if (exclusion.Max < lastRange.Max)
                    {
                        ranges.Add(new Range(exclusion.Max, lastRange.Max));
                    }
                }
            }
        }
        return new RangeList(ranges.ToArray());
    }

This method relies on several assumptions, including that not all space is excluded, exclusions are not overlapping, and exclusions are given in ascending order. It is then straight-forward to draw a number from the possible ranges:

    /// <summary> Assume exclusions are also given in ranges. </summary>
    public static double RangeWithExclusions(this Random random, Range range, params Range[] exclusions)
    {
        var rangeList = GetRangeList(range, exclusions);
        var rnd = random.NextDouble() * rangeList.Length;
        var rangeIndex = Array.BinarySearch(rangeList.CumulLengths, rnd);
        if (rangeIndex < 0)
        { // 'unlucky', we didn't hit a length exactly
            rangeIndex = ~rangeIndex;
        }
        var previousLength = rangeIndex > 0 ? rangeList.CumulLengths[rangeIndex - 1] : 0;
        var rndRange = rangeList.Ranges[rangeIndex]; // result range of our random draw
        return rndRange.Min + (rnd - previousLength); // scale rnd back into range space
    }

The following NUnit test demonstrate how to use the solution:

[TestFixture]
public class TestRandom
{
    [Test]
    public void Tests()
    {
        var random = new Random();
        double rnd;
        rnd = random.RangeWithExclusions(new Range(0, 1));
        Assert.IsTrue(rnd >= 0 && rnd <= 1);
        rnd = random.RangeWithExclusions(new Range(-100, 1));
        Assert.IsTrue(rnd >= -100 && rnd <= 1);
        rnd = random.RangeWithExclusions(new Range(0, 1), new Range(0.1, 0.9));
        Assert.IsTrue(rnd >= 0 && rnd <= 1 && (rnd <= 0.1 || rnd >= 0.9));
        rnd = random.RangeWithExclusions(new Range(0, 1), new Range(0, 0.9));
        Assert.IsTrue(rnd >= 0 && rnd <= 1 && (rnd >= 0.9));
        rnd = random.RangeWithExclusions(new Range(0, 1), new Range(0.2, 0.4), new Range(0.6, 0.8));
        Assert.IsTrue(rnd >= 0 && rnd <= 1 && (rnd <= 0.2 || rnd >= 0.4) && (rnd <= 0.6 || rnd >= 0.8));
    }
}

Hope this helps

Answer 3

This is pretty simple... probably a good one that you should have sat and figured out on your own for learning purposes (especially since you yourself say that it's a simple problem).

This isn't the best way nor the most efficient way to do this by any means, but it's a naive approach that works with little thinking required. The drawbacks are that if you run this multiple times (e.g. a million times) you'll generate quite a bit of duplicates.

public class Range
{
    public float MinValue { get; set; }
    public float MaxValue { get; set; }
}

public static class FloatGenerator
{
    public static float GenerateFloatWithExclusionsInANaiveWay(int minValue, int maxValue, params Range[] rangeExclusions)
    {
        // We don't care about ranges outside of the min and max values allowed
        var allowedRanges = rangeExclusions.Where(r => r.MinValue >= minValue && r.MaxValue <= maxValue);

        // We use a guid to generate a random seed that random will use (reduces chance of duplicates)
        var random = new Random(Guid.NewGuid().GetHashCode());

        // We will use this to keep a pool of random values that fit within our expected ranges
        var randomPool = new List<float>();

        // Loop through each of the ranges and get a value that fits the range
        foreach (var range in allowedRanges)
        {
            var randomValue = float.MaxValue;
            while (randomValue < range.MinValue || randomValue > range.MaxValue)
            {
                randomValue = (random.Next((int)range.MinValue, (int)range.MaxValue) + (float)random.NextDouble());
            }

            randomPool.Add(randomValue);
        }

        // Return one of the acceptable random numbers randomly
        return randomPool.ElementAt(random.Next(0, randomPool.Count - 1));
    }
}

If you want to get fancier, you can look at the other answers that put more thought into it than you probably wanted.