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}