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.

Constructor Summary

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

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

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