Generate random numbers in increments

I need to generate n random numbers between a and b, but any two numbers cannot have a difference of less than c. All variables except n are floats (n is an int).

Solutions are preferred in java, but C/C++ is okay too.

Here is what code I have so far.:

static float getRandomNumberInRange(float min, float max) {
    return (float) (min + (Math.random() * (ma开发者_StackOverflow社区x - min)));
}

static float[] randomNums(float a, float b, float c, int n) {
    float minDistance = c;
    float maxDistance = (b - a) - (n - 1) * c;
    float[] randomNumArray = new float[n];
    float random = getRandomNumberInRange(minDistance, maxDistance);
    randomNumArray[0] = a + random;
    for (int x = 1; x < n; x++) {
        maxDistance = (b - a) - (randomNumArray[x - 1]) - (n - x - 1) * c;
        random = getRandomNumberInRange(minDistance, maxDistance);
        randomNumArray[x] = randomNumArray[x - 1] + random;
    }
    return randomNumArray;
}

If I run the function as such (10 times), I get the following output:

Input: randomNums(-1f, 1f, 0.1f, 10)

[-0.88, 0.85, 1.23, 1.3784, 1.49, 1.59, 1.69, 1.79, 1.89, 1.99]

[-0.73, -0.40, 0.17, 0.98, 1.47, 1.58, 1.69, 1.79, 1.89, 1.99]

[-0.49, 0.29, 0.54, 0.77, 1.09, 1.56, 1.69, 1.79, 1.89, 1.99]

I think a reasonable approach can be the following:

1. Total "space" is (b - a)
2. Remove the minimum required space (n-1)*c to obtain the remaining space
3. Shot (n-1) random numbers between 0 and 1 and scale them so that the sum is this just computed "optional space". Each of them will be a "slice" of space to be used.
4. First number is a
5. For each other number add c and the next "slice" to the previous number. Last number will be b.

If you don't want first and last to match a and b exactly then just create n+1 slices instead of n-1 and start with a+slice[0] instead of a.

The main idea is that once you remove the required spacing between the points (totalling (n-1)*c) the problem is just to find n-1 values so that the sum is the prescribed "optional space". To do this with a uniform distribution just shoot n-1 numbers, compute the sum and uniformly scale those numbers so that the sum is instead what you want by multiplying each of them by the constant factor k = wanted_sum / current_sum.

To obtain the final result you just use as spacing between a value and the previous one the sum of the mandatory part c and one of the randomly sampled variable parts.

An example in Python of the code needed for the computation is the following

space = b - a
slack = space - (n - 1)*c
slice = [random.random() for i in xrange(n-1)]  # Pick (n-1) random numbers 0..1
k = slack / sum(slice)                          # Compute needed scaling
slice = [x*k for x in slice]                    # Scale to get slice sizes
result = [a]
for i in xrange(n-1):
    result.append(result[-1] + slice[i] + c)

If you have random number X and you want another random number Y which is a minimum of A from X and a maximum of B from X, why not write that in your code?

float nextRandom(float base, float minDist, float maxDist) {
  return base + minDist + (((float)Math.random()) * (maxDist - minDist));
}

by trying to keep the base out of the next number routine, you add a lot of complexity to your algorithm.

Though this does not exactly do what you need and does not incorporate the techinque being described in this thread, I believe that this code will prove to be useful as it will do what it seems like you want.

static float getRandomNumberInRange(float min, float max)
{
    return (float) (min + (Math.random() * ((max - min))));
}
 static float[] randomNums(float a, float b, float c, int n) 
{
    float averageDifference=(b-a)/n; 
    float[] randomNumArray = new float[n];
    int random;
    randomNumArray[0]=a+averageDifference/2;
    for (int x = 1; x < n; x++)
        randomNumArray[x]=randomNumArray[x-1]+averageDifference;
    for (int x = 0; x < n; x++)
    {
        random = getRandomNumberInRange(-averageDifference/2, averageDifference/2);
        randomNumArray[x]+=random;
    }
    return randomNumArray;
}

I need to generate n random numbers between a and b, but any two numbers cannot have a difference of less than c. All variables except n are floats (n is an int).

Solutions are preferred in java, but C/C++ is okay too.

First, what distribution? I'm going to assume a uniform distribution, but with that caveat that "any two numbers cannot have a difference of less than c". What you want is called "rejection sampling". There's a wikipedia article on the subject, plus a whole lot of other references on the 'net and in books (e.g. http://www.columbia.edu/~ks20/4703-Sigman/4703-07-Notes-ARM.pdf). Pseudocode, using some function random_uniform() that returns a random number drawn from U[0,1], and assuming a 1-based array (many languages use a 0-based array):

function generate_numbers (a, b, c, n, result)
  result[1] = a + (b-a)*random_uniform()
  for index from 2 to n
    rejected = true
    while (rejected)
      result[index] = a + (b-a)*random_uniform()
      rejected = abs (result[index] < result[index-1]) < c
    end
  end

Your solution was almost correct, here is the fix:

maxDistance = b - (randomNumArray[x - 1]) - (n - x - 1) * c;

I would do this by just generating n random numbers between a and b. Then I would sort them and get the first order differences, kicking out any numbers that generate a difference less than c, leaving me with m numbers. If m < n, I would just do it again, this time for n - m numbers, add those numbers to my original results, sort again, generate differences...and so on until I have n numbers.

Note, first order differences means x[1] - x[0], x[2] - x[1] and so on.

I don't have time to write this out in C but in R, it's pretty easy:

getRands<-function(n,a,b,c){
   r<-c()
   while(length(r) < n){
      r<-sort(c(r,runif(n,a,b)))
      r<-r[-(which(diff(r) <= c) + 1 )]
   }
   r


}

Note that if you are too aggresive with c relative to a and b, this kind of solution might take a long time to converge, or not converge at all if n * C > b -a

Also note, I don't mean for this R code to be a fully formed, production ready piece of code, just an illustration of the algorithm (for those who can follow R).

How about using a shifting range as you generate numbers to ensure that they don't appear too close?

static float[] randomNums(float min, float max, float separation, int n) {
    float rangePerNumber = (max - min) / n;

    // Check separation and range are consistent.
    assert (rangePerNumber >= separation) : "You have a problem.";

    float[] randomNumArray = new float[n];

    // Set range for first random number
    float lo = min;
    float hi = lo + rangePerNumber;

    for (int i = 0; i < n; ++i) {
        float random = getRandomNumberInRange(lo, hi);

        // Shift range for next random number.
        lo = random + separation;
        hi = lo + rangePerNumber;

        randomNumArray[i] = random;
    }
    return randomNumArray;
}

I know you already accepted an answer, but I like this problem. I hope it's unique, I haven't gone through everyone's answers in detail just yet, and I need to run, so I'll just post this and hope it helps.

Think of it this way: Once you pick your first number, you have a chunk +/- c that you can no longer pick in.

So your first number is

range1=b-a
x=Random()*range1+a

At this point, x is somewhere between a and b (assuming Random() returns in 0 to 1). Now, we mark out the space we can no longer pick in

excludedMin=x-c
excludedMax=x+c 

If x is close to either end, then it's easy, we just pick in the remaining space

if (excludedMin<=a)
{
  range2=b-excludedMax
  y=Random()*range2+excludedMax
}

Here, x is so close to a, that you won't get y between a and x, so you just pick between x+c and b. Likewise:

else if (excludedMax>=b)
{
   range2=excludedMin-a
   y=Random()*range2+a
}

Now if x is somewhere in the middle, we have to do a little magic

else
{
  range2=b-a-2*c
  y=Random()*range2+a
  if (y>excludedMin) y+=2*c
}

What's going on here? Well, we know that the range y can lie in, is 2*c smaller than the whole space, so we pick a number somewhere in that smaller space. Now, if y is less than excludedMin, we know y "is to the left" of x-c, and we're all ok. However, if y>excluded min, we add 2*c (the total excluded space) to it, to ensure that it's greater than x+c, but it'll still be less than b because our range was reduced.

Now, it's easy to expand so n numbers, each time you just reduce the range by the excluded space among any of the other points. You continue until the excluded space equals the original range (b-a).

I know it's bad form to do a second answer, but I just thought of one...use a recursive search of the space:

Assume a global list of points: points

FillRandom(a,b,c)
{
  range=b-a;
  if (range>0)
  {
    x=Random()*range+a
    points.Append(x)
    FillRandom(a,x-c,c)
    FillRandom(x+c,b,c)
  }
}

I'll let you follow the recursion, but at the end, you'll have a list in points that fills the space with density 1/c