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 }