How to create uneven range number random function?

问题:

We know that the classic range random function is like this:

public static final int random(final int min, final int max) {
    Random rand = new Random();
    return min + rand.nextInt(max - min + 1);  // +1 for including the max
}

I want to create algorithm function for generating number randomly at range between 1..10, but with uneven possibilities like:
1) 1,2,3 -> 3/6 (1/2)
2) 4,5,6,7 -> 1/6
3) 8,9,10 -> 2/6 (1/3)

Above means the function has 1/2 chance to return number between 1 and 3, 1/6 chance to return number between 4 and 7, and 1/3 chance to return number between 8 and 10.

Anyone know the algorithm?

UPDATE:
Actually the range between 1..10 is just served as an example. The function that I want to create would apply for any range of numbers, such as: 1..10000, but the rule is still same: 3/6 for top range (30% portion), 1/6 for middle range (next 40% portion), and 2/6 for bottom range (last 30% portion).

回答1:

Use the algorithm:

int temp = random(0,5);
if (temp <= 2) {
  return random(1,3);
} else if (temp <= 3) {
 return random(4,7);
} else  {
 return random(8,10);
}

This should do the trick.

EDIT: As requested in your comment:

int first_lo = 1, first_hi = 3000; // 1/2 chance to choose a number in [first_lo, first_hi]
int second_lo = 3001, second_hi = 7000; // 1/6 chance to choose a number in [second_lo, second_hi] 
int third_lo = 7001, third_hi = 10000;// 1/3 chance to choose a number in [third_lo, third_hi] 
int second
int temp = random(0,5);
if (temp <= 2) {
  return random(first_lo,first_hi);
} else if (temp <= 3) {
 return random(second_lo,second_hi);
} else  {
 return random(third_lo,third_hi);
}

回答2:

You can fill an array of the desired numbers with the desired density, and then generate a random index and take the corresponding element. I think it is faster a bit, but propably it is not so important. Something like that, it's not the correct solution, just an example:

1,1,1,2,2,2,3,3,3,4,5,6 ...

Or you can define domains first with if statements, and then generate a simple number from that domain.

int x = random(1,6)
if (x < 4) return random(1, 3);
if (x < 5) return random(4, 7);
return random(8, 10);

回答3:

Roll a 72-sided die to choose from the following array:

// Each row represents 1/6 of the space
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7,
 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9,
 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10]

回答4:

final int lut[] = [
  1, 1, 1,
  2, 2, 2,
  3, 3, 3,
  4,
  5,
  6,
  7,
  8, 8,
  9, 9,
  10, 10
];

int uneven_random = lut[random.nextInt(lut.length)];

Or something along those lines...

回答5:

This might help if you're using whole numbers:

You need to use the following function:

f : A -> B

B = [b0, b1] represents the range of values you want from your random number generator

A = [b0, 2 * b1] so that the last branch of f actually reaches b1

f(x) = step((x / 3) , 
    f(x) is part of interval [b0, length(B)/3]
f(x) = step(x)  + E,   
    f(x) is part of interval [length(B) / 3, 2 * length(B) / 3],
    E is a constant that makes sure the function is continuous
f(x) = step(x / 2) + F,   
    f(x) is part of interval [2 * length(B) / 3, length(B)]
    F is a constant that makes sure the function is continuous

Explanation: it will take 3 times more numbers to get the same value on the first branch than it would on the second. So the probability to get a number on the first branch is 3 times than on the second, with values evenly distributed from a random number generator. The same applies for the 3rd branch.

I hope this helps!

EDIT: modified the intervals, you have to tweak it a bit but this is my general idea.

回答6:

As requested, here is my code (based on izomorphius's code) that hopefully solve my problem:

private static Random rand = new Random();

public static int rangeRandom(final int min, final int max) {
    return min + rand.nextInt(max - min + 1);  // +1 for including the max
}

/**
 * 
 * @param min           The minimum range number
 * @param max           The maximum range number
 * @param weights       Array containing distributed weight values. The sum of values must be 1.0 
 * @param chances       Array containing distributed chance values. The array length must be same with weights and the sum of values must be 1.0 
 * @return              Random number
 * @throws Exception    Probably should create own exception, but I use default Exception for simplicity
 */
public static int weightedRangeRandom(final int min, final int max, final float[] weights, final float[] chances) throws Exception {
    // some validations
    if (weights.length != chances.length) {
        throw new Exception("Length of weight & chance must be equal");
    }

    int len = weights.length;

    float sumWeight = 0, sumChance = 0;
    for (int i=0; i<len; ++i) {
        sumWeight += weights[i];
        sumChance += chances[i];
    }
    if (sumWeight != 1.0 || sumChance != 1.0) {
        throw new Exception("Sum of weight/chance must be 1.0");
    }

    // find the random number
    int tMin = min, tMax;
    int rangeLen = max - min + 1;

    double n = Math.random();
    float c = 0;
    for (int i=0; i<len; ++i) {
        if (i != (len-1)) {
            tMax = tMin + Math.round(weights[i] * rangeLen) - 1;
        }
        else {
            tMax = max;
        }

        c += chances[i];
        if (n < c) {
            return rangeRandom(tMin, tMax);
        }
        tMin = tMax + 1;
    }

    throw new Exception("You shouldn't end up here, something got to be wrong!");
}

Usage example:

int result = weightedRangeRandom(1, 10, new float[] {0.3f, 0.4f, 0.3f}, 
    new float[] {1f/2, 1f/6, 1f/3});

The code might still has an inaccuracy in distributing the subrange boundaries (tMin & tMax) because of division by weight resulted in decimal value. But it's unavoidable I guess, because the range numbers are integers.

Some input validations might be required, but I left out for sake of simplicity.

Critics, corrections and reviews are gratefully welcomed :)