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