/*
 * CombinatoricOperator.java
 *
 * Created on 7-mrt-2006
 *
 * Copyright (C) 2006 Hendrik Maryns <hendrik@sfs.uni-tuebingen.de>.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */
package de.uni_tuebingen.sfb.macke.utilities;

import static java.math.BigInteger.ONE;
import static java.math.BigInteger.ZERO;

import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.Iterator;

/**
 * A common superclass for all combinatoric operators.  Makes use of the
 * template method pattern to define all others.
 *
 * @author <a href="mailto:hendrik.maryns@uni-tuebingen.de">Hendrik  Maryns</a>
 */
public abstract class CombinatoricOperator<T> implements Iterator<T[]>,
                Iterable<T[]> {

        /**
         * Initialise a new operator, with given elements and size of the arrays
         * to be returned.
         *
         * @param elements
         *       The elements on which this combinatoric operator has to act.
         * @param r
         *       The size of the arrays to compute.
         * @pre    r should not be smaller than 0.
         *     | 0 <= r
         * @post   The total number of iterations is set to the correct number.
         *     | new.getTotal() == initialiseTotal();
         * @post  The number of variations left is set to the total number.
         *     | new.getNumLeft() == new.getTotal()
         */
        protected CombinatoricOperator(T[] elements, int r) {
                assert 0 <= r;
                indices = new int[r];
                this.elements = elements.clone();
                total = initialiseTotal(elements.length, r);
                reset();
        }

        /**
         * The elements the operator works upon.
         */
        protected T[] elements;

        /**
         * An integer array backing up the original one to keep track of the
         * indices.
         */
        protected int[] indices;

        /**
         * Initialise the array of indices.  By default, it is initialised with
         * incrementing integers.
         */
        protected void initialiseIndices() {
                for (int i = 0; i < indices.length; i++) {
                        indices[i] = i;
                }
        }

        /**
         * The variations still to go.
         */
        private BigInteger numLeft;

        /**
         * The total number of variations to be computed.
         */
        private BigInteger total;

        /**
         * Compute the total number of elements to return.
         *
         * @param n
         *                      The number of elements the operator works on.
         * @param r
         *                      The size of the arrays to return.
         * @return      The total number of elements is always bigger than 0.
         *              | result >= 0
         */
        protected abstract BigInteger initialiseTotal(int n, int r);

        /**
         * Reset the iteration.
         *
         * @post        The number of iterations to go is the same as the total number
         *                      of iterations.
         *              | new.getNumLeft() == getTotal()
         */
        public void reset() {
                initialiseIndices();
                numLeft = total;
        }

        /**
         * Return number of variations not yet generated.
         */
        public BigInteger getNumLeft() {
                return numLeft;
        }

        /**
         * Return the total number of variations.
         *
         * @return  The factorial of the number of elements divided by the
         *       factorials of the size of the variations and the number of
         *       elements minus the size of the variations.
         *       That is, with the number of elements = n and the size of the
         *       variations = r: n^r
         */
        public BigInteger getTotal() {
                return total;
        }

        /**
         * Returns <tt>true</tt> if the iteration has more elements.  This is the
         * case if not all n! permutations have been covered.
         *
         * @return  The number of permutations to go is bigger than zero.
         *     | result == getNumLeft().compareTo(BigInteger.ZERO) > 0;
         * @see java.util.Iterator#hasNext()
         */
        public boolean hasNext() {
                return numLeft.compareTo(ZERO) == 1;
        }

        /**
         * Compute the next combination.
         *
         * @see java.util.Iterator#next()
         */
        public T[] next() {
                if (!numLeft.equals(total)) {
                        computeNext();
                }
                numLeft = numLeft.subtract(ONE);
                return getResult(indices);
        }

        /**
         * Compute the next array of indices.
         */
        protected abstract void computeNext();

        /**
         * Compute the result, based on the given array of indices.
         *
         * @param indexes
         *       An array of indices into the element array.
         * @return  An array consisting of the elements at positions of the given
         *       array.
         *     | result[i] == elements[indexes[i]]
         */
        @SuppressWarnings("unchecked")
        private T[] getResult(int[] indexes) {
                T[] result = (T[]) Array.newInstance(elements.getClass()
                                .getComponentType(), indexes.length);
                for (int i = 0; i < result.length; i++) {
                        result[i] = elements[indexes[i]];
                }
                return result;
        }

        /**
         * Not supported.
         *
         * @see java.util.Iterator#remove()
         */
        public void remove() {
                throw new UnsupportedOperationException();
        }

        /**
         * A combinatoric operator is itself an iterator.
         *
         * @return  Itself.
         *     | result == this
         * @see java.lang.Iterable#iterator()
         */
        public Iterator<T[]> iterator() {
                return this;
        }

        /**
         * Compute the factorial of n.
         */
        public static BigInteger factorial(int n) {
                BigInteger fact = ONE;
                for (int i = n; i > 1; i--) {
                        fact = fact.multiply(BigInteger.valueOf(i));
                }
                return fact;
        }
}

/*
 * Combinator.java
 *
 * Created on 3-mrt-2006, based on CombinationGenerator from Michael  Gilleland.
 *
 * Copyright (C) 2006 Hendrik Maryns <hendrik@sfs.uni-tuebingen.de>.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */
package de.uni_tuebingen.sfb.macke.utilities;

import java.math.BigInteger;

/**
 * A class that sequentially returns all combinations of a certain  number out of
 * an array of given elements.  Thanks to Michael Gillegand for the base
 * implementation: {@link http://www.merriampark.com/comb.htm}
 *
 * @author <a href="mailto:hendrik.maryns@uni-tuebingen.de">Hendrik Maryns</a>
 * @param <T>  The type of the elements of which combinations are to be
 *         returned.
 */
public class Combinator<T> extends CombinatoricOperator<T> {

        /**
         * Initialise a new Combinator, with given elements and size of the arrays
         * to be returned.
         *
         * @param elements
         *       The elements of which combinations have to be computed.
         * @param r
         *       The size of the combinations to compute.
         * @pre    r should not be greater than the length of the elements, and
         *       not smaller than 0.
         *     | 0 <= r <= elements.length
         * @post        The total number of iterations is set to the factorial of the
         *                      number of elements divided by the factorials of the size of the
         *                      combinations and the number of elements minus the size of the
         *                      combinations.  That is, with the number of elements = n and the
         *                      size of the combinations = r:
         *                      n                n!
         *                       (     )  =  ---------
         *                      r         (n-r)!r!
         *     | new.getTotal() == factorial(elements.length).divide(
         *     |  factorial(r).multiply(factorial(elements.length-r))
         * @post  The number of combinations left is set to the total number.
         *     | new.getNumLeft() == new.getTotal()
         */
        public Combinator(T[] elements, int r) {
                super(elements, r);
                assert r <= elements.length;
        }

        /**
         * Compute the total number of elements to return.
         *
         * @return  The factorial of the number of elements divided by the
         *       factorials of the size of the combinations and the number of
         *       elements minus the size of the combinations.
         *       That is, with the number of elements = n and the size of the
         *       combinations = r:
         *          n            n!
         *       (     )  =  ---------
         *          r         (n-r)!r!
         * @see CombinatoricOperator#initialiseTotal(int, int)
         */
        @Override
        protected BigInteger initialiseTotal(int n, int r) {
                BigInteger nFact = factorial(n);
                BigInteger rFact = factorial(r);
                BigInteger nminusrFact = factorial(n - r);
                return nFact.divide(rFact.multiply(nminusrFact));
        }

        /**
         * Compute the next array of indices.
         *
         * @see CombinatoricOperator#computeNext()
         */
        @Override
        protected void computeNext() {
                int r = indices.length;
                int i = r - 1;
                int n = elements.length;
                while (indices[i] == n - r + i) {
                        i--;
                }
                indices[i] = indices[i] + 1;
                for (int j = i + 1; j < r; j++) {
                        indices[j] = indices[i] + j - i;
                }
                // TODO: understand this.
        }

}

/*
 * Permuter.java
 *
 * Created on 3-mar-2006, based on Permutations from Tim Tyler.
 *
 * Copyright (C) 2005 Hendrik Maryns <hendrik@sfs.uni-tuebingen.de>.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */
package de.uni_tuebingen.sfb.macke.utilities;

import java.math.BigInteger;

/**
 * A class that permutes a given array of elements.  It is an iterator that
 * returns all permutations, successively.  Thanks to Tim Tyler for the
 * original implementation {@link http://mandala.co.uk/permutations/}.
 *
 * @author <a href="mailto:hendrik.maryns@uni-tuebingen.de">Hendrik  Maryns</a>
 * @param <T>  The type of the array to be permuted.
 */
public class Permuter<T> extends CombinatoricOperator<T> {

        /**
         * Initialise a new permuter, with given array of elements to permute.
         *
         * @param elements
         *       The elements to permute.
         * @post  The total number is set to the factorial of the number of
         *       elements.
         *     | new.getTotal() == factorial(elements.length)
         * @post  The number of permutations left is set to the total number.
         *     | new.getNumLeft() == new.getTotal()
         */
        public Permuter(T[] elements) {
                super(elements, elements.length);
        }

        /**
         * Compute the total number of elements to return.
         *
         * @return      The factorial of the number of elements.
         *              | result == factorial(n)
         * @see CombinatoricOperator#initialiseTotal(int, int)
         */
        @Override
        protected BigInteger initialiseTotal(int n, int r) {
                return factorial(n);
        }

        /**
         * Compute the next array of indices.
         *
         * @see CombinatoricOperator#computeNext()
         */
        @Override
        protected void computeNext() {
                // find the rightmost element that is smaller than the element at its right
                int i = indices.length - 1;
                while (indices[i - 1] >= indices[i])
                        i = i - 1;
                // find the rightmost element that is bigger then the other one
                int j = indices.length;
                while (indices[j - 1] <= indices[i - 1])
                        j = j - 1;
                // swap them (always is i < j)
                swap(i - 1, j - 1);
                // now the elements at the right of i
                // are in descending order, so  reverse them all
                i++;
                j = indices.length;
                while (i < j) {
                        swap(i - 1, j - 1);
                        i++;
                        j--;
                }
                // TODO: try other algorithms,
                // see http://www.cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml
        }

        /**
         * Swap the elements at positions a and b, both from the index array and
         * from the element array.
         *
         * @param       a, b
         *       The indices of the elements to be swapped.
         * @post        The elements at indices a and b of the array of indices are
         *                      swapped.
         *     | new.indexes[a] = indexes[b]
         *     | new.indexes[b] = indexes[a]
         */
        private void swap(int a, int b) {
                int temp = indices[a];
                indices[a] = indices[b];
                indices[b] = temp;
        }

}

/*
 * VariatorWithRepetition.java
 *
 * Created on 7-mrt-2006
 *
 * Copyright (C) 2006 Hendrik Maryns <hendrik@sfs.uni-tuebingen.de>.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */
package de.uni_tuebingen.sfb.macke.utilities;

import java.math.BigInteger;
import java.util.Arrays;

/**
 * A class that sequentially returns all variations with repetition of a  certain
 * number out of an array of given elements.
 *
 * @author <a href="mailto:hendrik.maryns@uni-tuebingen.de">Hendrik Maryns</a>
 * @param <T>  The type of the elements of which variations are to be
 *         returned.
 */
public class VariatorWithRepetition<T> extends CombinatoricOperator<T> {

        /**
         * Initialise a new variator, with given elements and size of the arrays
         * to be returned.
         *
         * @param elements
         *              The elements of which variations have to be computed.
         * @param r
         *              The size of the variations to compute.
         * @pre         r should not be smaller than 0.
         *     | 0 <= r
         * @post        The total number of iterations is set to the number of elements
         *                      to the rth power.
         *     | new.getTotal() == BigInteger.valueOf(elements.length).pow(r)
         * @post  The number of variations left is set to the total number.
         *     | new.getNumLeft() == new.getTotal()
         */
        public VariatorWithRepetition(T[] elements, int r) {
                super(elements, r);
        }

        /**
         * Initialise the array of indices.  For variations with repetition, it
         * needs to be initialised with all 0s
         */
        @Override
        protected void initialiseIndices() {
                Arrays.fill(indices, 0);
        }

        /**
         * Compute the total number of elements to return.
         *
         * @see CombinatoricOperator#initialiseTotal()
         */
        @Override
        protected BigInteger initialiseTotal(int n, int r) {
                return BigInteger.valueOf(n).pow(r);
        }

        /**
         * Compute the next array of indices.
         *
         * @see CombinatoricOperator#computeNext()
         */
        @Override
        protected void computeNext() {
                int i = indices.length - 1;
                int n = elements.length;
                while (++indices[i] == n && i > 0) {
                        indices[i--] = 0;
                }
        }

}

package de.uni_tuebingen.sfb.macke;
/*
 * PermuterTest.java
 *
 * Created on 3-mrt-2006
 *
 * Copyright (C) 2006 Hendrik Maryns <hendrik@sfs.uni-tuebingen.de>.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */

import de.uni_tuebingen.sfb.macke.utilities.*;

import java.util.Arrays;

/**
 * A class for testing the combinatoric operators.
 *
 * @author <a href="mailto:hendrik.maryns@uni-tuebingen.de">Hendrik Maryns</a>
 */
public class PermuterTest {

        /**
         *
         *
         * @param args
         */
        public static void main(String args[]) {
                final Integer[] data = new Integer[3];
                for (int i = 0; i < data.length; i++) {
                        data[i] = i;
                }
                for (Integer[] variation : new Permuter<Integer>(data)) {
                        System.out.println(Arrays.toString(variation));
                }
                System.out.println();
                for (int i = 0; i <= data.length; i++) {
                        for (Integer[] combination : new Combinator<Integer>(data, i)) {
                                System.out.println(Arrays.toString(combination));
                        }
                }
                System.out.println();
                for (int i = 0; i <= data.length; i++) {
                        for (Integer[] variation : new VariatorWithRepetition<Integer>(data,i)) {
                                System.out.println(Arrays.toString(variation));
                        }
                }
        }

}