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 }