
Method Summary
Modifier and TypeMethodDescriptionstatic int[]
sample
(int n, double p) Generates a random sample, without replacement, from the set of integers in the interval [0, n).static int[]
sample
(int n, double p, RandomGenerator r) Generates a random sample, without replacement, from the set of integers in the interval [0, n).static int[]
sample
(int n, int k, int[] result) Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n).static int[]
sample
(int n, int k, int[] result, RandomGenerator gen) Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n).static int[]
sampleInsertion
(int n, int k, int[] result) Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n).static int[]
sampleInsertion
(int n, int k, int[] result, RandomGenerator gen) Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n).static int[]
samplePool
(int n, int k, int[] result) Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n).static int[]
samplePool
(int n, int k, int[] result, RandomGenerator gen) Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n).static int[]
sampleReservoir
(int n, int k, int[] result) Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n).static int[]
sampleReservoir
(int n, int k, int[] result, RandomGenerator gen) Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n).

Method Details

sampleReservoir
public static int[] sampleReservoir(int n, int k, int[] result) Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n). All n choose k combinations are equally likely.Uses the reservoir sampling algorithm (Algorithm R) from J. Vitter's 1985 article "Random Sampling with a Reservoir" from ACM Transactions on Mathematical Software. The runtime is O(n) and it generates O(nk) random numbers. Thus, it is an especially good choice as k approaches n. Only constant extra space required.
This method uses ThreadLocalRandom as the pseudorandom number generator, and is thus safe, and efficient (i.e., nonblocking), for use with threads.
 Parameters:
n
 The number of integers to choose from.k
 The size of the desired sample.result
 An array to hold the sample that is generated. If result is null or if result.length is less than k, then this method will construct an array for the result. Returns:
 An array containing the sample of k randomly chosen integers from the interval [0, n).
 Throws:
IllegalArgumentException
 if k > n.NegativeArraySizeException
 if k < 0.

sampleReservoir
Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n). All n choose k combinations are equally likely.Uses the reservoir sampling algorithm (Algorithm R) from J. Vitter's 1985 article "Random Sampling with a Reservoir" from ACM Transactions on Mathematical Software. The runtime is O(n) and it generates O(nk) random numbers. Thus, it is an especially good choice as k approaches n. Only constant extra space required.
 Parameters:
n
 The number of integers to choose from.k
 The size of the desired sample.result
 An array to hold the sample that is generated. If result is null or if result.length is less than k, then this method will construct an array for the result.gen
 Source of randomness. Returns:
 An array containing the sample of k randomly chosen integers from the interval [0, n).
 Throws:
IllegalArgumentException
 if k > n.NegativeArraySizeException
 if k < 0.

samplePool
public static int[] samplePool(int n, int k, int[] result) Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n). All n choose k combinations are equally likely.This implements the algorithm SELECT of S. Goodman and S. Hedetniemi, as described in: J Ernvall, O Nevalainen, "An Algorithm for Unbiased Random Sampling," The Computer Journal, 25(1):4547, 1982.
The runtime is O(n) and it generates O(k) random numbers. Thus, it is a better choice than sampleReservoir when k < nk. However, this uses O(n) extra space, whereas the reservoir algorithm uses no extra space.
This method uses ThreadLocalRandom as the pseudorandom number generator, and is thus safe, and efficient (i.e., nonblocking), for use with threads.
 Parameters:
n
 The number of integers to choose from.k
 The size of the desired sample.result
 An array to hold the sample that is generated. If result is null or if result.length is less than k, then this method will construct an array for the result. Returns:
 An array containing the sample of k randomly chosen integers from the interval [0, n).
 Throws:
IllegalArgumentException
 if k > n.NegativeArraySizeException
 if k < 0.

samplePool
Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n). All n choose k combinations are equally likely.This implements the algorithm SELECT of S. Goodman and S. Hedetniemi, as described in: J Ernvall, O Nevalainen, "An Algorithm for Unbiased Random Sampling," The Computer Journal, 25(1):4547, 1982.
The runtime is O(n) and it generates O(k) random numbers. Thus, it is a better choice than sampleReservoir when k < nk. However, this uses O(n) extra space, whereas the reservoir algorithm uses no extra space.
 Parameters:
n
 The number of integers to choose from.k
 The size of the desired sample.result
 An array to hold the sample that is generated. If result is null or if result.length is less than k, then this method will construct an array for the result.gen
 Source of randomness. Returns:
 An array containing the sample of k randomly chosen integers from the interval [0, n).
 Throws:
IllegalArgumentException
 if k > n.NegativeArraySizeException
 if k < 0.

sampleInsertion
public static int[] sampleInsertion(int n, int k, int[] result) Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n). All n choose k combinations are equally likely.This implements the insertion sampling algorithm described in:
Vincent A. Cicirello. 2022. Cycle Mutation: Evolving Permutations via Cycle Induction, Applied Sciences, 12(11), Article 5506 (June 2022). doi:10.3390/app12115506
The runtime is O(k^{2}) and it generates O(k) random numbers. Thus, it is a better choice than both sampleReservoir and samplePool when k^{2} < n. Just like sampleReservoir, the sampleInsertion method only requires O(1) extra space, while samplePool requires O(n) extra space.
This method uses ThreadLocalRandom as the pseudorandom number generator, and is thus safe, and efficient (i.e., nonblocking), for use with threads.
 Parameters:
n
 The number of integers to choose from.k
 The size of the desired sample.result
 An array to hold the sample that is generated. If result is null or if result.length is less than k, then this method will construct an array for the result. Returns:
 An array containing the sample of k randomly chosen integers from the interval [0, n).
 Throws:
IllegalArgumentException
 if k > n.NegativeArraySizeException
 if k < 0.

sampleInsertion
Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n). All n choose k combinations are equally likely.This implements the insertion sampling algorithm described in:
Vincent A. Cicirello. 2022. Cycle Mutation: Evolving Permutations via Cycle Induction, Applied Sciences, 12(11), Article 5506 (June 2022). doi:10.3390/app12115506
The runtime is O(k^{2}) and it generates O(k) random numbers. Thus, it is a better choice than both sampleReservoir and samplePool when k^{2} < n. Just like sampleReservoir, the sampleInsertion method only requires O(1) extra space, while samplePool requires O(n) extra space.
 Parameters:
n
 The number of integers to choose from.k
 The size of the desired sample.result
 An array to hold the sample that is generated. If result is null or if result.length is less than k, then this method will construct an array for the result.gen
 The source of randomness. Returns:
 An array containing the sample of k randomly chosen integers from the interval [0, n).
 Throws:
IllegalArgumentException
 if k > n.NegativeArraySizeException
 if k < 0.

sample
public static int[] sample(int n, double p) Generates a random sample, without replacement, from the set of integers in the interval [0, n). Each of the n integers has a probability p of inclusion in the sample.This method uses ThreadLocalRandom as the source of randomness, and is thus safe, and efficient (i.e., nonblocking), for use with threads.
 Parameters:
n
 The number of integers to choose from.p
 The probability that each of the n integers is included in the sample. Returns:
 An array containing the sample.

sample
Generates a random sample, without replacement, from the set of integers in the interval [0, n). Each of the n integers has a probability p of inclusion in the sample. Parameters:
n
 The number of integers to choose from.p
 The probability that each of the n integers is included in the sample.r
 The source of randomness. Returns:
 An array containing the sample.

sample
public static int[] sample(int n, int k, int[] result) Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n). All n choose k combinations are equally likely.This method chooses among the RandomSampler.samplePool, RandomSampler.sampleReservoir, and RandomSampler.sampleInsertion methods based on the values of n and k.
This approach combining reservoir sampling, pool sampling, and insertion sampling was described in: Vincent A. Cicirello. 2022. Cycle Mutation: Evolving Permutations via Cycle Induction, Applied Sciences, 12(11), Article 5506 (June 2022). doi:10.3390/app12115506
The runtime is O(min(n, k^{2})) and it generates O(min(k, nk)) random numbers.
This method uses ThreadLocalRandom as the pseudorandom number generator, and is thus safe, and efficient (i.e., nonblocking), for use with threads.
 Parameters:
n
 The number of integers to choose from.k
 The size of the desired sample.result
 An array to hold the sample that is generated. If result is null or if result.length is less than k, then this method will construct an array for the result. Returns:
 An array containing the sample of k randomly chosen integers from the interval [0, n).
 Throws:
IllegalArgumentException
 if k > n.NegativeArraySizeException
 if k < 0.

sample
Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n). All n choose k combinations are equally likely.This method chooses among the RandomSampler.samplePool, RandomSampler.sampleReservoir, and RandomSampler.sampleInsertion methods based on the values of n and k.
This approach combining reservoir sampling, pool sampling, and insertion sampling was described in: Vincent A. Cicirello. 2022. Cycle Mutation: Evolving Permutations via Cycle Induction, Applied Sciences, 12(11), Article 5506 (June 2022). doi:10.3390/app12115506
The runtime is O(min(n, k^{2})) and it generates O(min(k, nk)) random numbers.
 Parameters:
n
 The number of integers to choose from.k
 The size of the desired sample.result
 An array to hold the sample that is generated. If result is null or if result.length is less than k, then this method will construct an array for the result.gen
 Source of randomness. Returns:
 An array containing the sample of k randomly chosen integers from the interval [0, n).
 Throws:
IllegalArgumentException
 if k > n.NegativeArraySizeException
 if k < 0.
