package Sequenic.T2.Engines;

import java.math.BigInteger;

/**
 * The PermitationGenerator by Michael Gilleland. See <a href="http://www.merriampark.com/perm.htm">
 * http://www.merriampark.com/perm.htm </a>.
 * 
 * <p>This implements a generator producing all permutations of n elements. 
 * The algorithm is described by Kenneth H. Rosen, in
 * Discrete Mathematics and Its Applications, 2nd edition, McGraw-Hill, 1991, 
 * pp. 282-284.
 * 
 * @author Michael Gilleland, adapted by Wishnu Prasetya
 */
public class PermutationGenerator extends AbstractCombinationGenerator {

    //-----------------------------------------------------------
    // Constructor. WARNING: Don't make n too large.
    // Recall that the number of permutations is n!
    // which can be very large, even when n is as small as 20 --
    // 20! = 2,432,902,008,176,640,000 and
    // 21! is too big to fit into a Java long, which is
    // why we use BigInteger instead.
    //----------------------------------------------------------
    public PermutationGenerator(int n) {
        if (n < 1) {
            throw new IllegalArgumentException("Min 1");
        }
        a = new int[n];
        long total = getFactorial(n);
        if (total <= (long) Integer.MAX_VALUE) this.total = (int) total ;
        else throw new Error("The number of combinations is too large.") ;
        reset();
    }

    //------
    // Reset
    //------
    @Override
    public void reset() {
        for (int i = 0; i < a.length; i++) {
            a[i] = i;
        }
        numLeft = total ;
    }


    /**
     * Generate next permutation (algorithm from Rosen p. 284)
     */
    @Override
    public void  getNext(int[] res) {

    	assert res.length == a.length ;
    	
        if (numLeft == total) {
            numLeft-- ;
            copyArray(a,res) ;
            return ;
        }

        int temp;

        // Find largest index j with a[j] < a[j+1]

        int j = a.length - 2;
        while (a[j] > a[j + 1]) {
            j--;
        }

        // Find index k such that a[k] is smallest integer
        // greater than a[j] to the right of a[j]

        int k = a.length - 1;
        while (a[j] > a[k]) {
            k--;
        }

        // Interchange a[j] and a[k]

        temp = a[k];
        a[k] = a[j];
        a[j] = temp;

        // Put tail end of permutation after jth position in increasing order

        int r = a.length - 1;
        int s = j + 1;

        while (r > s) {
            temp = a[s];
            a[s] = a[r];
            a[r] = temp;
            r--;
            s++;
        }

        numLeft-- ;
        copyArray(a,res) ;
        return ;

    }

}