View Javadoc
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 }