integerpermutationiter.java

使用Java开发的图论算法的包

/* ==========================================
 * JGraphT : a free Java graph-theory library
 * ==========================================
 *
 * Project Info:  http://jgrapht.sourceforge.net/
 * Project Creator:  Barak Naveh (http://sourceforge.net/users/barak_naveh)
 *
 * (C) Copyright 2003-2007, by Barak Naveh and Contributors.
 *
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 *
 * This library 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 Lesser General Public
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc.,
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
 */
/* -----------------
 * IntegerPermutationIter.java
 * -----------------
 * (C) Copyright 2005-2007, by Assaf Lehr and Contributors.
 *
 * Original Author:  Assaf Lehr
 * Contributor(s):   -
 *
 * $Id: IntegerPermutationIter.java 568 2007-09-30 00:12:18Z perfecthash $
 *
 * Changes
 * -------
 */
package org.jgrapht.experimental.permutation;

import java.util.*;


/**
 * Iterates through permutations of N elements.
 * <li>use getNext() to get the next permutation order, for example(N=4):
 * perm0=[1,2,3,4] perm1=[1,2,4,3] perm2=[1,3,2,4] .
 * <li>use hasNext() or verify by counter<getTotalNumberOfPermutations () that
 * you do not overflow the max number. RunTimeException will be thrown if you
 * do. Getting the next permutation is done in O(N) Note: This class is not
 * thread safe.
 *
 * @author Assaf
 * @since May 20, 2005
 */
public class IntegerPermutationIter
    implements Iterator,
        ArrayPermutationsIter
{
    //~ Instance fields --------------------------------------------------------

    private int [] Value;
    private int N;
    private long permutationCounter;
    private boolean endWasReached = false;
    private boolean wasNextValueCalculatedAlready = false;

    /**
     * Will hold the current value. Will be changed only by getNext()
     */
    private int [] currentValueBackup;

    //~ Constructors -----------------------------------------------------------

    /**
     * Creates an array of size N with elements 1,2,...,n-1 Useful for
     * describing regular permutations. See IntegerPermutationIter(int[] array)
     * for the other kind of permutations; efficency of initiation is O(N)
     *
     * @param N
     */
    public IntegerPermutationIter(int N)
    {
        int [] newArray = new int[N];

        // fill the array with 1,2,3...
        for (int i = 0; i < newArray.length; i++) {
            newArray[i] = i;
        }
        init(newArray);
    }

    /**
     * Uses a predefined array (sorted), for example: [3,1,1,2,1]-->[1,1,1,2,3];
     * note that there are much less than 5! premutations here, because of the
     * repetitive 1s.
     *
     * @param array creates a copy of it (so sort / later changes will not
     * matter)
     */
    public IntegerPermutationIter(int [] array)
    {
        int [] newArray = new int[array.length];
        System.arraycopy(array, 0, newArray, 0, array.length);
        Arrays.sort(newArray);
        init(newArray);
    }

    //~ Methods ----------------------------------------------------------------

    private void init(int [] array)
    {
        this.N = array.length;
        this.Value = array;
        this.currentValueBackup = this.Value;
        permutationCounter = 0;
    }

    /**
     * Swaps by array indexes
     *
     * @param i
     * @param j
     */
    private void swap(int i, int j)
    {
        int temp = this.Value[i];
        this.Value[i] = this.Value[j];
        this.Value[j] = temp;
    }

    private int [] arrayClone(int [] sourceArray)
    {
        int [] destArray = new int[sourceArray.length];
        System.arraycopy(sourceArray, 0, destArray, 0, sourceArray.length);
        return destArray;
    }

    private int [] getNextStartingWith2()
    {
        permutationCounter++;
        int i = N - 1;

        if (i <= 0) // may happen only on N<=1

        {
            this.endWasReached = true;
            return null;
        }

        /** while (Value[i-1] >= Value[i])
          {
          i = i-1;
          }*/
        while (Value[i - 1] >= Value[i]) {
            i = i - 1;
            if (i == 0) {
                this.endWasReached = true;
                return null;
            }
        }

        int j = N;

        while (Value[j - 1] <= Value[i - 1]) {
            j = j - 1;
        }

        swap(i - 1, j - 1); // swap values at positions (i-1) and (j-1)

        i++;
        j = N;

        while (i < j) {
            swap(i - 1, j - 1);
            i++;
            j--;
        }
        return this.Value;
    }

    /**
     * Efficiency: O(N) implementation, try to take the next!
     */
    public boolean hasNext()
    {
        if ((this.permutationCounter == 0)
            || (this.wasNextValueCalculatedAlready))
        {
            return true;
        } else if (this.endWasReached) {
            return false;
        }

        boolean result = true;
        // calculate the next value into this.value  save the current result. in
        // the end swap the arrays there is no way to know when to stop , but
        // the out-of-bound
        /*  try
         *  {
         *      this.wasNextValueCalculatedAlready=true;
         *      getNextStartingWith2();
         *  }
         *  catch (ArrayIndexOutOfBoundsException outOfBoundException)
         *  {
         *      endWasReached=true;
         *      result=false;
         *  }*/

        getNextStartingWith2();
        this.wasNextValueCalculatedAlready = true;
        if (endWasReached) {
            return false;
        }

        //////////////////////////////
        return result;
    }

    public Object next()
    {
        return getNext();
    }

    /**
     * Facade. use it with getNext. efficency: O(N)
     *
     * @return a new Array with the permutatation order. for example:
     * perm0=[1,2,3,4] perm1=[1,2,4,3] perm2=[1,3,2,4]
     */
    public int [] getNext()
    {
        if (!hasNext()) {
            throw new RuntimeException(
                "IntegerPermutationIter exceeds the total number of permutaions."
                + " Suggestion: do a check with hasNext() , or count till getTotalNumberOfPermutations"
                + " before using getNext()");
        }

        // if it is the first one , return original
        int [] internalArray;
        if (this.permutationCounter == 0) {
            this.permutationCounter++;
            internalArray = this.Value;
        } else {
            // if hasNext() has precaclulated it , take this value.
            if (this.wasNextValueCalculatedAlready) {
                internalArray = this.Value;
                this.wasNextValueCalculatedAlready = false;
            } else {
                internalArray = getNextStartingWith2();
                if (this.endWasReached) {
                    return null;
                }
            }
        }
        this.currentValueBackup = arrayClone(internalArray);
        return arrayClone(internalArray);
    }

    public int [] getCurrent()
    {
        return arrayClone(this.currentValueBackup);
    }

    /**
     * Utility method to convert the array into a string examples: [] [0]
     * [0,1][1,0]
     *
     * @param array
     */
    public String toString(int [] array)
    {
        if (array.length <= 0) {
            return "[]";
        }
        StringBuffer stBuffer = new StringBuffer("[");
        for (int i = 0; i < (array.length - 1); i++) {
            stBuffer.append(array[i]).append(",");
        }
        stBuffer.append(array[array.length - 1]).append("]");
        return stBuffer.toString();
    }

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

    /* (non-Javadoc)
     * @see ArrayPermutationsIter#nextPermutation()
     */
    public int [] nextPermutation()
    {
        return (int []) next();
    }

    /* (non-Javadoc)
     * @see ArrayPermutationsIter#hasNextPermutaions()
     */
    public boolean hasNextPermutaions()
    {
        return hasNext();
    }
}

// End IntegerPermutationIter.java