001// --- BEGIN LICENSE BLOCK ---
002/*
003 * Copyright (c) 2009, Mikio L. Braun
004 * All rights reserved.
005 *
006 * Redistribution and use in source and binary forms, with or without
007 * modification, are permitted provided that the following conditions are
008 * met:
009 *
010 *     * Redistributions of source code must retain the above copyright
011 *       notice, this list of conditions and the following disclaimer.
012 *
013 *     * Redistributions in binary form must reproduce the above
014 *       copyright notice, this list of conditions and the following
015 *       disclaimer in the documentation and/or other materials provided
016 *       with the distribution.
017 *
018 *     * Neither the name of the Technische Universit?t Berlin nor the
019 *       names of its contributors may be used to endorse or promote
020 *       products derived from this software without specific prior
021 *       written permission.
022 *
023 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
024 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
025 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
026 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
027 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
028 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
029 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
030 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
031 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
032 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
033 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
034 */
035// --- END LICENSE BLOCK ---
036
037package org.jblas.util;
038
039import java.util.Random;
040import org.jblas.DoubleMatrix;
041
042/**
043 * Functions which generate random permutations.
044 *
045 * @author Mikio L. Braun
046 */
047public class Permutations {
048    /**
049     * Create a random permutation of the numbers 0, ..., size - 1.
050     *
051     * see Algorithm P, D.E. Knuth: The Art of Computer Programming, Vol. 2, p. 145
052     */
053    public static int[] randomPermutation(int size) {
054        Random r = new Random();
055        int[] result = new int[size];
056
057        for (int j = 0; j < size; j++) {
058            result[j] = j;
059        }
060        
061        for (int j = size - 1; j > 0; j--) {
062            int k = r.nextInt(j);
063            int temp = result[j];
064            result[j] = result[k];
065            result[k] = temp;
066        }
067
068        return result;
069    }
070    
071    /**
072     * Get a random sample of k out of n elements.
073     *
074     * See Algorithm S, D. E. Knuth, The Art of Computer Programming, Vol. 2, p.142.
075     */
076    public static int[] randomSubset(int k, int n) {
077        assert(0 < k && k <= n);
078        Random r = new Random();
079        int t = 0, m = 0;
080        int[] result = new int[k];
081
082        while (m < k) {
083            double u = r.nextDouble();
084            if ( (n - t) * u < k - m ) {
085                result[m] = t;
086                m++;
087            }
088            t++;
089        }
090        return result;
091    }
092
093    /**
094     * Create a permutation matrix from a LAPACK-style 'ipiv' vector.
095     *
096     * @param ipiv row i was interchanged with row ipiv[i]
097     */
098    public static DoubleMatrix permutationMatrixFromPivotIndices(int size, int[] ipiv) {
099        int n = ipiv.length;
100        //System.out.printf("size = %d n = %d\n", size, n);
101        int indices[] = new int[size];
102        for (int i = 0; i < size; i++)
103            indices[i] = i;
104
105        //for (int i = 0; i < n; i++)
106        //    System.out.printf("ipiv[%d] = %d\n", i, ipiv[i]);
107
108        for (int i = 0; i < n; i++) {
109            int j = ipiv[i] - 1;
110            int t = indices[i];
111            indices[i] = indices[j];
112            indices[j] = t;
113        }
114        DoubleMatrix result = new DoubleMatrix(size, size);
115        for (int i = 0; i < size; i++)
116            result.put(indices[i], i, 1.0);
117        return result;
118    }
119}