A combination is a selection of items from a collection, such that (unlike + * permutations) the order of selection does not matter. This + * sampler can be used to generate a combination in an unspecified order and is + * faster than the corresponding {@link PermutationSampler}. + * + *

Note that the sample order is unspecified. For example a sample + * combination of 2 from 4 may return {@code [0,1]} or {@code [1,0]} as the two are + * equivalent, and the order of a given combination may change in subsequent samples. + * + *

The sampler can be used to generate indices to select subsets where the + * order of the subset is not important. + * + * @see Combination + * definition + * @see PermutationSampler + */ +public class CombinationSampler { + /** Domain of the combination. */ + private final int[] domain; + /** Size of the combination. */ + private final int size; + /** The number of steps of a full shuffle to perform. */ + private final int steps; + /** + * The position to copy the domain from after a partial shuffle. + * + *

The copy is either in the range [0 : size] or [domain.length - size : + * domain.length]. + */ + private final int from; + /** RNG. */ + private final UniformRandomProvider rng; + + /** + * Creates a generator of combinations. + * + *

The {@link #sample()} method will generate an integer array of + * length {@code k} whose entries are selected randomly, without + * repetition, from the integers 0, 1, ..., {@code n}-1 (inclusive). + * The returned array represents a combination of {@code n} taken + * {@code k}. + * + *

In contrast to a permutation, the returned array is not + * guaranteed to be in a random order. The {@link #sample()} + * method returns the array in an unspecified order. + * + *

If {@code n <= 0} or {@code k <= 0} or {@code k > n} then no combination + * is required and an exception is raised. + * + * @param rng Generator of uniformly distributed random numbers. + * @param n Domain of the combination. + * @param k Size of the combination. + * @throws IllegalArgumentException if {@code n <= 0} or {@code k <= 0} or + * {@code k > n}. + */ + public CombinationSampler(UniformRandomProvider rng, int n, int k) { + if (n <= 0) { + throw new IllegalArgumentException("n <= 0 : n=" + n); + } + if (k <= 0) { + throw new IllegalArgumentException("k <= 0 : k=" + k); + } + if (k > n) { + throw new IllegalArgumentException("k > n : k=" + k + ", n=" + n); + } + + domain = PermutationSampler.natural(n); + size = k; + // The sample can be optimised by only performing the first k or (n - k) steps + // from a full Fisher-Yates shuffle from the end of the domain to the start. + // The upper positions will then contain a random sample from the domain. The + // lower half is then by definition also a random sample (just not in a random order). + // The sample is then picked using the upper or lower half depending which + // makes the number of steps smaller. + if (k <= n / 2) { + // Upper half + steps = k; + from = n - k; + } else { + // Lower half + steps = n - k; + from = 0; + } + this.rng = rng; + } + + /** + * Return a combination of {@code k} whose entries are selected randomly, + * without repetition, from the integers 0, 1, ..., {@code n}-1 (inclusive). + * + *