Calculate number of distinct values between two numbers at a given precision

Question

Context: I am building a random-number generating user interface where a user can enter values for the following:

lowerLimit: the lower limit for each randomly generated number
upperLimit: the upper limit for each randomly generated number
maxPrecision: the maximum precision each randomly generated number
Quantity: the maximum number of random number values to be generated

The question is: how can I ensure that at a given lowerLimit/upperLimit range and at a given precision, that the user does not request a greater quantity than is possible?

Example:

lowerLimit: 1 upperLimit: 1.01 maxPrecision: 3 Quantity: 50

At this precision level (3), there are 11 possible values between 1 and 1.01: 1.000, 1.001, 1.002, 1.003, 1.004, 1.005, 1.006, 1.007, 1.008, 1.009, 1.100, yet the user is asking for the top 50.

In one version of the function that returns only distinct values that match user criteria, I am using a dictionary object to store already-generated values and if the value already exists, try another random number until I have found X distinct random number values where X is the user-desired quantity. The problem is, my logic allows for a never-ending loop if the number of possible values is less than the user-entered quantity.

While I could probably employ logic to detect runaway condition, I thought it would be a nicer approach to somehow calculate the quantity of possible return values in advance to make sure it is possible. But that logic is eluding me. (Haven't tried anything because I can't think of how to do it).

Please note: I did see question Generating random, unique values C# but is does not address the specifics of my question relating to number of possible values at a given precision and subsequent runaway condition.

private Random RandomSeed = new Random();
public double GetRandomDouble(double lowerBounds, double upperBounds, int maxPrecision)
{
    //Return a randomly-generated double between lowerBounds and upperBounds 
    //with maximum precision of maxPrecision
    double x = (RandomSeed.NextDouble() * ((upperBounds - lowerBounds))) + lowerBounds;
    return Math.Round(x, maxPrecision);
}
public double[] GetRandomDoublesUnique(double lowerBounds, double upperBounds, int maxPrecision, int quantity)
{
    //This method returns an array of doubles containing randomly-generated numbers
    //between user-entered lowerBounds and upperBounds with a maximum precision of
    //maxPrecision.  The array size is capped at user-entered quantity.

    //Create Dictionary to store number values already generated so we can ensure
    //we don't have duplicates
    Dictionary<double, int> myDoubles = new Dictionary<double, int>();
    double[] returnValues = new double[quantity];
    double nextValue;
    for (int i = 0; i < quantity; i++)
    {
        nextValue = GetRandomDouble(lowerBounds, upperBounds, maxPrecision);
        if (!myDoubles.ContainsKey(nextValue))
        {
            myDoubles.Add(nextValue, i);
            returnValues[i] = nextValue;
        }
        else
        {
            i -= 1;
        }
    }
    return returnValues;
}

Any quantity of random numbers is possible with any range with any precision because random numbers, by definition, are allowed to recur. If you are saying you never want to get the same number to recur you are looking for a [shuffle](https://stackoverflow.com/questions/56378647/), not a random number. — Dour High Arch, Nov 27 '19 at 20:41

Alexei Levenkov · Answer 1 · 2019-11-29T19:29:22.193

Number of items can be computed by just subtracting "position" of first from last (pseudo-code below, use Math.Pow to compute 10^x):

(int)(last * 10 ^ precision) - (int)(first * 10 ^ precision)

This may need to be adjusted depending on whether you want boundaries and whether you take decimal (precise) or float/double as input - some +/-1 and Math.Round may need to be sprinkled in to get desired results for all expected values.

After you get number of items there are essentially two cases

there are significantly more choices that desired results (i.e. 1 to 100, take 5 random numbers) - use code you have to filter out duplicates.
there the number of choices is close or less than desired number of results (i.e. 1 to 10, return 11 random numbers) - pre-generate the list of all value and shuffle.

Experiment with the boundary between "significantly more" and "close" - I'd use 25% as boundary ( i.e. 1 to 100, take 76 - use shuffling) to avoid excessive retires close to the end (which is exact reason of slowness/infinite retries of basic approach).

Correct implementation of shuffle is in Randomize a List<T> (check out similar posts like Generating random, unique values C# for more discussion).

Thanks--good to know about shuffle. That will be useful in the future. BTW: it appears that the ^ symbol doesn't work for "power". Math.Pow did the trick, though. — AndrewBanjo1968, Nov 29 '19 at 12:55
@AndrewBanjo1968 sorry, I originally did not want example look like code... as indeed `^` is not power (also it is common knowledge)... — Alexei Levenkov, Nov 29 '19 at 19:27

score 1 · Accepted Answer · 2019-12-02T14:17:16.693

The easiest way would probably be to convert the values to integers by multiplying them by 10 ^ precision and then subtract

int lowerInt = (int)(lower * (decimal)Math.Pow(10, precision));
int higherInt = (int)(higher * (decimal)Math.Pow(10, precision));
int possibleValues = higherInt - lowerInt + 1

I feel like it would defeat the purpose of you project to require the user to know how many possible values there are in advance, since it seems like thats what they are hitting this function for in the first place. I'm assuming that requirement was just to alleviate the technical issues you were having. You can just change your loop to this now

for (int i = 0; i < possibleValues; i++)

score 0 · Answer 3 · answered Nov 29 '19 at 14:05

This is what worked based on Josh Williard's answer.

public double[] GetRandomDoublesUnique(double lowerBounds, double upperBounds, int maxPrecision, int quantity)
    {
        if (lowerBounds >= upperBounds)
        {
            throw new Exception("Error in GetRandomDoublesUnique is: LowerBounds is greater than UpperBounds!");
        }
        //These next few lines are for the purpose of determining the maximum possible number of return values
        //possibleValues is populated to prevent a runaway condition that could occurs if the 
        //max possible values--at the given precision level--is less than the user-selected quantity.
        //i.e. if user selects 1 to 1.01, precision of 3, and quantity of 50, there would be a problem
        // if we didn't limit loop to the 11 possible values at precision of 3:  
        //1.000, 1.001, 1.002, 1.003, 1.004, 1.005, 1.006, 1.007, 1.008, 1.009, 1.010

        int lowerInt = (int)(lowerBounds * (double)Math.Pow(10, maxPrecision));
        int higherInt = (int)(upperBounds * (double)Math.Pow(10, maxPrecision));
        int possibleValues = higherInt - lowerInt + 1;

        //Create Dictionary to store number values already generated so we can ensure
        //we don't have duplicates
        Dictionary<double, int> myDoubles = new Dictionary<double, int>();
        double[] returnValues = new double[(quantity>possibleValues?possibleValues:quantity)];
        double NextValue;
        //Iterate through and generate values--limiting to both the user-selected quantity and # of possible values
        for (int i = 0; (i < quantity)&&(i<possibleValues); i++)
        {
            NextValue = GetRandomDouble(lowerBounds, upperBounds, maxPrecision);
            if (!myDoubles.ContainsKey(NextValue))
            {
                myDoubles.Add(NextValue, i);
                returnValues[i] = NextValue;
            }
            else
            {
                i -= 1;
            }
        }
        return returnValues;
    }

Calculate number of distinct values between two numbers at a given precision

3 Answers3