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   * 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.
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.
61       *
62       * @param domain The domain.
63       * @param steps  The number of shuffle steps.
64       * @param rng    Generator of uniformly distributed random numbers.
65       * @param upper  Set to true to return the upper fully shuffled section.
66       * @return a random combination.
67       */
68      static int[] partialSample(int[] domain,
69                                 int steps,
70                                 UniformRandomProvider rng,
71                                 boolean upper) {
72          // Shuffle from the end but limit to a number of steps.
73          for (int i = domain.length - 1, j = 0; i > 0 && j < steps; i--, j++) {
74              // Swap index i with any position down to 0 (including itself)
75              swap(domain, i, rng.nextInt(i + 1));
76          }
77          final int size = upper ? steps : domain.length - steps;
78          final int from = upper ? domain.length - steps : 0;
79          final int[] result = new int[size];
80          System.arraycopy(domain, from, result, 0, size);
81          return result;
82      }
83  
84      /**
85       * Swaps the two specified elements in the specified array.
86       *
87       * @param array the array
88       * @param i     the first index
89       * @param j     the second index
90       */
91      static void swap(int[] array, int i, int j) {
92          final int tmp = array[i];
93          array[i] = array[j];
94          array[j] = tmp;
95      }
96  }