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