001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 018package org.apache.commons.rng.sampling; 019 020import java.util.Arrays; 021 022import org.apache.commons.rng.UniformRandomProvider; 023 024/** 025 * Class for representing permutations of a sequence of integers. 026 * 027 * This class also contains utilities for shuffling an {@code int[]} array in-place. 028 */ 029public class PermutationSampler { 030 /** Domain of the permutation. */ 031 private final int[] domain; 032 /** Size of the permutation. */ 033 private final int size; 034 /** RNG. */ 035 private final UniformRandomProvider rng; 036 037 /** 038 * Creates a generator of permutations. 039 * 040 * The {@link #sample()} method will generate an integer array of 041 * length {@code k} whose entries are selected randomly, without 042 * repetition, from the integers 0, 1, ..., {@code n}-1 (inclusive). 043 * The returned array represents a permutation of {@code n} taken 044 * {@code k}. 045 * 046 * @param rng Generator of uniformly distributed random numbers. 047 * @param n Domain of the permutation. 048 * @param k Size of the permutation. 049 * @throws IllegalArgumentException if {@code n < 0} or {@code k <= 0} 050 * or {@code k > n}. 051 */ 052 public PermutationSampler(UniformRandomProvider rng, 053 int n, 054 int k) { 055 if (n < 0) { 056 throw new IllegalArgumentException(n + " < " + 0); 057 } 058 if (k <= 0) { 059 throw new IllegalArgumentException(k + " <= " + 0); 060 } 061 if (k > n) { 062 throw new IllegalArgumentException(k + " > " + n); 063 } 064 065 domain = natural(n); 066 size = k; 067 this.rng = rng; 068 } 069 070 /** 071 * @return a random permutation. 072 * 073 * @see #PermutationSampler(UniformRandomProvider,int,int) 074 */ 075 public int[] sample() { 076 shuffle(rng, domain); 077 return Arrays.copyOf(domain, size); 078 } 079 080 /** 081 * Shuffles the entries of the given array. 082 * 083 * @see #shuffle(UniformRandomProvider,int[],int,boolean) 084 * 085 * @param rng Random number generator. 086 * @param list Array whose entries will be shuffled (in-place). 087 */ 088 public static void shuffle(UniformRandomProvider rng, 089 int[] list) { 090 shuffle(rng, list, 0, false); 091 } 092 093 /** 094 * Shuffles the entries of the given array, using the 095 * <a href="http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm"> 096 * Fisher-Yates</a> algorithm. 097 * The {@code start} and {@code pos} parameters select which part 098 * of the array is randomized and which is left untouched. 099 * 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}