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 org.apache.commons.rng.UniformRandomProvider; 021 022/** 023 * Class for representing <a href="https://en.wikipedia.org/wiki/Permutation">permutations</a> 024 * of a sequence of integers. 025 * 026 * <p>Sampling uses {@link UniformRandomProvider#nextInt(int)}.</p> 027 * 028 * <p>This class also contains utilities for shuffling an {@code int[]} array in-place.</p> 029 */ 030public class PermutationSampler implements SharedStateSampler<PermutationSampler> { 031 /** Domain of the permutation. */ 032 private final int[] domain; 033 /** Size of the permutation. */ 034 private final int size; 035 /** RNG. */ 036 private final UniformRandomProvider rng; 037 038 /** 039 * Creates a generator of permutations. 040 * 041 * <p>The {@link #sample()} method will generate an integer array of 042 * length {@code k} whose entries are selected randomly, without 043 * repetition, from the integers 0, 1, ..., {@code n}-1 (inclusive). 044 * The returned array represents a permutation of {@code n} taken 045 * {@code k}.</p> 046 * 047 * @param rng Generator of uniformly distributed random numbers. 048 * @param n Domain of the permutation. 049 * @param k Size of the permutation. 050 * @throws IllegalArgumentException if {@code n <= 0} or {@code k <= 0} 051 * or {@code k > n}. 052 */ 053 public PermutationSampler(UniformRandomProvider rng, 054 int n, 055 int k) { 056 SubsetSamplerUtils.checkSubset(n, k); 057 domain = natural(n); 058 size = k; 059 this.rng = rng; 060 } 061 062 /** 063 * @param rng Generator of uniformly distributed random numbers. 064 * @param source Source to copy. 065 */ 066 private PermutationSampler(UniformRandomProvider rng, 067 PermutationSampler source) { 068 // Do not clone the domain. This ensures: 069 // 1. Thread safety as the domain may be shuffled during the clone 070 // and an incomplete shuffle swap step can result in duplicates and 071 // missing elements in the array. 072 // 2. If the argument RNG is an exact match for the RNG in the source 073 // then the output sequence will differ unless the domain is currently 074 // in natural order. 075 domain = PermutationSampler.natural(source.domain.length); 076 size = source.size; 077 this.rng = rng; 078 } 079 080 /** 081 * @return a random permutation. 082 * 083 * @see #PermutationSampler(UniformRandomProvider,int,int) 084 */ 085 public int[] sample() { 086 return SubsetSamplerUtils.partialSample(domain, size, rng, true); 087 } 088 089 /** 090 * {@inheritDoc} 091 * 092 * @since 1.3 093 */ 094 @Override 095 public PermutationSampler withUniformRandomProvider(UniformRandomProvider rng) { 096 return new PermutationSampler(rng, this); 097 } 098 099 /** 100 * Shuffles the entries of the given array. 101 * 102 * @see #shuffle(UniformRandomProvider,int[],int,boolean) 103 * 104 * @param rng Random number generator. 105 * @param list Array whose entries will be shuffled (in-place). 106 */ 107 public static void shuffle(UniformRandomProvider rng, 108 int[] list) { 109 shuffle(rng, list, list.length - 1, true); 110 } 111 112 /** 113 * Shuffles the entries of the given array, using the 114 * <a href="http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm"> 115 * Fisher-Yates</a> algorithm. 116 * The {@code start} and {@code towardHead} parameters select which part 117 * of the array is randomized and which is left untouched. 118 * 119 * <p>Sampling uses {@link UniformRandomProvider#nextInt(int)}.</p> 120 * 121 * @param rng Random number generator. 122 * @param list Array whose entries will be shuffled (in-place). 123 * @param start Index at which shuffling begins. 124 * @param towardHead Shuffling is performed for index positions between 125 * {@code start} and either the end (if {@code false}) or the beginning 126 * (if {@code true}) of the array. 127 */ 128 public static void shuffle(UniformRandomProvider rng, 129 int[] list, 130 int start, 131 boolean towardHead) { 132 if (towardHead) { 133 // Visit all positions from start to 0. 134 // Do not visit 0 to avoid a swap with itself. 135 for (int i = start; i > 0; i--) { 136 // Swap index with any position down to 0 137 SubsetSamplerUtils.swap(list, i, rng.nextInt(i + 1)); 138 } 139 } else { 140 // Visit all positions from the end to start. 141 // Start is not visited to avoid a swap with itself. 142 for (int i = list.length - 1; i > start; i--) { 143 // Swap index with any position down to start. 144 // Note: i - start + 1 is the number of elements remaining. 145 SubsetSamplerUtils.swap(list, i, rng.nextInt(i - start + 1) + start); 146 } 147 } 148 } 149 150 /** 151 * Creates an array representing the natural number {@code n}. 152 * 153 * @param n Natural number. 154 * @return an array whose entries are the numbers 0, 1, ..., {@code n}-1. 155 * If {@code n == 0}, the returned array is empty. 156 */ 157 public static int[] natural(int n) { 158 final int[] a = new int[n]; 159 for (int i = 0; i < n; i++) { 160 a[i] = i; 161 } 162 return a; 163 } 164}