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 java.util.Arrays;
021
022import org.apache.commons.rng.UniformRandomProvider;
023
024/**
025 * Class for representing permutations of a sequence of integers.
026 *
027 * This class also contains utilities for shuffling an {@code int[]} array in-place.
028 */
029public class PermutationSampler {
030    /** Domain of the permutation. */
031    private final int[] domain;
032    /** Size of the permutation. */
033    private final int size;
034    /** RNG. */
035    private final UniformRandomProvider rng;
036
037    /**
038     * Creates a generator of permutations.
039     *
040     * The {@link #sample()} method will generate an integer array of
041     * length {@code k} whose entries are selected randomly, without
042     * repetition, from the integers 0, 1, ..., {@code n}-1 (inclusive).
043     * The returned array represents a permutation of {@code n} taken
044     * {@code k}.
045     *
046     * @param rng Generator of uniformly distributed random numbers.
047     * @param n Domain of the permutation.
048     * @param k Size of the permutation.
049     * @throws IllegalArgumentException if {@code n < 0} or {@code k <= 0}
050     * or {@code k > n}.
051     */
052    public PermutationSampler(UniformRandomProvider rng,
053                              int n,
054                              int k) {
055        if (n < 0) {
056            throw new IllegalArgumentException(n + " < " + 0);
057        }
058        if (k <= 0) {
059            throw new IllegalArgumentException(k + " <= " + 0);
060        }
061        if (k > n) {
062            throw new IllegalArgumentException(k + " > " + n);
063        }
064
065        domain = natural(n);
066        size = k;
067        this.rng = rng;
068    }
069
070    /**
071     * @return a random permutation.
072     *
073     * @see #PermutationSampler(UniformRandomProvider,int,int)
074     */
075    public int[] sample() {
076        shuffle(rng, domain);
077        return Arrays.copyOf(domain, size);
078    }
079
080    /**
081     * Shuffles the entries of the given array.
082     *
083     * @see #shuffle(UniformRandomProvider,int[],int,boolean)
084     *
085     * @param rng Random number generator.
086     * @param list Array whose entries will be shuffled (in-place).
087     */
088    public static void shuffle(UniformRandomProvider rng,
089                               int[] list) {
090        shuffle(rng, list, 0, false);
091    }
092
093    /**
094     * Shuffles the entries of the given array, using the
095     * <a href="http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm">
096     * Fisher-Yates</a> algorithm.
097     * The {@code start} and {@code pos} parameters select which part
098     * of the array is randomized and which is left untouched.
099     *
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}