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 }