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>Sampling uses {@link UniformRandomProvider#nextInt(int)}.</p>
027 *
028 * <p>This class also contains utilities for shuffling an {@code int[]} array in-place.</p>
029 */
030public class PermutationSampler implements SharedStateObjectSampler<int[]> {
031    /** Domain of the permutation. */
032    private final int[] domain;
033    /** Size of the permutation. */
034    private final int size;
035    /** RNG. */
036    private final UniformRandomProvider rng;
037
038    /**
039     * Creates a generator of permutations.
040     *
041     * <p>The {@link #sample()} method will generate an integer array of
042     * length {@code k} whose entries are selected randomly, without
043     * repetition, from the integers 0, 1, ..., {@code n}-1 (inclusive).
044     * The returned array represents a permutation of {@code n} taken
045     * {@code k}.</p>
046     *
047     * @param rng Generator of uniformly distributed random numbers.
048     * @param n Domain of the permutation.
049     * @param k Size of the permutation.
050     * @throws IllegalArgumentException if {@code n <= 0} or {@code k <= 0}
051     * or {@code k > n}.
052     */
053    public PermutationSampler(UniformRandomProvider rng,
054                              int n,
055                              int k) {
056        SubsetSamplerUtils.checkSubset(n, k);
057        domain = natural(n);
058        size = k;
059        this.rng = rng;
060    }
061
062    /**
063     * @param rng Generator of uniformly distributed random numbers.
064     * @param source Source to copy.
065     */
066    private PermutationSampler(UniformRandomProvider rng,
067                               PermutationSampler source) {
068        // Do not clone the domain. This ensures:
069        // 1. Thread safety as the domain may be shuffled during the clone
070        //    and an incomplete shuffle swap step can result in duplicates and
071        //    missing elements in the array.
072        // 2. If the argument RNG is an exact match for the RNG in the source
073        //    then the output sequence will differ unless the domain is currently
074        //    in natural order.
075        domain = natural(source.domain.length);
076        size = source.size;
077        this.rng = rng;
078    }
079
080    /**
081     * @return a random permutation.
082     * @see #PermutationSampler(UniformRandomProvider,int,int)
083     */
084    @Override
085    public int[] sample() {
086        return SubsetSamplerUtils.partialSample(domain, size, rng, true);
087    }
088
089    /**
090     * {@inheritDoc}
091     *
092     * @since 1.3
093     */
094    @Override
095    public PermutationSampler withUniformRandomProvider(UniformRandomProvider rng) {
096        return new PermutationSampler(rng, this);
097    }
098
099    /**
100     * Shuffles the entries of the given array.
101     *
102     * @param rng Random number generator.
103     * @param list Array whose entries will be shuffled (in-place).
104     * @see #shuffle(UniformRandomProvider,int[],int,boolean)
105     */
106    public static void shuffle(UniformRandomProvider rng,
107                               int[] list) {
108        ArraySampler.shuffle(rng, list);
109    }
110
111    /**
112     * Shuffles the entries of the given array, using the
113     * <a href="https://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm">
114     * Fisher-Yates</a> algorithm.
115     * The {@code start} and {@code towardHead} parameters select which part
116     * of the array is randomized and which is left untouched.
117     *
118     * <p>Sampling uses {@link UniformRandomProvider#nextInt()}.</p>
119     *
120     * @param rng Random number generator.
121     * @param list Array whose entries will be shuffled (in-place).
122     * @param start Index at which shuffling begins.
123     * @param towardHead Shuffling is performed for index positions between
124     * {@code start} and either the end (if {@code false}) or the beginning
125     * (if {@code true}) of the array.
126     */
127    public static void shuffle(UniformRandomProvider rng,
128                               int[] list,
129                               int start,
130                               boolean towardHead) {
131        if (towardHead) {
132            // Visit all positions from start to 0.
133            ArraySampler.shuffle(rng, list, 0, start + 1);
134        } else {
135            // Visit all positions from the end to start.
136            ArraySampler.shuffle(rng, list, start, list.length);
137        }
138    }
139
140    /**
141     * Creates an array representing the natural number {@code n}.
142     *
143     * @param n Natural number.
144     * @return an array whose entries are the numbers 0, 1, ..., {@code n}-1.
145     * If {@code n == 0}, the returned array is empty.
146     */
147    public static int[] natural(int n) {
148        final int[] a = new int[n];
149        for (int i = 0; i < n; i++) {
150            a[i] = i;
151        }
152        return a;
153    }
154}