RandomSubset
edu.rit.util

Class RandomSubset

  • All Implemented Interfaces:
    Iterator<Integer>


    public class RandomSubsetextends Objectimplements Iterator<Integer>
    Class RandomSubset provides an object that generates a random subset of a set of integers. The original set consists of the integers from 0 to N−1 inclusive. The subset consists of integers chosen at random without replacement from the original set; each member of the original set is equally likely to be chosen. Class RandomSubset is an Iterator that visits the elements of the original set in a random order; each next() method call returns another element of the subset.

    Calling the remove(i) method one or more times removes the given integers from the original set. Those integers will not be chosen for the random subset.

    Class RandomSubset is layered on top of a pseudorandom number generator (PRNG), an instance of class Random. Each time the next() method is called, one random number is consumed from the underlying PRNG.

    Class RandomSubset has two different implementations with different storage requirements. The implementation is specified with a constructor argument.

    • The sparse implementation requires less storage when the size of the random subset (the number of next() method calls) is a small fraction of the size of the original set (N).

    • The dense implementation requires less storage when the size of the random subset is a large fraction of the size of the original set.
    • Constructor Summary

      Constructors 
      Constructor and Description
      RandomSubset(Random prng, int N)
      Construct a new random subset object for the original set consisting of the integers from 0 through N−1 inclusive.
      RandomSubset(Random prng, int N, boolean dense)
      Construct a new random subset object for the original set consisting of the integers from 0 through N−1 inclusive.
    • Constructor Detail

      • RandomSubset

        public RandomSubset(Random prng,            int N)
        Construct a new random subset object for the original set consisting of the integers from 0 through N−1 inclusive. The sparse implementation is used.
        Parameters:
        prng - Underlying PRNG.
        N - Size of original set.
        Throws:
        NullPointerException - (unchecked exception) Thrown if prng is null.
        IllegalArgumentException - (unchecked exception) Thrown if N < 0.
      • RandomSubset

        public RandomSubset(Random prng,            int N,            boolean dense)
        Construct a new random subset object for the original set consisting of the integers from 0 through N−1 inclusive. If dense is false, the sparse implementation is used. If dense is true, the dense implementation is used.
        Parameters:
        prng - Underlying PRNG.
        N - Size of original set.
        dense - False to use the sparse implementation, true to use the dense implementation.
        Throws:
        NullPointerException - (unchecked exception) Thrown if prng is null.
        IllegalArgumentException - (unchecked exception) Thrown if N < 0.
    • Method Detail

      • hasNext

        public boolean hasNext()
        Determine whether there are more integers in the random subset.
        Specified by:
        hasNext in interface Iterator<Integer>
        Returns:
        True if there are more integers in the random subset, false if all the integers in the original set have been used up.
      • next

        public Integer next()
        Returns the next integer in the random subset.
        Specified by:
        next in interface Iterator<Integer>
        Returns:
        Next integer in the random subset.
        Throws:
        NoSuchElementException - (unchecked exception) Thrown if all the integers in the original set have been used up.
      • remove

        public RandomSubset remove(int i)
        Remove the given integer from the original set.

        If i has already been removed from the original set, either by a remove(i) method call, or by a next() method call that returned i, then this method does nothing.

        Parameters:
        i - Integer to remove.
        Returns:
        This random subset object.
        Throws:
        IllegalArgumentException - (unchecked exception) Thrown if i is not in the range 0 through N−1 inclusive.
      • restart

        public void restart()
        Restart this random subset's iteration. The original set is reset to contain all the integers from 0 through N−1 inclusive. If integers had been removed from the original set by calling the remove(i) method, those integers must be removed again by calling the remove(i) method again. The iteration is restarted, and calling the next() method will yield a different random subset.

        The restart() method lets you generate multiple random subsets from the same original set using the same RandomSubset object. This avoids the multiple storage allocations that would take place when creating multiple RandomSubset objects. This in turn can reduce the running time, especially when N is large.

SCaVis 2.1 © jWork.ORG