org.jamesframework.core.util

## Class SetUtilities

• public final class SetUtilities
extends Object
Contains some utility functions for manipulating sets.
Author:
Herman De Beukelaer
• ### Constructor Summary

Constructors
Constructor and Description
SetUtilities()
• ### Method Summary

All Methods
Modifier and Type Method and Description
static <T> T getRandomElement(Set<? extends T> set, Random rg)
Select a random element from a given set (uniformly distributed).
static <T> Set<T> getRandomSubset(Set<? extends T> set, int size, Random rg)
Selects a random subset of a specific size from a given set (uniformly distributed).
static <T> Collection<T> getRandomSubset(Set<? extends T> set, int size, Random rg, Collection<T> subset)
Selects a random subset of a specific size from a given set (uniformly distributed).
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Constructor Detail

• #### SetUtilities

public SetUtilities()
• ### Method Detail

• #### getRandomElement

public static <T> T getRandomElement(Set<? extends T> set,
Random rg)
Select a random element from a given set (uniformly distributed). This implementation generates a random number r in [0,|set|-1] and traverses the set using an iterator, where the element obtained after r+1 applications of Iterator.next() is returned. In the worst case, this algorithm has linear time complexity with respect to the size of the given set.
Type Parameters:
T - type of randomly selected element
Parameters:
set - set from which to select a random element
rg - random generator
Returns:
random element (uniformly distributed)
• #### getRandomSubset

public static <T> Collection<T> getRandomSubset(Set<? extends T> set,
int size,
Random rg,
Collection<T> subset)

Selects a random subset of a specific size from a given set (uniformly distributed). Applies a full scan algorithm that iterates once through the given set and selects each item with probability (#remaining to select)/(#remaining to scan). It can be proven that this algorithm creates uniformly distributed random subsets (for example, a proof is given here). In the worst case, this algorithm has linear time complexity with respect to the size of the given set.

The items from the selected subset are added to the given collection subset. This collection is not cleared so that already contained items will be retained. A reference to this same collection is returned after it has been modified. To store the generated subset in a newly allocated LinkedHashSet the alternative method getRandomSubset(Set, int, Random) may also be used.

Type Parameters:
T - type of elements in randomly selected subset
Parameters:
set - set from which a random subset is to be sampled
size - desired subset size, should be a number in [0,|set|]
rg - random generator
subset - collection to which the items from the selected subset are added
Returns:
reference to given collection subset after it has been filled with the items from the randomly generated subset
Throws:
IllegalArgumentException - if an invalid subset size outside [0,|set|] is specified
http://eyalsch.wordpress.com/2010/04/01/random-sample
• #### getRandomSubset

public static <T> Set<T> getRandomSubset(Set<? extends T> set,
int size,
Random rg)

Selects a random subset of a specific size from a given set (uniformly distributed). Applies a full scan algorithm that iterates once through the given set and selects each item with probability (#remaining to select)/(#remaining to scan). It can be proven that this algorithm creates uniformly distributed random subsets (for example, a proof is given here). In the worst case, this algorithm has linear time complexity with respect to the size of the given set.

The generated subset is stored in a newly allocated LinkedHashSet.

Type Parameters:
T - type of elements in randomly selected subset
Parameters:
set - set from which a random subset is to be selected
size - desired subset size, should be a number in [0,|set|]
rg - random generator
Returns:
random subset stored in a newly allocated LinkedHashSet.
Throws:
IllegalArgumentException - if an invalid subset size outside [0,|set|] is specified