Class RandomIndexer


  • public final class RandomIndexer
    extends Object
    RandomIndexer is a class of utility methods related to efficiently generating random indexes, and combination of indexes, into arrays. The methods of this class neither directly operate, nor depend, on arrays, and can thus be used wherever you need random integer values. The name of the class is derived from the motivating case, the case of efficiently generating random indexes into an array.
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static boolean[] arrayMask​(int n)
      Generates an "array mask" of a specified length, where an "array mask" is an array of boolean values of the same length as another array.
      static boolean[] arrayMask​(int n, double p)
      Generates an "array mask" of a specified length, where an "array mask" is an array of boolean values of the same length as another array.
      static boolean[] arrayMask​(int n, double p, Random gen)
      Generates an "array mask" of a specified length, where an "array mask" is an array of boolean values of the same length as another array.
      static boolean[] arrayMask​(int n, double p, SplittableRandom gen)
      Generates an "array mask" of a specified length, where an "array mask" is an array of boolean values of the same length as another array.
      static boolean[] arrayMask​(int n, int k)
      Generates an "array mask" of a specified length and specified number of true values, where an "array mask" is an array of boolean values of the same length as another array.
      static boolean[] arrayMask​(int n, int k, Random gen)
      Generates an "array mask" of a specified length and specified number of true values, where an "array mask" is an array of boolean values of the same length as another array.
      static boolean[] arrayMask​(int n, int k, SplittableRandom gen)
      Generates an "array mask" of a specified length and specified number of true values, where an "array mask" is an array of boolean values of the same length as another array.
      static boolean[] arrayMask​(int n, Random gen)
      Generates an "array mask" of a specified length, where an "array mask" is an array of boolean values of the same length as another array.
      static boolean[] arrayMask​(int n, SplittableRandom gen)
      Generates an "array mask" of a specified length, where an "array mask" is an array of boolean values of the same length as another array.
      static int nextBiasedInt​(int bound)
      Generates a random integer in the interval: [0, bound).
      static int nextBiasedInt​(int bound, Random gen)
      Generates a random integer in the interval: [0, bound).
      static int nextBiasedInt​(int bound, SplittableRandom gen)
      Generates a random integer in the interval: [0, bound).
      static int nextInt​(int bound)
      Generates a random integer uniformly distributed in the interval: [0, bound).
      static int nextInt​(int bound, Random gen)
      Generates a random integer uniformly distributed in the interval: [0, bound).
      static int nextInt​(int bound, SplittableRandom gen)
      Generates a random integer uniformly distributed in the interval: [0, bound).
      static int[] nextIntPair​(int n, int[] result)
      Generates a random sample of 2 integers, without replacement, from the set of integers in the interval [0, n).
      static int[] nextIntPair​(int n, int[] result, Random gen)
      Generates a random sample of 2 integers, without replacement, from the set of integers in the interval [0, n).
      static int[] nextIntPair​(int n, int[] result, SplittableRandom gen)
      Generates a random sample of 2 integers, without replacement, from the set of integers in the interval [0, n).
      static int[] nextIntTriple​(int n, int[] result)
      Generates a random sample of 3 integers, without replacement, from the set of integers in the interval [0, n).
      static int[] nextIntTriple​(int n, int[] result, boolean sort)
      Generates a random sample of 3 integers, without replacement, from the set of integers in the interval [0, n).
      static int[] nextIntTriple​(int n, int[] result, boolean sort, Random gen)
      Generates a random sample of 3 integers, without replacement, from the set of integers in the interval [0, n).
      static int[] nextIntTriple​(int n, int[] result, boolean sort, SplittableRandom gen)
      Generates a random sample of 3 integers, without replacement, from the set of integers in the interval [0, n).
      static int[] nextIntTriple​(int n, int[] result, Random gen)
      Generates a random sample of 3 integers, without replacement, from the set of integers in the interval [0, n).
      static int[] nextIntTriple​(int n, int[] result, SplittableRandom gen)
      Generates a random sample of 3 integers, without replacement, from the set of integers in the interval [0, n).
      static int[] nextWindowedIntPair​(int n, int window, int[] result)
      Generates a random sample of 2 integers, i, j, without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window.
      static int[] nextWindowedIntPair​(int n, int window, int[] result, Random gen)
      Generates a random sample of 2 integers, i, j, without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window.
      static int[] nextWindowedIntPair​(int n, int window, int[] result, SplittableRandom gen)
      Generates a random sample of 2 integers, i, j, without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window.
      static int[] nextWindowedIntTriple​(int n, int window, int[] result)
      Generates a random sample of 3 integers, i, j, k without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window.
      static int[] nextWindowedIntTriple​(int n, int window, int[] result, boolean sort)
      Generates a random sample of 3 integers, i, j, k without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window.
      static int[] nextWindowedIntTriple​(int n, int window, int[] result, boolean sort, Random gen)
      Generates a random sample of 3 integers, i, j, k without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window.
      static int[] nextWindowedIntTriple​(int n, int window, int[] result, boolean sort, SplittableRandom gen)
      Generates a random sample of 3 integers, i, j, k without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window.
      static int[] nextWindowedIntTriple​(int n, int window, int[] result, Random gen)
      Generates a random sample of 3 integers, i, j, k without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window.
      static int[] nextWindowedIntTriple​(int n, int window, int[] result, SplittableRandom gen)
      Generates a random sample of 3 integers, i, j, k without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window.
      static 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, Random r)
      Generates a random sample, without replacement, from the set of integers in the interval [0, n).
      static int[] sample​(int n, double p, SplittableRandom 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, Random gen)
      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, SplittableRandom 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, Random 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, SplittableRandom 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, Random 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, SplittableRandom 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, Random 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, SplittableRandom gen)
      Generates a random sample of k integers, without replacement, from the set of integers in the interval [0, n).
    • Method Detail

      • nextInt

        public static int nextInt​(int bound)

        Generates a random integer uniformly distributed in the interval: [0, bound).

        This method uses ThreadLocalRandom as the pseudorandom number generator, and is thus safe, and efficient (i.e., non-blocking), for use with threads. However, it does not use ThreadLocalRandom.nextInt(int bound) method. Instead, our nextInt(int bound) method is an implementation of the algorithm proposed in the article: Daniel Lemire, "Fast Random Integer Generation in an Interval," ACM Transactions on Modeling and Computer Simulation, 29(1), 2019.

        This method is significantly faster than ThreadLocalRandom.nextInt(int bound).

        Parameters:
        bound - Upper bound, exclusive, on range of random integers (must be positive).
        Returns:
        a random integer between 0 (inclusive) and bound (exclusive).
        Throws:
        IllegalArgumentException - if the bound is not positive
      • nextInt

        public static int nextInt​(int bound,
                                  SplittableRandom gen)

        Generates a random integer uniformly distributed in the interval: [0, bound).

        This method uses a SplittableRandom object passed as a parameter as the pseudorandom number generator. However, it does not use SplittableRandom.nextInt(int bound) method. Instead, our nextInt(int bound) method is an implementation of the algorithm proposed in the article: Daniel Lemire, "Fast Random Integer Generation in an Interval," ACM Transactions on Modeling and Computer Simulation, 29(1), 2019.

        This method is significantly faster than SplittableRandom.nextInt(int bound).

        Parameters:
        bound - Upper bound, exclusive, on range of random integers (must be positive).
        gen - A source of randomness.
        Returns:
        a random integer between 0 (inclusive) and bound (exclusive).
        Throws:
        IllegalArgumentException - if the bound is not positive
      • nextInt

        public static int nextInt​(int bound,
                                  Random gen)

        Generates a random integer uniformly distributed in the interval: [0, bound).

        This method uses a Random object passed as a parameter as the pseudorandom number generator. However, it does not use Random.nextInt(int bound) method. Instead, our nextInt(int bound) method is an implementation of the algorithm proposed in the article: Daniel Lemire, "Fast Random Integer Generation in an Interval," ACM Transactions on Modeling and Computer Simulation, 29(1), 2019.

        This method is significantly faster than Random.nextInt(int bound).

        Parameters:
        bound - Upper bound, exclusive, on range of random integers (must be positive).
        gen - A source of randomness.
        Returns:
        a random integer between 0 (inclusive) and bound (exclusive).
        Throws:
        IllegalArgumentException - if the bound is not positive
      • nextBiasedInt

        public static int nextBiasedInt​(int bound)

        Generates a random integer in the interval: [0, bound).

        This method uses ThreadLocalRandom as the pseudorandom number generator, and is thus safe, and efficient (i.e., non-blocking), for use with threads. However, it does not use ThreadLocalRandom.nextInt(int bound) method. Instead, our nextBiasedInt(int bound) method computes a random int in the target interval via a multiplication and a shift, rather than the more common mod. This method does not correct for bias via rejection sampling, and thus some values in the interval [0, bound) may be more likely than others. There is no bias for bound values that are powers of 2. Otherwise, the lower the value of bound, the less bias; and the higher the value of bound, the more bias. If your bound is relatively low, and if your application does not require strict uniformity, then this method is significantly faster than any approach that corrects for bias. We started with the algorithm proposed in the article: Daniel Lemire, "Fast Random Integer Generation in an Interval," ACM Transactions on Modeling and Computer Simulation, 29(1), 2019. But we removed from it the rejection sampling portion.

        Parameters:
        bound - Upper bound, exclusive, on range of random integers (must be positive).
        Returns:
        a random integer between 0 (inclusive) and bound (exclusive).
        Throws:
        IllegalArgumentException - if the bound is not positive
      • nextBiasedInt

        public static int nextBiasedInt​(int bound,
                                        SplittableRandom gen)

        Generates a random integer in the interval: [0, bound).

        This method uses SplittableRandom as the pseudorandom number generator, and is thus safe for use with threads. However, it does not use SplittableRandom.nextInt(int bound) method. Instead, our nextBiasedInt(int bound) method computes a random int in the target interval via a multiplication and a shift, rather than the more common mod. This method does not correct for bias via rejection sampling, and thus some values in the interval [0, bound) may be more likely than others. There is no bias for bound values that are powers of 2. Otherwise, the lower the value of bound, the less bias; and the higher the value of bound, the more bias. If your bound is relatively low, and if your application does not require strict uniformity, then this method is significantly faster than any approach that corrects for bias. We started with the algorithm proposed in the article: Daniel Lemire, "Fast Random Integer Generation in an Interval," ACM Transactions on Modeling and Computer Simulation, 29(1), 2019. But we removed from it the rejection sampling portion.

        Parameters:
        bound - Upper bound, exclusive, on range of random integers (must be positive).
        gen - A source of randomness.
        Returns:
        a random integer between 0 (inclusive) and bound (exclusive).
        Throws:
        IllegalArgumentException - if the bound is not positive
      • nextBiasedInt

        public static int nextBiasedInt​(int bound,
                                        Random gen)

        Generates a random integer in the interval: [0, bound).

        This method uses Random as the pseudorandom number generator, and is thus safe for use with threads. However, it does not use Random.nextInt(int bound) method. Instead, our nextBiasedInt(int bound) method computes a random int in the target interval via a multiplication and a shift, rather than the more common mod. This method does not correct for bias via rejection sampling, and thus some values in the interval [0, bound) may be more likely than others. There is no bias for bound values that are powers of 2. Otherwise, the lower the value of bound, the less bias; and the higher the value of bound, the more bias. If your bound is relatively low, and if your application does not require strict uniformity, then this method is significantly faster than any approach that corrects for bias. We started with the algorithm proposed in the article: Daniel Lemire, "Fast Random Integer Generation in an Interval," ACM Transactions on Modeling and Computer Simulation, 29(1), 2019. But we removed from it the rejection sampling portion.

        Parameters:
        bound - Upper bound, exclusive, on range of random integers (must be positive).
        gen - A source of randomness.
        Returns:
        a random integer between 0 (inclusive) and bound (exclusive).
        Throws:
        IllegalArgumentException - if the bound is not positive
      • 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(n-k) 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., non-blocking), 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

        public static int[] sampleReservoir​(int n,
                                            int k,
                                            int[] result,
                                            Random gen)

        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(n-k) 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.
      • sampleReservoir

        public static int[] sampleReservoir​(int n,
                                            int k,
                                            int[] result,
                                            SplittableRandom gen)

        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(n-k) 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):45-47, 1982.

        The runtime is O(n) and it generates O(k) random numbers. Thus, it is a better choice than sampleReservoir when k < n-k. 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., non-blocking), 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

        public static int[] samplePool​(int n,
                                       int k,
                                       int[] result,
                                       SplittableRandom gen)

        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):45-47, 1982.

        The runtime is O(n) and it generates O(k) random numbers. Thus, it is a better choice than sampleReservoir when k < n-k. 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.
      • samplePool

        public static int[] samplePool​(int n,
                                       int k,
                                       int[] result,
                                       Random gen)

        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):45-47, 1982.

        The runtime is O(n) and it generates O(k) random numbers. Thus, it is a better choice than sampleReservoir when k < n-k. 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.

        The runtime is O(k2) and it generates O(k) random numbers. Thus, it is a better choice than both sampleReservoir and samplePool when k2 < 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., non-blocking), 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

        public static int[] sampleInsertion​(int n,
                                            int k,
                                            int[] result,
                                            SplittableRandom gen)

        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.

        The runtime is O(k2) and it generates O(k) random numbers. Thus, it is a better choice than both sampleReservoir and samplePool when k2 < 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.
      • sampleInsertion

        public static int[] sampleInsertion​(int n,
                                            int k,
                                            int[] result,
                                            Random gen)

        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.

        The runtime is O(k2) and it generates O(k) random numbers. Thus, it is a better choice than both sampleReservoir and samplePool when k2 < 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., non-blocking), 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

        public static int[] sample​(int n,
                                   double p,
                                   SplittableRandom r)

        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., non-blocking), 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.
        r - The source of randomness.
        Returns:
        An array containing the sample.
      • sample

        public static int[] sample​(int n,
                                   double p,
                                   Random r)

        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., non-blocking), 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.
        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 RandomIndexer.samplePool, RandomIndexer.sampleReservoir, and RandomIndexer.sampleInsertion methods based on the values of n and k.

        The runtime is O(min(n, k2)) and it generates O(min(k, n-k)) random numbers.

        This method uses ThreadLocalRandom as the pseudorandom number generator, and is thus safe, and efficient (i.e., non-blocking), 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

        public static int[] sample​(int n,
                                   int k,
                                   int[] result,
                                   SplittableRandom gen)

        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 RandomIndexer.samplePool, RandomIndexer.sampleReservoir, and RandomIndexer.sampleInsertion methods based on the values of n and k.

        The runtime is O(min(n, k2)) and it generates O(min(k, n-k)) 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.
      • sample

        public static int[] sample​(int n,
                                   int k,
                                   int[] result,
                                   Random gen)

        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 RandomIndexer.samplePool, RandomIndexer.sampleReservoir, and RandomIndexer.sampleInsertion methods based on the values of n and k.

        The runtime is O(min(n, k2)) and it generates O(min(k, n-k)) 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.
      • nextIntPair

        public static int[] nextIntPair​(int n,
                                        int[] result)

        Generates a random sample of 2 integers, without replacement, from the set of integers in the interval [0, n). All n choose 2 combinations are equally likely.

        The runtime is O(1).

        This method uses ThreadLocalRandom as the pseudorandom number generator, and is thus safe, and efficient (i.e., non-blocking), for use with threads.

        Parameters:
        n - The number of integers to choose from.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 2, then this method will construct an array for the result.
        Returns:
        An array containing the pair of randomly chosen integers from the interval [0, n).
        Throws:
        IllegalArgumentException - if n < 2.
      • nextIntPair

        public static int[] nextIntPair​(int n,
                                        int[] result,
                                        SplittableRandom gen)

        Generates a random sample of 2 integers, without replacement, from the set of integers in the interval [0, n). All n choose 2 combinations are equally likely.

        The runtime is O(1).

        Parameters:
        n - The number of integers to choose from.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 2, then this method will construct an array for the result.
        gen - Source of randomness.
        Returns:
        An array containing the pair of randomly chosen integers from the interval [0, n).
        Throws:
        IllegalArgumentException - if n < 2.
      • nextIntPair

        public static int[] nextIntPair​(int n,
                                        int[] result,
                                        Random gen)

        Generates a random sample of 2 integers, without replacement, from the set of integers in the interval [0, n). All n choose 2 combinations are equally likely.

        The runtime is O(1).

        Parameters:
        n - The number of integers to choose from.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 2, then this method will construct an array for the result.
        gen - Source of randomness.
        Returns:
        An array containing the pair of randomly chosen integers from the interval [0, n).
        Throws:
        IllegalArgumentException - if n < 2.
      • nextIntTriple

        public static int[] nextIntTriple​(int n,
                                          int[] result)

        Generates a random sample of 3 integers, without replacement, from the set of integers in the interval [0, n). All n choose 3 combinations are equally likely.

        The runtime is O(1).

        This method uses ThreadLocalRandom as the pseudorandom number generator, and is thus safe, and efficient (i.e., non-blocking), for use with threads.

        Parameters:
        n - The number of integers to choose from.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 3, then this method will construct an array for the result.
        Returns:
        An array containing the pair of randomly chosen integers from the interval [0, n).
        Throws:
        IllegalArgumentException - if n < 3.
      • nextIntTriple

        public static int[] nextIntTriple​(int n,
                                          int[] result,
                                          boolean sort)

        Generates a random sample of 3 integers, without replacement, from the set of integers in the interval [0, n). All n choose 3 combinations are equally likely.

        The runtime is O(1).

        This method uses ThreadLocalRandom as the pseudorandom number generator, and is thus safe, and efficient (i.e., non-blocking), for use with threads.

        Parameters:
        n - The number of integers to choose from.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 3, then this method will construct an array for the result.
        sort - If true, the result is sorted in increasing order; otherwise it is in arbitrary order.
        Returns:
        An array containing the pair of randomly chosen integers from the interval [0, n).
        Throws:
        IllegalArgumentException - if n < 3.
      • nextIntTriple

        public static int[] nextIntTriple​(int n,
                                          int[] result,
                                          boolean sort,
                                          SplittableRandom gen)

        Generates a random sample of 3 integers, without replacement, from the set of integers in the interval [0, n). All n choose 3 combinations are equally likely.

        The runtime is O(1).

        Parameters:
        n - The number of integers to choose from.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 3, then this method will construct an array for the result.
        sort - If true, the result is sorted in increasing order; otherwise it is in arbitrary order.
        gen - The source of randomness.
        Returns:
        An array containing the pair of randomly chosen integers from the interval [0, n).
        Throws:
        IllegalArgumentException - if n < 3.
      • nextIntTriple

        public static int[] nextIntTriple​(int n,
                                          int[] result,
                                          boolean sort,
                                          Random gen)

        Generates a random sample of 3 integers, without replacement, from the set of integers in the interval [0, n). All n choose 3 combinations are equally likely.

        The runtime is O(1).

        Parameters:
        n - The number of integers to choose from.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 3, then this method will construct an array for the result.
        sort - If true, the result is sorted in increasing order; otherwise it is in arbitrary order.
        gen - The source of randomness.
        Returns:
        An array containing the pair of randomly chosen integers from the interval [0, n).
        Throws:
        IllegalArgumentException - if n < 3.
      • nextIntTriple

        public static int[] nextIntTriple​(int n,
                                          int[] result,
                                          SplittableRandom gen)

        Generates a random sample of 3 integers, without replacement, from the set of integers in the interval [0, n). All n choose 3 combinations are equally likely.

        The runtime is O(1).

        Parameters:
        n - The number of integers to choose from.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 3, then this method will construct an array for the result.
        gen - Source of randomness.
        Returns:
        An array containing the pair of randomly chosen integers from the interval [0, n).
        Throws:
        IllegalArgumentException - if n < 3.
      • nextIntTriple

        public static int[] nextIntTriple​(int n,
                                          int[] result,
                                          Random gen)

        Generates a random sample of 3 integers, without replacement, from the set of integers in the interval [0, n). All n choose 3 combinations are equally likely.

        The runtime is O(1).

        Parameters:
        n - The number of integers to choose from.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 3, then this method will construct an array for the result.
        gen - Source of randomness.
        Returns:
        An array containing the pair of randomly chosen integers from the interval [0, n).
        Throws:
        IllegalArgumentException - if n < 3.
      • arrayMask

        public static boolean[] arrayMask​(int n)

        Generates an "array mask" of a specified length, where an "array mask" is an array of boolean values of the same length as another array. Each position in the result is equally likely true or false.

        Runtime: O(n).

        This method uses ThreadLocalRandom as the source of randomness, and is thus safe, and efficient (i.e., non-blocking), for use with threads.

        Parameters:
        n - The length of the array mask.
        Returns:
        An array of n randomly generated boolean values.
      • arrayMask

        public static boolean[] arrayMask​(int n,
                                          SplittableRandom gen)

        Generates an "array mask" of a specified length, where an "array mask" is an array of boolean values of the same length as another array. Each position in the result is equally likely true or false.

        Runtime: O(n).

        Parameters:
        n - The length of the array mask.
        gen - The source of randomness.
        Returns:
        An array of n randomly generated boolean values.
      • arrayMask

        public static boolean[] arrayMask​(int n,
                                          Random gen)

        Generates an "array mask" of a specified length, where an "array mask" is an array of boolean values of the same length as another array. Each position in the result is equally likely true or false.

        Runtime: O(n).

        Parameters:
        n - The length of the array mask.
        gen - The source of randomness.
        Returns:
        An array of n randomly generated boolean values.
      • arrayMask

        public static boolean[] arrayMask​(int n,
                                          int k)

        Generates an "array mask" of a specified length and specified number of true values, where an "array mask" is an array of boolean values of the same length as another array.

        Runtime: O(min(n, k2)), and it uses O(min(k, n-k)) random numbers.

        This method uses ThreadLocalRandom as the pseudorandom number generator, and is thus safe, and efficient (i.e., non-blocking), for use with threads.

        Parameters:
        n - The length of the array mask.
        k - The desired number of true values, which must be no greater than n.
        Returns:
        An array of n boolean values, exactly k of which are equal to true.
      • arrayMask

        public static boolean[] arrayMask​(int n,
                                          int k,
                                          SplittableRandom gen)

        Generates an "array mask" of a specified length and specified number of true values, where an "array mask" is an array of boolean values of the same length as another array.

        Runtime: O(min(n, k2)), and it uses O(min(k, n-k)) random numbers.

        Parameters:
        n - The length of the array mask.
        k - The desired number of true values, which must be no greater than n.
        gen - The source of randomness.
        Returns:
        An array of n boolean values, exactly k of which are equal to true.
      • arrayMask

        public static boolean[] arrayMask​(int n,
                                          int k,
                                          Random gen)

        Generates an "array mask" of a specified length and specified number of true values, where an "array mask" is an array of boolean values of the same length as another array.

        Runtime: O(min(n, k2)), and it uses O(min(k, n-k)) random numbers.

        Parameters:
        n - The length of the array mask.
        k - The desired number of true values, which must be no greater than n.
        gen - The source of randomness.
        Returns:
        An array of n boolean values, exactly k of which are equal to true.
      • arrayMask

        public static boolean[] arrayMask​(int n,
                                          double p)

        Generates an "array mask" of a specified length, where an "array mask" is an array of boolean values of the same length as another array.

        Runtime: O(n), and it uses O(n) random doubles.

        This method uses ThreadLocalRandom as the pseudorandom number generator, and is thus safe, and efficient (i.e., non-blocking), for use with threads.

        Parameters:
        n - The length of the array mask.
        p - The probability that an element of the result is true.
        Returns:
        An array of n boolean values, such that each element is true with probability p.
      • arrayMask

        public static boolean[] arrayMask​(int n,
                                          double p,
                                          SplittableRandom gen)

        Generates an "array mask" of a specified length, where an "array mask" is an array of boolean values of the same length as another array.

        Runtime: O(n), and it uses O(n) random doubles.

        Parameters:
        n - The length of the array mask.
        p - The probability that an element of the result is true.
        gen - The source of randomness.
        Returns:
        An array of n boolean values, such that each element is true with probability p.
      • arrayMask

        public static boolean[] arrayMask​(int n,
                                          double p,
                                          Random gen)

        Generates an "array mask" of a specified length, where an "array mask" is an array of boolean values of the same length as another array.

        Runtime: O(n), and it uses O(n) random doubles.

        Parameters:
        n - The length of the array mask.
        p - The probability that an element of the result is true.
        gen - The source of randomness.
        Returns:
        An array of n boolean values, such that each element is true with probability p.
      • nextWindowedIntPair

        public static int[] nextWindowedIntPair​(int n,
                                                int window,
                                                int[] result)

        Generates a random sample of 2 integers, i, j, without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window. All pairs that satisfy the window constraint are equally likely.

        The runtime is O(1).

        This method uses ThreadLocalRandom as the pseudorandom number generator, and is thus safe, and efficient (i.e., non-blocking), for use with threads.

        Parameters:
        n - The number of integers to choose from.
        window - The maximum difference between the integers of the pair.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 2, then this method will construct an array for the result.
        Returns:
        An array containing the pair of randomly chosen integers, i, j, from the interval [0, n), such that |i-j| ≤ window.
        Throws:
        IllegalArgumentException - if window < 1 or n < 2.
      • nextWindowedIntPair

        public static int[] nextWindowedIntPair​(int n,
                                                int window,
                                                int[] result,
                                                SplittableRandom gen)

        Generates a random sample of 2 integers, i, j, without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window. All pairs that satisfy the window constraint are equally likely.

        The runtime is O(1).

        Parameters:
        n - The number of integers to choose from.
        window - The maximum difference between the integers of the pair.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 2, then this method will construct an array for the result.
        gen - Source of randomness.
        Returns:
        An array containing the pair of randomly chosen integers, i, j, from the interval [0, n), such that |i-j| ≤ window.
        Throws:
        IllegalArgumentException - if window < 1 or n < 2.
      • nextWindowedIntPair

        public static int[] nextWindowedIntPair​(int n,
                                                int window,
                                                int[] result,
                                                Random gen)

        Generates a random sample of 2 integers, i, j, without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window. All pairs that satisfy the window constraint are equally likely.

        The runtime is O(1).

        Parameters:
        n - The number of integers to choose from.
        window - The maximum difference between the integers of the pair.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 2, then this method will construct an array for the result.
        gen - Source of randomness.
        Returns:
        An array containing the pair of randomly chosen integers, i, j, from the interval [0, n), such that |i-j| ≤ window.
        Throws:
        IllegalArgumentException - if window < 1 or n < 2.
      • nextWindowedIntTriple

        public static int[] nextWindowedIntTriple​(int n,
                                                  int window,
                                                  int[] result)

        Generates a random sample of 3 integers, i, j, k without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window. All triples that satisfy the window constraint are equally likely.

        The runtime is O(1).

        This method uses ThreadLocalRandom as the pseudorandom number generator, and is thus safe, and efficient (i.e., non-blocking), for use with threads.

        Parameters:
        n - The number of integers to choose from.
        window - The maximum difference between the integers of the triple.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 3, then this method will construct an array for the result.
        Returns:
        An array containing the triple of randomly chosen integers, i, j, k from the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window.
        Throws:
        IllegalArgumentException - if window < 2 or n < 3.
      • nextWindowedIntTriple

        public static int[] nextWindowedIntTriple​(int n,
                                                  int window,
                                                  int[] result,
                                                  boolean sort)

        Generates a random sample of 3 integers, i, j, k without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window. All triples that satisfy the window constraint are equally likely.

        The runtime is O(1).

        This method uses ThreadLocalRandom as the pseudorandom number generator, and is thus safe, and efficient (i.e., non-blocking), for use with threads.

        Parameters:
        n - The number of integers to choose from.
        window - The maximum difference between the integers of the triple.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 3, then this method will construct an array for the result.
        sort - If true, the result is sorted in increasing order, otherwise it is in random order.
        Returns:
        An array containing the triple of randomly chosen integers, i, j, k from the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window.
        Throws:
        IllegalArgumentException - if window < 2 or n < 3.
      • nextWindowedIntTriple

        public static int[] nextWindowedIntTriple​(int n,
                                                  int window,
                                                  int[] result,
                                                  SplittableRandom gen)

        Generates a random sample of 3 integers, i, j, k without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window. All triples that satisfy the window constraint are equally likely.

        The runtime is O(1).

        Parameters:
        n - The number of integers to choose from.
        window - The maximum difference between the integers of the triple.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 3, then this method will construct an array for the result.
        gen - The source of randomness.
        Returns:
        An array containing the triple of randomly chosen integers, i, j, k from the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window.
        Throws:
        IllegalArgumentException - if window < 2 or n < 3.
      • nextWindowedIntTriple

        public static int[] nextWindowedIntTriple​(int n,
                                                  int window,
                                                  int[] result,
                                                  boolean sort,
                                                  SplittableRandom gen)

        Generates a random sample of 3 integers, i, j, k without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window. All triples that satisfy the window constraint are equally likely.

        The runtime is O(1).

        Parameters:
        n - The number of integers to choose from.
        window - The maximum difference between the integers of the triple.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 3, then this method will construct an array for the result.
        sort - If true, the result is sorted in increasing order, otherwise it is in random order.
        gen - The source of randomness.
        Returns:
        An array containing the triple of randomly chosen integers, i, j, k from the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window.
        Throws:
        IllegalArgumentException - if window < 2 or n < 3.
      • nextWindowedIntTriple

        public static int[] nextWindowedIntTriple​(int n,
                                                  int window,
                                                  int[] result,
                                                  Random gen)

        Generates a random sample of 3 integers, i, j, k without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window. All triples that satisfy the window constraint are equally likely.

        The runtime is O(1).

        Parameters:
        n - The number of integers to choose from.
        window - The maximum difference between the integers of the triple.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 3, then this method will construct an array for the result.
        gen - The source of randomness.
        Returns:
        An array containing the triple of randomly chosen integers, i, j, k from the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window.
        Throws:
        IllegalArgumentException - if window < 2 or n < 3.
      • nextWindowedIntTriple

        public static int[] nextWindowedIntTriple​(int n,
                                                  int window,
                                                  int[] result,
                                                  boolean sort,
                                                  Random gen)

        Generates a random sample of 3 integers, i, j, k without replacement, from the set of integers in the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window. All triples that satisfy the window constraint are equally likely.

        The runtime is O(1).

        Parameters:
        n - The number of integers to choose from.
        window - The maximum difference between the integers of the triple.
        result - An array to hold the pair that is generated. If result is null or if result.length is less than 3, then this method will construct an array for the result.
        sort - If true, the result is sorted in increasing order, otherwise it is in random order.
        gen - The source of randomness.
        Returns:
        An array containing the triple of randomly chosen integers, i, j, k from the interval [0, n), such that |i-j| ≤ window, and |i-k| ≤ window, and |k-j| ≤ window.
        Throws:
        IllegalArgumentException - if window < 2 or n < 3.