1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 package org.apache.commons.rng.sampling; 19 20 import org.apache.commons.rng.UniformRandomProvider; 21 22 /** 23 * Class for representing <a href="https://en.wikipedia.org/wiki/Combination">combinations</a> 24 * of a sequence of integers. 25 * 26 * <p>A combination is a selection of items from a collection, such that (unlike 27 * permutations) the order of selection <strong>does not matter</strong>. This 28 * sampler can be used to generate a combination in an unspecified order and is 29 * faster than the corresponding {@link PermutationSampler}. 30 * 31 * <p>Note that the sample order is unspecified. For example a sample 32 * combination of 2 from 4 may return {@code [0,1]} or {@code [1,0]} as the two are 33 * equivalent, and the order of a given combination may change in subsequent samples. 34 * 35 * <p>The sampler can be used to generate indices to select subsets where the 36 * order of the subset is not important. 37 * 38 * @see PermutationSampler 39 */ 40 public class CombinationSampler { 41 /** Domain of the combination. */ 42 private final int[] domain; 43 /** The number of steps of a full shuffle to perform. */ 44 private final int steps; 45 /** 46 * The section to copy the domain from after a partial shuffle. 47 */ 48 private final boolean upper; 49 /** RNG. */ 50 private final UniformRandomProvider rng; 51 52 /** 53 * Creates a generator of combinations. 54 * 55 * <p>The {@link #sample()} method will generate an integer array of 56 * length {@code k} whose entries are selected randomly, without 57 * repetition, from the integers 0, 1, ..., {@code n}-1 (inclusive). 58 * The returned array represents a combination of {@code n} taken 59 * {@code k}. 60 * 61 * <p>In contrast to a permutation, the returned array is <strong>not 62 * guaranteed</strong> to be in a random order. The {@link #sample()} 63 * method returns the array in an unspecified order. 64 * 65 * <p>If {@code n <= 0} or {@code k <= 0} or {@code k > n} then no combination 66 * is required and an exception is raised. 67 * 68 * @param rng Generator of uniformly distributed random numbers. 69 * @param n Domain of the combination. 70 * @param k Size of the combination. 71 * @throws IllegalArgumentException if {@code n <= 0} or {@code k <= 0} or 72 * {@code k > n}. 73 */ 74 public CombinationSampler(UniformRandomProvider rng, 75 int n, 76 int k) { 77 SubsetSamplerUtils.checkSubset(n, k); 78 domain = PermutationSampler.natural(n); 79 // The sample can be optimised by only performing the first k or (n - k) steps 80 // from a full Fisher-Yates shuffle from the end of the domain to the start. 81 // The upper positions will then contain a random sample from the domain. The 82 // lower half is then by definition also a random sample (just not in a random order). 83 // The sample is then picked using the upper or lower half depending which 84 // makes the number of steps smaller. 85 upper = k <= n / 2; 86 steps = upper ? k : n - k; 87 this.rng = rng; 88 } 89 90 /** 91 * Return a combination of {@code k} whose entries are selected randomly, 92 * without repetition, from the integers 0, 1, ..., {@code n}-1 (inclusive). 93 * 94 * <p>The order of the returned array is not guaranteed to be in a random order 95 * as the order of a combination <strong>does not matter</strong>. 96 * 97 * @return a random combination. 98 */ 99 public int[] sample() { 100 return SubsetSamplerUtils.partialSample(domain, steps, rng, upper); 101 } 102 }