View Javadoc
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 = PermutationSampler.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 }