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>Sampling uses {@link UniformRandomProvider#nextInt(int)}.</p>
27 *
28 * <p>This class also contains utilities for shuffling an {@code int[]} array in-place.</p>
29 */
30 public class PermutationSampler implements SharedStateObjectSampler<int[]> {
31 /** Domain of the permutation. */
32 private final int[] domain;
33 /** Size of the permutation. */
34 private final int size;
35 /** RNG. */
36 private final UniformRandomProvider rng;
37
38 /**
39 * Creates a generator of permutations.
40 *
41 * <p>The {@link #sample()} method will generate an integer array of
42 * length {@code k} whose entries are selected randomly, without
43 * repetition, from the integers 0, 1, ..., {@code n}-1 (inclusive).
44 * The returned array represents a permutation of {@code n} taken
45 * {@code k}.</p>
46 *
47 * @param rng Generator of uniformly distributed random numbers.
48 * @param n Domain of the permutation.
49 * @param k Size of the permutation.
50 * @throws IllegalArgumentException if {@code n <= 0} or {@code k <= 0}
51 * or {@code k > n}.
52 */
53 public PermutationSampler(UniformRandomProvider rng,
54 int n,
55 int k) {
56 SubsetSamplerUtils.checkSubset(n, k);
57 domain = natural(n);
58 size = k;
59 this.rng = rng;
60 }
61
62 /**
63 * @param rng Generator of uniformly distributed random numbers.
64 * @param source Source to copy.
65 */
66 private PermutationSampler(UniformRandomProvider rng,
67 PermutationSampler source) {
68 // Do not clone the domain. This ensures:
69 // 1. Thread safety as the domain may be shuffled during the clone
70 // and an incomplete shuffle swap step can result in duplicates and
71 // missing elements in the array.
72 // 2. If the argument RNG is an exact match for the RNG in the source
73 // then the output sequence will differ unless the domain is currently
74 // in natural order.
75 domain = natural(source.domain.length);
76 size = source.size;
77 this.rng = rng;
78 }
79
80 /**
81 * @return a random permutation.
82 *
83 * @see #PermutationSampler(UniformRandomProvider,int,int)
84 */
85 @Override
86 public int[] sample() {
87 return SubsetSamplerUtils.partialSample(domain, size, rng, true);
88 }
89
90 /**
91 * {@inheritDoc}
92 *
93 * @since 1.3
94 */
95 @Override
96 public PermutationSampler withUniformRandomProvider(UniformRandomProvider rng) {
97 return new PermutationSampler(rng, this);
98 }
99
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 }