package meerkat.mixer.network;

import java.util.Random;

/**
 * Created by Tzlil on 12/17/2015.
 * container for random permutation
 * the permutation is set in the constructor and can't be changed
 */
public class RandomPermutation {
      public final int[] permutation;

    /**
     * constructor
     * @param n permutation size
     * @param random
     */
    public RandomPermutation(int n, Random random) {
        this.permutation = generatePermutation(n,random);
    }

    /**
     * generate random permutation ovver [0,n)
     * @param n permutation size
     * @param random
     * @return permutation
     */
    public static int[] generatePermutation(int n, Random random){
        int[] result = new int[n];

        // initialize and permute in one pass using "inside-out" Fisher-Yates
        for (int i = 0; i < n; ++i) {
            int j = random.nextInt(i+1);

            if (j != i) {
                result[i] = result[j];
            }

            result[j] = i;
        }

        return result;
    }


    /**
     * randomly shuffle an array of elements in-place (using Fisher-Yates)
     * @param perm array of elements to shuffle.
     * @param random
     */
    public static <T> void permute(T[] perm, Random random){
        for (int i = perm.length - 1; i > 0; --i) {
            int j = random.nextInt(i+1);
            T tmp = perm[i];
            perm[i] = perm[j];
            perm[j] = tmp;
        }
    }
}
