# Java：具有非均匀分布的随机整数

` `Random r=new Random(); int n=r.nextInt(k)+1;` `

` `public static int getLinnearRandomNumber(int maxSize){ //Get a linearly multiplied random number int randomMultiplier = maxSize * (maxSize + 1) / 2; Random r=new Random(); int randomInt = r.nextInt(randomMultiplier); //Linearly iterate through the possible values to find the correct one int linearRandomNumber = 0; for(int i=maxSize; randomInt >= 0; i--){ randomInt -= i; linearRandomNumber++; } return linearRandomNumber; }` `

` `public static int getYourPositiveFunctionRandomNumber(int startIndex, int stopIndex) { //Generate a random number whose value ranges from 0.0 to the sum of the values of yourFunction for all the possible integer return values from startIndex to stopIndex. double randomMultiplier = 0; for (int i = startIndex; i <= stopIndex; i++) { randomMultiplier += yourFunction(i);//yourFunction(startIndex) + yourFunction(startIndex + 1) + .. yourFunction(stopIndex -1) + yourFunction(stopIndex) } Random r = new Random(); double randomDouble = r.nextDouble() * randomMultiplier; //For each possible integer return value, subtract yourFunction value for that possible return value till you get below 0. Once you get below 0, return the current value. int yourFunctionRandomNumber = startIndex; randomDouble = randomDouble - yourFunction(yourFunctionRandomNumber); while (randomDouble >= 0) { yourFunctionRandomNumber++; randomDouble = randomDouble - yourFunction(yourFunctionRandomNumber); } return yourFunctionRandomNumber; }` `

` `* ** *** **** *****` `

` `1 2 3 4 5 6 7 8 9 10 11 12 13 14 15` `

` `// Assume k is given, via parameter or otherwise int k; // Assume also that r has already been initialized as a valid Random instance Random r = new Random(); // First, generate a number from 1 to T_k int triangularK = k * (k + 1) / 2; int x = r.nextInt(triangularK) + 1; // Next, figure out which bucket x fits into, bounded by // triangular numbers by taking the triangular root // We're dealing strictly with positive integers, so we can // safely ignore the - part of the +/- in the triangular root equation double triangularRoot = (Math.sqrt(8 * x + 1) - 1) / 2; int bucket = (int) Math.ceil(triangularRoot); // Buckets start at 1 as the least likely; we want k to be the least likely int n = k - bucket + 1;` `

1. 你有两个直angular三angular形，每个`kxh`一个公共的斜边。 复合形状是一个`kxh`矩形。
2. 以相等的概率生成落在矩形内每个点上的随机点。
3. 一半的时间会落在一个三angular形中，一半的时间落在另一个三angular形中。
4. 假设点落在下三angular。
• 三angular形基本上描述了PMF，并且每个x值上的三angular形的“高度”描述了该点将具有这样的x值的概率。 （请记住，我们只处理下三angular形中的点。）所以通过产生x值。
5. 假设该点落在上三angular。
• 反转坐标并按照上面的三angular形处理。

` `int [] indexBound = new int[k]; int prevBound =0; for(int i=0;i<k;i++){ indexBound[i] = prevBound+prob(i); prevBound=indexBound[i]; } int r = new Random().nextInt(prevBound); for(int i=0;i<k;i++){ if(r > indexBound[i]; return i; }` `

` `class DiscreteDistribution { // cumulative distribution final private double[] cdf; final private int k; public DiscreteDistribution(Function<Integer, Double> pdf, int k) { this.k = k; this.cdf = new double[k]; double S = 0; for (int i = 0; i < k; ++i) { double p = pdf.apply(i+1); S += p; this.cdf[i] = S; } for (int i = 0; i < k; ++i) { this.cdf[i] /= S; } } /** * transform a cumulative distribution between 0 (inclusive) and 1 (exclusive) * to an integer between 1 and k. */ public int transform(double q) { // exercise for the reader: // binary search on cdf for the lowest index i where q < cdf[i] // return this number + 1 (to get into a 1-based index. // If q >= 1, return k. } }` `

` `int a = 1; // lower bound, inclusive int b = k; // upper bound, exclusive double weightedRand = Math.sqrt(rand.nextDouble()); // use triangular distribution weightedRand = 1.0 - weightedRand; // invert the distribution (greater density at bottom) int result = (int) Math.floor((ba) * weightedRand); result += a; // offset by lower bound if(result >= b) result = a; // handle the edge case` `

` `int k = /* possible values */ int[] results = new int[k*(k+1)/2]; for(int i=1,r=0;i<=k;i++) for(int j=0;j<=ki;j++) results[r++] = i; // k=4 => { 1,1,1,1,2,2,2,3,3,4 } // to get a value with a given distribution. int n = results[random.nextInt(results.length)];` `

` `int k = int[] buckets = new int[k+1]; for(int i=1;i<k;i++) buckets[i] = buckets[i-1] + k - i + 1; int r = random.nextInt(buckets[buckets.length-1]); int n = Arrays.binarySearch(buckets, r); n = n < 0 ? -n : n + 1;` `