RandomPermutation.java

/*
 * Class:        RandomPermutation
 * Description:  Provides methods to randomly shuffle arrays or lists
 * Environment:  Java
 * Software:     SSJ 
 * Copyright (C) 2001  Pierre L'Ecuyer and Universite de Montreal
 * Organization: DIRO, Universite de Montreal
 * @author       
 * @since
 *
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 */
package umontreal.ssj.rng;
 
import java.util.Collections;
import java.util.List;
import java.util.ListIterator;
import java.util.RandomAccess;

public class RandomPermutation {
   private static final int SHUFFLE_THRESHOLD = 5;

   @Deprecated
   public static void init(byte[] array, int n) {
      for (byte k = 1; k <= n; k++)
         array[k - 1] = k;
   }

   @Deprecated
   public static void init(short[] array, int n) {
      for (short k = 1; k <= n; k++)
         array[k - 1] = k;
   }

   @Deprecated
   public static void init(int[] array, int n) {
      for (int k = 1; k <= n; k++)
         array[k - 1] = k;
   }

   @Deprecated
   public static void init(long[] array, int n) {
      for (int k = 1; k <= n; k++)
         array[k - 1] = k;
   }

   @Deprecated
   public static void init(float[] array, int n) {
      for (int k = 1; k <= n; k++)
         array[k - 1] = k;
   }

   @Deprecated
   public static void init(double[] array, int n) {
      for (int k = 1; k <= n; k++)
         array[k - 1] = k;
   }

   @SuppressWarnings("unchecked")
   public static void shuffle(List<?> list, RandomStream stream) {
      // The implementation is inspired from Sun's Collections.shuffle
      final int size = list.size();
      if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
         for (int i = size; i > 1; i--)
            Collections.swap(list, i - 1, stream.nextInt(0, i - 1));
 
      } else {
         final Object arr[] = list.toArray();
 
         // Shuffle array<
         shuffle(arr, stream);
 
         // Dump array back into list
         final ListIterator it = list.listIterator();
         for (Object element : arr) {
            it.next();
            it.set(element);
         }
      }
   }

   public static void shuffle(Object[] array, RandomStream stream) {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt(0, i);
         final Object tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }

   public static void shuffle(byte[] array, RandomStream stream) {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt(0, i);
         final byte tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }

   public static void shuffle(short[] array, RandomStream stream) {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt(0, i);
         final short tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }

   public static void shuffle(int[] array, RandomStream stream) {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt(0, i);
         final int tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }

   public static void shuffle(long[] array, RandomStream stream) {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt(0, i);
         final long tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }

   public static void shuffle(char[] array, RandomStream stream) {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt(0, i);
         final char tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }

   public static void shuffle(boolean[] array, RandomStream stream) {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt(0, i);
         final boolean tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }

   public static void shuffle(float[] array, RandomStream stream) {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt(0, i);
         final float tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }

   public static void shuffle(double[] array, RandomStream stream) {
      final int size = array.length;
      for (int i = size - 1; i > 0; i--) {
         final int j = stream.nextInt(0, i);
         final double tmp = array[i];
         array[i] = array[j];
         array[j] = tmp;
      }
   }

   @SuppressWarnings("unchecked")
   public static void shuffle(List<?> list, int k, RandomStream stream) {
      // @precondition 0 <= k <= n <= size.
 
      // The implementation is inspired from Sun's Collections.shuffle
      final int size = list.size();
      if (k < 0 || k > size)
         throw new IllegalArgumentException("k must be   0 <= k <= list.size()");
      if (0 == k)
         return;
      if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
         for (int i = 0; i < k; i++) {
            // Get random j in {i,...,n-1} and interchange a[i] with a[j].
            int j = stream.nextInt(i, size - 1);
            Collections.swap(list, i, j);
         }
 
      } else {
         final Object arr[] = list.toArray();
 
         // Shuffle array<
         shuffle(arr, size, k, stream);
 
         // Dump array back into list
         final ListIterator it = list.listIterator();
         for (Object element : arr) {
            it.next();
            it.set(element);
         }
      }
   }

   public static void shuffle(Object[] array, int n, int k, RandomStream stream) {
      // @precondition 0 <= k <= n <= a.length.
      // Replace by
      // if (k < 0 || k > n) throw new IllegalArgumentException();
      // or at least assert 0 <= k && k <= n;
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt(i, n - 1);
         Object temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }

   public static void shuffle(byte[] array, int n, int k, RandomStream stream) {
      // @precondition 0 <= k <= n <= a.length.
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt(i, n - 1);
         byte temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }

   public static void shuffle(short[] array, int n, int k, RandomStream stream) {
      // @precondition 0 <= k <= n <= a.length.
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt(i, n - 1);
         short temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }

   public static void shuffle(int[] array, int n, int k, RandomStream stream) {
      // @precondition 0 <= k <= n <= a.length.
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt(i, n - 1);
         int temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }

   public static void shuffle(long[] array, int n, int k, RandomStream stream) {
      // @precondition 0 <= k <= n <= a.length.
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt(i, n - 1);
         long temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }

   public static void shuffle(char[] array, int n, int k, RandomStream stream) {
      // @precondition 0 <= k <= n <= a.length.
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt(i, n - 1);
         char temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }

   public static void shuffle(boolean[] array, int n, int k, RandomStream stream) {
      // @precondition 0 <= k <= n <= a.length.
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt(i, n - 1);
         boolean temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }

   public static void shuffle(float[] array, int n, int k, RandomStream stream) {
      // @precondition 0 <= k <= n <= a.length.
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt(i, n - 1);
         float temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }

   public static void shuffle(double[] array, int n, int k, RandomStream stream) {
      // @precondition 0 <= k <= n <= a.length.
      if (k < 0 || k > n)
         throw new IllegalArgumentException("k must be   0 <= k <= n");
      for (int i = 0; i < k; i++) {
         // Get random j in {i,...,n-1} and interchange a[i] with a[j].
         int j = stream.nextInt(i, n - 1);
         double temp = array[j];
         array[j] = array[i];
         array[i] = temp;
      }
   }
 
}