CS计算机代考程序代写 algorithm Java package byow.Core;

package byow.Core;

import java.util.Random;

/**
* A library of static methods to generate pseudo-random numbers from
* different distributions (bernoulli, uniform, gaussian, discrete,
* and exponential). Also includes methods for shuffling an array and
* other randomness related stuff you might want to do. Feel free to
* modify this file.
*

* Adapted from https://introcs.cs.princeton.edu/java/22library/StdRandom.java.html
*
*/
public class RandomUtils {

/**
* Returns a random real number uniformly in [0, 1).
*
* @return a random real number uniformly in [0, 1)
*/
public static double uniform(Random random) {
return random.nextDouble();
}

/**
* Returns a random integer uniformly in [0, n).
*
* @param n number of possible integers
* @return a random integer uniformly between 0 (inclusive) and {@code n} (exclusive)
* @throws IllegalArgumentException if {@code n <= 0} */ public static int uniform(Random random, int n) { if (n <= 0) { throw new IllegalArgumentException("argument must be positive: " + n); } return random.nextInt(n); } /** * Returns a random long integer uniformly in [0, n). * * @param n number of possible {@code long} integers * @return a random long integer uniformly between 0 (inclusive) and {@code n} (exclusive) * @throws IllegalArgumentException if {@code n <= 0} */ public static long uniform(Random random, long n) { if (n <= 0L) { throw new IllegalArgumentException("argument must be positive: " + n); } // https://docs.oracle.com/javase/8/docs/api/java/util/Random.html#longs-long-long-long- long r = random.nextLong(); long m = n - 1; // power of two if ((n & m) == 0L) { return r & m; } // reject over-represented candidates long u = r >>> 1;
while (u + m – (r = u % n) < 0L) { u = random.nextLong() >>> 1;
}
return r;
}

///////////////////////////////////////////////////////////////////////////
// STATIC METHODS BELOW RELY ON JAVA.UTIL.RANDOM ONLY INDIRECTLY VIA
// THE STATIC METHODS ABOVE.
///////////////////////////////////////////////////////////////////////////

/**
* Returns a random integer uniformly in [a, b).
*
* @param a the left endpoint
* @param b the right endpoint
* @return a random integer uniformly in [a, b)
* @throws IllegalArgumentException if {@code b <= a} * @throws IllegalArgumentException if {@code b - a >= Integer.MAX_VALUE}
*/
public static int uniform(Random random, int a, int b) {
if ((b <= a) || ((long) b - a >= Integer.MAX_VALUE)) {
throw new IllegalArgumentException(“invalid range: [” + a + “, ” + b + “)”);
}
return a + uniform(random, b – a);
}

/**
* Returns a random real number uniformly in [a, b).
*
* @param a the left endpoint
* @param b the right endpoint
* @return a random real number uniformly in [a, b)
* @throws IllegalArgumentException unless {@code a < b} */ public static double uniform(Random random, double a, double b) { if (!(a < b)) { throw new IllegalArgumentException("invalid range: [" + a + ", " + b + ")"); } return a + uniform(random) * (b - a); } /** * Returns a random boolean from a Bernoulli distribution with success * probability p.
*
* @param p the probability of returning {@code true}
* @return {@code true} with probability {@code p} and
* {@code false} with probability {@code p}
* @throws IllegalArgumentException unless {@code 0} ≤ {@code p} ≤ {@code 1.0}
*/
public static boolean bernoulli(Random random, double p) {
if (!(p >= 0.0 && p <= 1.0)) { throw new IllegalArgumentException("probability p must be between 0.0 and 1.0: " + p); } return uniform(random) < p; } /** * Returns a random boolean from a Bernoulli distribution with success * probability 1/2. * * @return {@code true} with probability 1/2 and * {@code false} with probability 1/2 */ public static boolean bernoulli(Random random) { return bernoulli(random, 0.5); } /** * Returns a random real number from a standard Gaussian distribution. * * @return a random real number from a standard Gaussian distribution * (mean 0 and standard deviation 1). */ public static double gaussian(Random random) { // use the polar form of the Box-Muller transform double r, x, y; do { x = uniform(random, -1.0, 1.0); y = uniform(random, -1.0, 1.0); r = x * x + y * y; } while (r >= 1 || r == 0);
return x * Math.sqrt(-2 * Math.log(r) / r);

// Remark: y * Math.sqrt(-2 * Math.log(r) / r)
// is an independent random gaussian
}

/**
* Returns a random real number from a Gaussian distribution with mean μ
* and standard deviation σ.
*
* @param mu the mean
* @param sigma the standard deviation
* @return a real number distributed according to the Gaussian distribution
* with mean {@code mu} and standard deviation {@code sigma}
*/
public static double gaussian(Random random, double mu, double sigma) {
return mu + sigma * gaussian(random);
}

/**
* Returns a random integer from a geometric distribution with success
* probability p.
*
* @param p the parameter of the geometric distribution
* @return a random integer from a geometric distribution with success
* probability {@code p}; or {@code Integer.MAX_VALUE} if
* {@code p} is (nearly) equal to {@code 1.0}.
* @throws IllegalArgumentException unless {@code p >= 0.0} and {@code p <= 1.0} */ public static int geometric(Random random, double p) { if (!(p >= 0.0 && p <= 1.0)) { throw new IllegalArgumentException("probability p must be between 0.0 and 1.0: " + p); } // using algorithm given by Knuth return (int) Math.ceil(Math.log(uniform(random)) / Math.log(1.0 - p)); } /** * Returns a random integer from a Poisson distribution with mean λ. * * @param lambda the mean of the Poisson distribution * @return a random integer from a Poisson distribution with mean {@code lambda} * @throws IllegalArgumentException unless {@code lambda > 0.0} and not infinite
*/
public static int poisson(Random random, double lambda) {
if (!(lambda > 0.0)) {
throw new IllegalArgumentException(“lambda must be positive: ” + lambda);
}
if (Double.isInfinite(lambda)) {
throw new IllegalArgumentException(“lambda must not be infinite: ” + lambda);
}
// using algorithm given by Knuth
// see http://en.wikipedia.org/wiki/Poisson_distribution
int k = 0;
double p = 1.0;
double expLambda = Math.exp(-lambda);
do {
k++;
p *= uniform(random);
} while (p >= expLambda);
return k – 1;
}

/**
* Returns a random real number from the standard Pareto distribution.
*
* @return a random real number from the standard Pareto distribution
*/
public static double pareto(Random random) {
return pareto(random, 1.0);
}

/**
* Returns a random real number from a Pareto distribution with
* shape parameter α.
*
* @param alpha shape parameter
* @return a random real number from a Pareto distribution with shape
* parameter {@code alpha}
* @throws IllegalArgumentException unless {@code alpha > 0.0}
*/
public static double pareto(Random random, double alpha) {
if (!(alpha > 0.0)) {
throw new IllegalArgumentException(“alpha must be positive: ” + alpha);
}
return Math.pow(1 – uniform(random), -1.0 / alpha) – 1.0;
}

/**
* Returns a random real number from the Cauchy distribution.
*
* @return a random real number from the Cauchy distribution.
*/
public static double cauchy(Random random) {
return Math.tan(Math.PI * (uniform(random) – 0.5));
}

/**
* Returns a random integer from the specified discrete distribution.
*
* @param probabilities the probability of occurrence of each integer
* @return a random integer from a discrete distribution:
* {@code i} with probability {@code probabilities[i]}
* @throws IllegalArgumentException if {@code probabilities} is {@code null}
* @throws IllegalArgumentException if sum of array entries is not (very nearly) equal to 1.0
* @throws IllegalArgumentException unless {@code probabilities[i] >= 0.0} for each index i
*/
public static int discrete(Random random, double[] probabilities) {
if (probabilities == null) {
throw new IllegalArgumentException(“argument array is null”);
}
double eps = 1E-14;
double sum = 0.0;
for (int i = 0; i < probabilities.length; i++) { if (!(probabilities[i] >= 0.0)) {
throw new IllegalArgumentException(“array entry ” + i + ” must be nonnegative: ”
+ probabilities[i]);
}
sum += probabilities[i];
}
if (sum > 1.0 + eps || sum < 1.0 - eps) { throw new IllegalArgumentException("sum of array entries does not approximately " + "equal 1.0: " + sum); } // the for loop may not return a value when both r is (nearly) 1.0 and when the // cumulative sum is less than 1.0 (as a result of floating-point roundoff error) while (true) { double r = uniform(random); sum = 0.0; for (int i = 0; i < probabilities.length; i++) { sum = sum + probabilities[i]; if (sum > r) {
return i;
}
}
}
}

/**
* Returns a random integer from the specified discrete distribution.
*
* @param frequencies the frequency of occurrence of each integer
* @return a random integer from a discrete distribution:
* i with probability proportional to frequencies[i]
* @throws IllegalArgumentException if frequencies is null
* @throws IllegalArgumentException if all array entries are 0
* @throws IllegalArgumentException if frequencies[i] is negative for any index i
* @throws IllegalArgumentException if sum of frequencies exceeds Integer.MAX_VALUE (2^31 – 1)
*/
public static int discrete(Random random, int[] frequencies) {
if (frequencies == null) {
throw new IllegalArgumentException(“argument array is null”);
}
long sum = 0;
for (int i = 0; i < frequencies.length; i++) { if (frequencies[i] < 0) { throw new IllegalArgumentException("array entry " + i + " must be nonnegative: " + frequencies[i]); } sum += frequencies[i]; } if (sum == 0) { throw new IllegalArgumentException("at least one array entry must be positive"); } if (sum >= Integer.MAX_VALUE) {
throw new IllegalArgumentException(“sum of frequencies overflows an int”);
}

// pick index i with probabilitity proportional to frequency
double r = uniform(random, (int) sum);
sum = 0;
for (int i = 0; i < frequencies.length; i++) { sum += frequencies[i]; if (sum > r) {
return i;
}
}

// can’t reach here
assert false;
return -1;
}

/**
* Returns a random real number from an exponential distribution
* with rate λ.
*
* @param lambda the rate of the exponential distribution
* @return a random real number from an exponential distribution with
* rate {@code lambda}
* @throws IllegalArgumentException unless {@code lambda > 0.0}
*/
public static double exp(Random random, double lambda) {
if (!(lambda > 0.0)) {
throw new IllegalArgumentException(“lambda must be positive: ” + lambda);
}
return -Math.log(1 – uniform(random)) / lambda;
}

/**
* Rearranges the elements of the specified array in uniformly random order.
*
* @param a the array to shuffle
* @throws IllegalArgumentException if {@code a} is {@code null}
*/
public static void shuffle(Random random, Object[] a) {
validateNotNull(a);
int n = a.length;
for (int i = 0; i < n; i++) { int r = i + uniform(random, n - i); // between i and n-1 Object temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearranges the elements of the specified array in uniformly random order. * * @param a the array to shuffle * @throws IllegalArgumentException if {@code a} is {@code null} */ public static void shuffle(Random random, double[] a) { validateNotNull(a); int n = a.length; for (int i = 0; i < n; i++) { int r = i + uniform(random, n - i); // between i and n-1 double temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearranges the elements of the specified array in uniformly random order. * * @param a the array to shuffle * @throws IllegalArgumentException if {@code a} is {@code null} */ public static void shuffle(Random random, int[] a) { validateNotNull(a); int n = a.length; for (int i = 0; i < n; i++) { int r = i + uniform(random, n - i); // between i and n-1 int temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearranges the elements of the specified array in uniformly random order. * * @param a the array to shuffle * @throws IllegalArgumentException if {@code a} is {@code null} */ public static void shuffle(Random random, char[] a) { validateNotNull(a); int n = a.length; for (int i = 0; i < n; i++) { int r = i + uniform(random, n - i); // between i and n-1 char temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearranges the elements of the specified subarray in uniformly random order. * * @param a the array to shuffle * @param lo the left endpoint (inclusive) * @param hi the right endpoint (exclusive) * @throws IllegalArgumentException if {@code a} is {@code null} * @throws IllegalArgumentException unless {@code (0 <= lo) && (lo < hi) && (hi <= a.length)} */ public static void shuffle(Random random, Object[] a, int lo, int hi) { validateNotNull(a); validateSubarrayIndices(lo, hi, a.length); for (int i = lo; i < hi; i++) { int r = i + uniform(random, hi - i); // between i and hi-1 Object temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearranges the elements of the specified subarray in uniformly random order. * * @param a the array to shuffle * @param lo the left endpoint (inclusive) * @param hi the right endpoint (exclusive) * @throws IllegalArgumentException if {@code a} is {@code null} * @throws IllegalArgumentException unless {@code (0 <= lo) && (lo < hi) && (hi <= a.length)} */ public static void shuffle(Random random, double[] a, int lo, int hi) { validateNotNull(a); validateSubarrayIndices(lo, hi, a.length); for (int i = lo; i < hi; i++) { int r = i + uniform(random, hi - i); // between i and hi-1 double temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Rearranges the elements of the specified subarray in uniformly random order. * * @param a the array to shuffle * @param lo the left endpoint (inclusive) * @param hi the right endpoint (exclusive) * @throws IllegalArgumentException if {@code a} is {@code null} * @throws IllegalArgumentException unless {@code (0 <= lo) && (lo < hi) && (hi <= a.length)} */ public static void shuffle(Random random, int[] a, int lo, int hi) { validateNotNull(a); validateSubarrayIndices(lo, hi, a.length); for (int i = lo; i < hi; i++) { int r = i + uniform(random, hi - i); // between i and hi-1 int temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * Returns a uniformly random permutation of n elements.
*
* @param n number of elements
* @return an array of length {@code n} that is a uniformly random permutation
* of {@code 0}, {@code 1}, …, {@code n-1}
* @throws IllegalArgumentException if {@code n} is negative
*/
public static int[] permutation(Random random, int n) {
if (n < 0) { throw new IllegalArgumentException("argument is negative"); } int[] perm = new int[n]; for (int i = 0; i < n; i++) { perm[i] = i; } shuffle(random, perm); return perm; } /** * Returns a uniformly random permutation of k of n elements.
*
* @param n number of elements
* @param k number of elements to select
* @return an array of length {@code k} that is a uniformly random permutation
* of {@code k} of the elements from {@code 0}, {@code 1}, …, {@code n-1}
* @throws IllegalArgumentException if {@code n} is negative
* @throws IllegalArgumentException unless {@code 0 <= k <= n} */ public static int[] permutation(Random random, int n, int k) { if (n < 0) { throw new IllegalArgumentException("argument is negative"); } if (k < 0 || k > n) {
throw new IllegalArgumentException(“k must be between 0 and n”);
}
int[] perm = new int[k];
for (int i = 0; i < k; i++) { int r = uniform(random, i + 1); // between 0 and i perm[i] = perm[r]; perm[r] = i; } for (int i = k; i < n; i++) { int r = uniform(random, i + 1); // between 0 and i if (r < k) { perm[r] = i; } } return perm; } // throw an IllegalArgumentException if x is null // (x can be of type Object[], double[], int[], ...) private static void validateNotNull(Object x) { if (x == null) { throw new IllegalArgumentException("argument is null"); } } // throw an exception unless 0 <= lo <= hi <= length private static void validateSubarrayIndices(int lo, int hi, int length) { if (lo < 0 || hi > length || lo > hi) {
throw new IllegalArgumentException(“subarray indices out of bounds: [” + lo + “, ”
+ hi + “)”);
}
}
}