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 * Utility class for selecting a subset of a sequence of integers.
24 */
25 final class SubsetSamplerUtils {
26
27 /** No public construction. */
28 private SubsetSamplerUtils() {}
29
30 /**
31 * Checks the subset of length {@code k} from {@code n} is valid.
32 *
33 * <p>If {@code n <= 0} or {@code k <= 0} or {@code k > n} then no subset
34 * is required and an exception is raised.</p>
35 *
36 * @param n Size of the set.
37 * @param k Size of the subset.
38 * @throws IllegalArgumentException if {@code n <= 0} or {@code k <= 0} or
39 * {@code k > n}.
40 */
41 static void checkSubset(int n,
42 int k) {
43 if (n <= 0) {
44 throw new IllegalArgumentException("n <= 0 : n=" + n);
45 }
46 if (k <= 0) {
47 throw new IllegalArgumentException("k <= 0 : k=" + k);
48 }
49 if (k > n) {
50 throw new IllegalArgumentException("k > n : k=" + k + ", n=" + n);
51 }
52 }
53
54 /**
55 * Perform a partial Fisher-Yates shuffle of the domain in-place and return
56 * either the upper fully shuffled section or the remaining lower partially
57 * shuffled section.
58 *
59 * <p>The returned combination will have a length of {@code steps} for
60 * {@code upper=true}, or {@code domain.length - steps} otherwise.</p>
61 *
62 * <p>Sampling uses {@link UniformRandomProvider#nextInt(int)}.</p>
63 *
64 * @param domain The domain.
65 * @param steps The number of shuffle steps.
66 * @param rng Generator of uniformly distributed random numbers.
67 * @param upper Set to true to return the upper fully shuffled section.
68 * @return a random combination.
69 */
70 static int[] partialSample(int[] domain,
71 int steps,
72 UniformRandomProvider rng,
73 boolean upper) {
74 // Shuffle from the end but limit to the number of steps.
75 // Note: If 'steps' is the full length of the array then the final
76 // swap is redundant so can be skipped.
77 int swapCount = Math.min(steps, domain.length - 1);
78 for (int i = domain.length - 1; swapCount > 0; i--, swapCount--) {
79 // Swap index i with any position down to 0 (including itself)
80 swap(domain, i, rng.nextInt(i + 1));
81 }
82 final int size = upper ? steps : domain.length - steps;
83 final int from = upper ? domain.length - steps : 0;
84 final int[] result = new int[size];
85 System.arraycopy(domain, from, result, 0, size);
86 return result;
87 }
88
89 /**
90 * Swaps the two specified elements in the specified array.
91 *
92 * @param array the array
93 * @param i the first index
94 * @param j the second index
95 */
96 static void swap(int[] array, int i, int j) {
97 final int tmp = array[i];
98 array[i] = array[j];
99 array[j] = tmp;
100 }
101 }