This Question have 3 answers right now.

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

Tags: c# random
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?
http://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.)



Answers

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.



  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.

enter image description here



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

By : pstrato


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