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 }