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    
037    package org.jblas.util;
038    
039    import java.util.Random;
040    import org.jblas.DoubleMatrix;
041    
042    /**
043     * Functions which generate random permutations.
044     *
045     * @author Mikio L. Braun
046     */
047    public 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    }