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>This class also contains utilities for shuffling an {@code int[]} array in-place.
27   */
28  public class PermutationSampler {
29      /** Domain of the permutation. */
30      private final int[] domain;
31      /** Size of the permutation. */
32      private final int size;
33      /** RNG. */
34      private final UniformRandomProvider rng;
35  
36      /**
37       * Creates a generator of permutations.
38       *
39       * <p>The {@link #sample()} method will generate an integer array of
40       * length {@code k} whose entries are selected randomly, without
41       * repetition, from the integers 0, 1, ..., {@code n}-1 (inclusive).
42       * The returned array represents a permutation of {@code n} taken
43       * {@code k}.
44       *
45       * @param rng Generator of uniformly distributed random numbers.
46       * @param n Domain of the permutation.
47       * @param k Size of the permutation.
48       * @throws IllegalArgumentException if {@code n <= 0} or {@code k <= 0}
49       * or {@code k > n}.
50       */
51      public PermutationSampler(UniformRandomProvider rng,
52                                int n,
53                                int k) {
54          SubsetSamplerUtils.checkSubset(n, k);
55          domain = natural(n);
56          size = k;
57          this.rng = rng;
58      }
59  
60      /**
61       * @return a random permutation.
62       *
63       * @see #PermutationSampler(UniformRandomProvider,int,int)
64       */
65      public int[] sample() {
66          return SubsetSamplerUtils.partialSample(domain, size, rng, true);
67      }
68  
69      /**
70       * Shuffles the entries of the given array.
71       *
72       * @see #shuffle(UniformRandomProvider,int[],int,boolean)
73       *
74       * @param rng Random number generator.
75       * @param list Array whose entries will be shuffled (in-place).
76       */
77      public static void shuffle(UniformRandomProvider rng,
78                                 int[] list) {
79          shuffle(rng, list, list.length - 1, true);
80      }
81  
82      /**
83       * Shuffles the entries of the given array, using the
84       * <a href="http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm">
85       * Fisher-Yates</a> algorithm.
86       * The {@code start} and {@code towardHead} parameters select which part
87       * of the array is randomized and which is left untouched.
88       *
89       * @param rng Random number generator.
90       * @param list Array whose entries will be shuffled (in-place).
91       * @param start Index at which shuffling begins.
92       * @param towardHead Shuffling is performed for index positions between
93       * {@code start} and either the end (if {@code false}) or the beginning
94       * (if {@code true}) of the array.
95       */
96      public static void shuffle(UniformRandomProvider rng,
97                                 int[] list,
98                                 int start,
99                                 boolean towardHead) {
100         if (towardHead) {
101             // Visit all positions from start to 0.
102             // Do not visit 0 to avoid a swap with itself.
103             for (int i = start; i > 0; i--) {
104                 // Swap index with any position down to 0
105                 SubsetSamplerUtils.swap(list, i, rng.nextInt(i + 1));
106             }
107         } else {
108             // Visit all positions from the end to start.
109             // Start is not visited to avoid a swap with itself.
110             for (int i = list.length - 1; i > start; i--) {
111                 // Swap index with any position down to start.
112                 // Note: i - start + 1 is the number of elements remaining.
113                 SubsetSamplerUtils.swap(list, i, rng.nextInt(i - start + 1) + start);
114             }
115         }
116     }
117 
118     /**
119      * Creates an array representing the natural number {@code n}.
120      *
121      * @param n Natural number.
122      * @return an array whose entries are the numbers 0, 1, ..., {@code n}-1.
123      * If {@code n == 0}, the returned array is empty.
124      */
125     public static int[] natural(int n) {
126         final int[] a = new int[n];
127         for (int i = 0; i < n; i++) {
128             a[i] = i;
129         }
130         return a;
131     }
132 }