001    /*
002     * To change this template, choose Tools | Templates
003     * and open the template in the editor.
004     */
005    
006    package org.jblas.util;
007    
008    import java.util.Random;
009    import org.jblas.DoubleMatrix;
010    
011    /**
012     *
013     */
014    public class Permutations {
015        /**
016         * Create a random permutation of the numbers 0, ..., size - 1.
017         *
018         * see Algorithm P, D.E. Knuth: The Art of Computer Programming, Vol. 2, p. 145
019         */
020        public static int[] randomPermutation(int size) {
021            Random r = new Random();
022            int[] result = new int[size];
023    
024            for (int j = 0; j < size; j++) {
025                result[j] = j;
026            }
027            
028            for (int j = size - 1; j > 0; j--) {
029                int k = r.nextInt(j);
030                int temp = result[j];
031                result[j] = result[k];
032                result[k] = temp;
033            }
034    
035            return result;
036        }
037        
038        /**
039         * Get a random sample of k out of n elements.
040         *
041         * See Algorithm S, D. E. Knuth, The Art of Computer Programming, Vol. 2, p.142.
042         */
043        public static int[] randomSubset(int k, int n) {
044            assert(0 < k && k <= n);
045            Random r = new Random();
046            int t = 0, m = 0;
047            int[] result = new int[k];
048    
049            while (m < k) {
050                double u = r.nextDouble();
051                if ( (n - t) * u < k - m ) {
052                    result[m] = t;
053                    m++;
054                }
055                t++;
056            }
057            return result;
058        }
059    
060        /**
061         * Create a permutation matrix from a LAPACK-style 'ipiv' vector.
062         *
063         * @param ipiv row i was interchanged with row ipiv[i]
064         */
065        public static DoubleMatrix permutationMatrixFromPivotIndices(int size, int[] ipiv) {
066            int n = ipiv.length;
067            //System.out.printf("size = %d n = %d\n", size, n);
068            int indices[] = new int[size];
069            for (int i = 0; i < size; i++)
070                indices[i] = i;
071    
072            //for (int i = 0; i < n; i++)
073            //    System.out.printf("ipiv[%d] = %d\n", i, ipiv[i]);
074    
075            for (int i = 0; i < n; i++) {
076                int j = ipiv[i] - 1;
077                int t = indices[i];
078                indices[i] = indices[j];
079                indices[j] = t;
080            }
081            DoubleMatrix result = new DoubleMatrix(size, size);
082            for (int i = 0; i < size; i++)
083                result.put(indices[i], i, 1.0);
084            return result;
085        }
086    }