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/Permutation">permutations</a> 24 * of a sequence of integers. 25 * 26 * <p>This class also contains utilities for shuffling an {@code int[]} array in-place. 27 */ 28 public class PermutationSampler { 29 /** Domain of the permutation. */ 30 private final int[] domain; 31 /** Size of the permutation. */ 32 private final int size; 33 /** RNG. */ 34 private final UniformRandomProvider rng; 35 36 /** 37 * Creates a generator of permutations. 38 * 39 * <p>The {@link #sample()} method will generate an integer array of 40 * length {@code k} whose entries are selected randomly, without 41 * repetition, from the integers 0, 1, ..., {@code n}-1 (inclusive). 42 * The returned array represents a permutation of {@code n} taken 43 * {@code k}. 44 * 45 * @param rng Generator of uniformly distributed random numbers. 46 * @param n Domain of the permutation. 47 * @param k Size of the permutation. 48 * @throws IllegalArgumentException if {@code n <= 0} or {@code k <= 0} 49 * or {@code k > n}. 50 */ 51 public PermutationSampler(UniformRandomProvider rng, 52 int n, 53 int k) { 54 SubsetSamplerUtils.checkSubset(n, k); 55 domain = natural(n); 56 size = k; 57 this.rng = rng; 58 } 59 60 /** 61 * @return a random permutation. 62 * 63 * @see #PermutationSampler(UniformRandomProvider,int,int) 64 */ 65 public int[] sample() { 66 return SubsetSamplerUtils.partialSample(domain, size, rng, true); 67 } 68 69 /** 70 * Shuffles the entries of the given array. 71 * 72 * @see #shuffle(UniformRandomProvider,int[],int,boolean) 73 * 74 * @param rng Random number generator. 75 * @param list Array whose entries will be shuffled (in-place). 76 */ 77 public static void shuffle(UniformRandomProvider rng, 78 int[] list) { 79 shuffle(rng, list, list.length - 1, true); 80 } 81 82 /** 83 * Shuffles the entries of the given array, using the 84 * <a href="http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm"> 85 * Fisher-Yates</a> algorithm. 86 * The {@code start} and {@code towardHead} parameters select which part 87 * of the array is randomized and which is left untouched. 88 * 89 * @param rng Random number generator. 90 * @param list Array whose entries will be shuffled (in-place). 91 * @param start Index at which shuffling begins. 92 * @param towardHead Shuffling is performed for index positions between 93 * {@code start} and either the end (if {@code false}) or the beginning 94 * (if {@code true}) of the array. 95 */ 96 public static void shuffle(UniformRandomProvider rng, 97 int[] list, 98 int start, 99 boolean towardHead) { 100 if (towardHead) { 101 // Visit all positions from start to 0. 102 // Do not visit 0 to avoid a swap with itself. 103 for (int i = start; i > 0; i--) { 104 // Swap index with any position down to 0 105 SubsetSamplerUtils.swap(list, i, rng.nextInt(i + 1)); 106 } 107 } else { 108 // Visit all positions from the end to start. 109 // Start is not visited to avoid a swap with itself. 110 for (int i = list.length - 1; i > start; i--) { 111 // Swap index with any position down to start. 112 // Note: i - start + 1 is the number of elements remaining. 113 SubsetSamplerUtils.swap(list, i, rng.nextInt(i - start + 1) + start); 114 } 115 } 116 } 117 118 /** 119 * Creates an array representing the natural number {@code n}. 120 * 121 * @param n Natural number. 122 * @return an array whose entries are the numbers 0, 1, ..., {@code n}-1. 123 * If {@code n == 0}, the returned array is empty. 124 */ 125 public static int[] natural(int n) { 126 final int[] a = new int[n]; 127 for (int i = 0; i < n; i++) { 128 a[i] = i; 129 } 130 return a; 131 } 132 }