C++ generate random number based on mathematical equations.

Question

I have three positive integers

• distance1
• distance2
• distnace3

that sum up to 100.

distance1 + distance2 + distance3 = 100 (EQ1)

I have additional information that

• 20 < distance2 < 90 (EQ2) and
• distance1 + distance3 > 8 (EQ3)

I need in C++ to calculate fast three positive random values for distance1, distance2 and distance3 in order to support the equations EQ1, EQ2 and EQ3.

My first approach was to do the following

    std::list<...> solutions;
    //i for distance1, j for distance2, z for distance3
    for (int i = 1; i < 101; i++) {

       for (int j = 1; j < 101; j++)  {

           for (int z = 1; z < 101; z++)  {

              evaluate if i, j, z satisfy EQ1, EQ2,EQ3
              if ( evaluate == true )
                solutions.push_back(...i,j,z...); //pseudocode

           }
       }

    }
// when all iterations are finished select a random from std::<list>

Any better approach to do this? Is there any library that can help? Is this the correct way to perform combinations?

Answer 1

Mathematically you have stated that these are your conditions:

I have three positive integers

• distance1
• distance2
• distnace3

that sum up to 100. 


distance1 + distance2 + distance3 = 100 (EQ1)

I have additional information that

•20 < distance2 < 90 (EQ2) and
•distance1 + distance3 > 8 (EQ3)

Let's first use mathematics to find the range & domain of the values. Let these be A, B & C for your three distances. From what you stated we can see that:

For A We don't have enough information without first finding B & C
A = [Depends On B & C]
B = [21,89]

For C; Since A+C > 8 then:
C > 8 - A
We Know that both A & C are both positive so let's make a small table setting values to A
C > 8 - 1   |  C > 7
C > 8 - 2   |  C > 6
C > 8 - 3   |  C > 5
C > 8 - 4   |  C > 4
C > 8 - 5   |  C > 3
C > 8 - 6   |  C > 2
C > 8 - 7   |  C > 1
C > 8 - 8   |  C > 0 still holds true
C > 8 - 9   |  C > -1  ... ? Still true

How Large can A go? This depends on B & C so we need to use B's domain.

100 = (C > 8 - A) + B[21,89]

We can use B's min and max values or the 
floor & ceiling function to determine the domains of A & C.

If B = 21 (min) then the range of combinations between A & C are
100 - 21 = 79
A[1-78]  &  C[1-78] since you have A+B

If B = 89 (max) then the range of combinations between A & C are
100 - 89 = 21
A[1-20] & C[1-20] since you have A+B

So both A & C have a valid domain of [1,78] since
B has a domain of [21,89] and that A+B+C = 100 and all three are + integers

However the Domains of Both A & C depend on the initial value of B.
If B is small then either A or C or A & C can be large
If B is large then both A & C should be small. 

Let's say that the first random value for B is its max 89
Then A or C would be 100 - 89 - 1 giving a range of values [1,10] for either A or C's domain

Let's say that the first random value for B is its min 21
Then A or C would be 100 - 21 - 1 giving a range of values [1,78] for either A or C's domain

We can combine these domains to look as such: [1, 10...78]

We can see above that in both calculations we have 100 - 1 that is constant

The final pseudo mathematical code would be:
99 - B[21,89] = A[1,10...78] + C[1,10...78] where A + C > 8

We can now use the above assessments of their full domains to design an algorithm as others have already stated:

// First use a random number generated to find B in the range of [21,89]
// Then you can find a random number for either A or C in the Range of [1,10...78] 
// depending on what B is. Remember if B is small then either A or C can be large.
// And if B is large then A & C should be fairly small.
// Once you have the 2nd value just calculate the third.

Answer 2

First, EQ3 is implied in EQ1+EQ2. (d1+d3=100-d2>100-90=10)

And the core problem is: Do you need a uniform distribution over all possible combinations?

If yes, every combination need to be calculated first (in this case, not in every case).

If no, you can use a more efficient random function.

#include <iostream>
#include <random>
#include <vector>

std::default_random_engine generator;
std::vector<std::pair<int, int> > results;

void prepareUniformResult()
{
    for(int d2 = 21; d2 <= 89; d2 ++)
        for(int d1 = 1; d1 <= 99-d2; d1 ++)
        results.push_back(std::make_pair(d1, d2));
}

void randomThreeUniform(int &d1, int &d2, int &d3)
{
    std::uniform_int_distribution<int> idist(0, results.size()-1);
    int ind = idist(generator);
    d1 = results.at(ind).first;
    d2 = results.at(ind).second;
    d3 = 100 - d1 - d2;
}

void randomThreeNonUniform(int &d1, int &d2, int &d3)
{
    std::uniform_int_distribution<int> d2dist(21,89);
    d2 = d2dist(generator);
    std::uniform_int_distribution<int> d1dist(1,100-d2-1);
    d1 = d1dist(generator);
    d3 = 100 - d1 - d2;
}
int main()
{
    int d1,d2,d3;

    prepareUniformResult();

    std::cout<<"Non-uniform results:"<<std::endl;
    for(int i=0;i<10;i++)
    {
        randomThreeNonUniform(d1, d2, d3);
        std::cout<<d1<<" "<<d2<<" "<<d3<<std::endl;
    }

    std::cout<<"Uniform results:"<<std::endl;
    for(int i=0;i<10;i++)
    {
        randomThreeUniform(d1, d2, d3);
        std::cout<<d1<<" "<<d2<<" "<<d3<<std::endl;
    }
    return 0;
}

We can uniform sampled points (blue points) are more well-distributed than non-uniformed points (orange ones).

Answer 3

First note that you only need two random numbers per trial, since the third is constrained by their having to sum to 100.

Second note, if distance2 is less than 90, and the sum is 100, then distance1 + distance3 must be 11 or more. So EQ3 must hold if EQ2 holds.

Sampling using Mersenne Twister (in the absence of any other information) is probably the best way, and reject combinations that don't satisfy the constraints. To get started, sample distance1 and distance2 between [0, 100] regardless of efficiency and improve if necessary but take absolutely exquisite care that you don't introduce statistical bias in reducing the number of rejected combinations (and that is the hard bit).

Note that Mersenne Twister has been part of the C++ Standard since C++11: to get things started use something like

#include <random>
std::random_device rd;
std::mt19937 rng(rd());
std::uniform_int_distribution<int> uni(0, 100);
auto random_integer = uni(rng);

Answer 4

Equation 3 is irrelevant. It is assumed by equation 2.

Distance 1 can go from 1 to 80, Distance 2 can go from 21 to 99 - Distance 1, Distance 3 is then given by 100 - Distance 1 - Distance 2.

So, you need to decide what sort of distribution you want. Do you want a uniform distribution of Distance 1, in which case Distance 2 will have a distribution bunched up to the lower end. Or a uniform distribution on Distance 2? Or do you want to enumerate the allowed states and select one at random, giving all equal weight? Do that by creating a half matrix with Distance 1 the major axis and Distance 2 the minor.

Answer 5

distance1 + distance3 > 8 (EQ3)

If we take distance3 as 8, EQ3 holds good since distance1 is a positive number (>= 1).

20 < distance2 < 90 (EQ2)

Let distance2 be 21

Now calculate distance3 = 100 - distance1 - distance2. (constant value)

No need of generating random numbers ;)

If you really need that, just increment one of the variables by k and decrement the other by the same to achieve another combination. Just make sure this doesn't break EQ2.

Answer 6

1. Pick a random value for distance2 in the appropriate range.
2. Pick a random value for distance1 in the appropriate range (based on the value of distance2).
3. Calculate distance3.