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 SharedStateObjectSampler<int[]> { 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 = 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 @Override 086 public int[] sample() { 087 return SubsetSamplerUtils.partialSample(domain, size, rng, true); 088 } 089 090 /** 091 * {@inheritDoc} 092 * 093 * @since 1.3 094 */ 095 @Override 096 public PermutationSampler withUniformRandomProvider(UniformRandomProvider rng) { 097 return new PermutationSampler(rng, this); 098 } 099 100 /** 101 * Shuffles the entries of the given array. 102 * 103 * @see #shuffle(UniformRandomProvider,int[],int,boolean) 104 * 105 * @param rng Random number generator. 106 * @param list Array whose entries will be shuffled (in-place). 107 */ 108 public static void shuffle(UniformRandomProvider rng, 109 int[] list) { 110 shuffle(rng, list, list.length - 1, true); 111 } 112 113 /** 114 * Shuffles the entries of the given array, using the 115 * <a href="http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm"> 116 * Fisher-Yates</a> algorithm. 117 * The {@code start} and {@code towardHead} parameters select which part 118 * of the array is randomized and which is left untouched. 119 * 120 * <p>Sampling uses {@link UniformRandomProvider#nextInt(int)}.</p> 121 * 122 * @param rng Random number generator. 123 * @param list Array whose entries will be shuffled (in-place). 124 * @param start Index at which shuffling begins. 125 * @param towardHead Shuffling is performed for index positions between 126 * {@code start} and either the end (if {@code false}) or the beginning 127 * (if {@code true}) of the array. 128 */ 129 public static void shuffle(UniformRandomProvider rng, 130 int[] list, 131 int start, 132 boolean towardHead) { 133 if (towardHead) { 134 // Visit all positions from start to 0. 135 // Do not visit 0 to avoid a swap with itself. 136 for (int i = start; i > 0; i--) { 137 // Swap index with any position down to 0 138 SubsetSamplerUtils.swap(list, i, rng.nextInt(i + 1)); 139 } 140 } else { 141 // Visit all positions from the end to start. 142 // Start is not visited to avoid a swap with itself. 143 for (int i = list.length - 1; i > start; i--) { 144 // Swap index with any position down to start. 145 // Note: i - start + 1 is the number of elements remaining. 146 SubsetSamplerUtils.swap(list, i, rng.nextInt(i - start + 1) + start); 147 } 148 } 149 } 150 151 /** 152 * Creates an array representing the natural number {@code n}. 153 * 154 * @param n Natural number. 155 * @return an array whose entries are the numbers 0, 1, ..., {@code n}-1. 156 * If {@code n == 0}, the returned array is empty. 157 */ 158 public static int[] natural(int n) { 159 final int[] a = new int[n]; 160 for (int i = 0; i < n; i++) { 161 a[i] = i; 162 } 163 return a; 164 } 165}