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