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; 041import org.jblas.FloatMatrix; 042 043/** 044 * Functions which generate random permutations. 045 * 046 * @author Mikio L. Braun 047 */ 048public class Permutations { 049 /** 050 * Create a random permutation of the numbers 0, ..., size - 1. 051 * 052 * see Algorithm P, D.E. Knuth: The Art of Computer Programming, Vol. 2, p. 145 053 */ 054 public static int[] randomPermutation(int size) { 055 Random r = new Random(); 056 int[] result = new int[size]; 057 058 for (int j = 0; j < size; j++) { 059 result[j] = j; 060 } 061 062 for (int j = size - 1; j > 0; j--) { 063 int k = r.nextInt(j); 064 int temp = result[j]; 065 result[j] = result[k]; 066 result[k] = temp; 067 } 068 069 return result; 070 } 071 072 /** 073 * Get a random sample of k out of n elements. 074 * 075 * See Algorithm S, D. E. Knuth, The Art of Computer Programming, Vol. 2, p.142. 076 */ 077 public static int[] randomSubset(int k, int n) { 078 assert(0 < k && k <= n); 079 Random r = new Random(); 080 int t = 0, m = 0; 081 int[] result = new int[k]; 082 083 while (m < k) { 084 double u = r.nextDouble(); 085 if ( (n - t) * u < k - m ) { 086 result[m] = t; 087 m++; 088 } 089 t++; 090 } 091 return result; 092 } 093 094 /** 095 * Create a permutation matrix from a LAPACK-style 'ipiv' vector. 096 * 097 * @param ipiv row i was interchanged with row ipiv[i] 098 */ 099 public static DoubleMatrix permutationDoubleMatrixFromPivotIndices(int size, int[] ipiv) { 100 int n = ipiv.length; 101 //System.out.printf("size = %d n = %d\n", size, n); 102 int indices[] = new int[size]; 103 for (int i = 0; i < size; i++) 104 indices[i] = i; 105 106 //for (int i = 0; i < n; i++) 107 // System.out.printf("ipiv[%d] = %d\n", i, ipiv[i]); 108 109 for (int i = 0; i < n; i++) { 110 int j = ipiv[i] - 1; 111 int t = indices[i]; 112 indices[i] = indices[j]; 113 indices[j] = t; 114 } 115 DoubleMatrix result = new DoubleMatrix(size, size); 116 for (int i = 0; i < size; i++) 117 result.put(indices[i], i, 1.0); 118 return result; 119 } 120 121 /** 122 * Create a permutation matrix from a LAPACK-style 'ipiv' vector. 123 * 124 * @param ipiv row i was interchanged with row ipiv[i] 125 */ 126 public static FloatMatrix permutationFloatMatrixFromPivotIndices(int size, int[] ipiv) { 127 int n = ipiv.length; 128 //System.out.printf("size = %d n = %d\n", size, n); 129 int indices[] = new int[size]; 130 for (int i = 0; i < size; i++) 131 indices[i] = i; 132 133 //for (int i = 0; i < n; i++) 134 // System.out.printf("ipiv[%d] = %d\n", i, ipiv[i]); 135 136 for (int i = 0; i < n; i++) { 137 int j = ipiv[i] - 1; 138 int t = indices[i]; 139 indices[i] = indices[j]; 140 indices[j] = t; 141 } 142 FloatMatrix result = new FloatMatrix(size, size); 143 for (int i = 0; i < size; i++) 144 result.put(indices[i], i, 1.0f); 145 return result; 146 } 147}