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}.</p>
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.</p>
34 *
35 * <p>The sampler can be used to generate indices to select subsets where the
36 * order of the subset is not important.</p>
37 *
38 * <p>Sampling uses {@link UniformRandomProvider#nextInt(int)}.</p>
39 *
40 * @see PermutationSampler
41 */
42 public class CombinationSampler implements SharedStateObjectSampler<int[]> {
43 /** Domain of the combination. */
44 private final int[] domain;
45 /** The number of steps of a full shuffle to perform. */
46 private final int steps;
47 /**
48 * The section to copy the domain from after a partial shuffle.
49 */
50 private final boolean upper;
51 /** RNG. */
52 private final UniformRandomProvider rng;
53
54 /**
55 * Creates a generator of combinations.
56 *
57 * <p>The {@link #sample()} method will generate an integer array of
58 * length {@code k} whose entries are selected randomly, without
59 * repetition, from the integers 0, 1, ..., {@code n}-1 (inclusive).
60 * The returned array represents a combination of {@code n} taken
61 * {@code k}.
62 *
63 * <p>In contrast to a permutation, the returned array is <strong>not
64 * guaranteed</strong> to be in a random order. The {@link #sample()}
65 * method returns the array in an unspecified order.
66 *
67 * <p>If {@code n <= 0} or {@code k <= 0} or {@code k > n} then no combination
68 * is required and an exception is raised.
69 *
70 * @param rng Generator of uniformly distributed random numbers.
71 * @param n Domain of the combination.
72 * @param k Size of the combination.
73 * @throws IllegalArgumentException if {@code n <= 0} or {@code k <= 0} or
74 * {@code k > n}.
75 */
76 public CombinationSampler(UniformRandomProvider rng,
77 int n,
78 int k) {
79 SubsetSamplerUtils.checkSubset(n, k);
80 domain = PermutationSampler.natural(n);
81 // The sample can be optimised by only performing the first k or (n - k) steps
82 // from a full Fisher-Yates shuffle from the end of the domain to the start.
83 // The upper positions will then contain a random sample from the domain. The
84 // lower half is then by definition also a random sample (just not in a random order).
85 // The sample is then picked using the upper or lower half depending which
86 // makes the number of steps smaller.
87 upper = k <= n / 2;
88 steps = upper ? k : n - k;
89 this.rng = rng;
90 }
91
92 /**
93 * @param rng Generator of uniformly distributed random numbers.
94 * @param source Source to copy.
95 */
96 private CombinationSampler(UniformRandomProvider rng,
97 CombinationSampler source) {
98 // Do not clone the domain. This ensures:
99 // 1. Thread safety as the domain may be shuffled during the clone
100 // and a shuffle swap step can result in duplicates and missing elements
101 // in the array.
102 // 2. If the argument RNG is an exact match for the RNG in the source
103 // then the output sequence will differ unless the domain is currently
104 // in natural order.
105 domain = PermutationSampler.natural(source.domain.length);
106 steps = source.steps;
107 upper = source.upper;
108 this.rng = rng;
109 }
110
111 /**
112 * Return a combination of {@code k} whose entries are selected randomly,
113 * without repetition, from the integers 0, 1, ..., {@code n}-1 (inclusive).
114 *
115 * <p>The order of the returned array is not guaranteed to be in a random order
116 * as the order of a combination <strong>does not matter</strong>.
117 *
118 * @return a random combination.
119 */
120 @Override
121 public int[] sample() {
122 return SubsetSamplerUtils.partialSample(domain, steps, rng, upper);
123 }
124
125 /**
126 * {@inheritDoc}
127 *
128 * @since 1.3
129 */
130 @Override
131 public CombinationSampler withUniformRandomProvider(UniformRandomProvider rng) {
132 return new CombinationSampler(rng, this);
133 }
134 }