Package edu.rit.util

Class RandomSubset

java.lang.Object
edu.rit.util.RandomSubset
All Implemented Interfaces:
Iterator<Integer>
public class RandomSubset extends Object implements 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.
Version:
22-Nov-2011
Author:
Alan Kaminsky

  • Constructor Summary

    Constructors
    Constructor
    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.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    hasNext()
    Determine whether there are more integers in the random subset.
    Integer
    next()
    Returns the next integer in the random subset.
    void
    remove()
    Unsupported operation.
    RandomSubset
    remove(int i)
    Remove the given integer from the original set.
    void
    restart()
    Restart this random subset's iteration.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface java.util.Iterator

    forEachRemaining

  • Constructor Details

    • 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 Details

    • 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 void remove()
      Unsupported operation.
      Specified by:
      remove in interface Iterator<Integer>
      Throws:
      UnsupportedOperationException - (unchecked exception) Thrown always.

    • 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.