001/*
002 *                    BioJava development code
003 *
004 * This code may be freely distributed and modified under the
005 * terms of the GNU Lesser General Public Licence.  This should
006 * be distributed with the code.  If you do not have a copy,
007 * see:
008 *
009 *      http://www.gnu.org/copyleft/lesser.html
010 *
011 * Copyright for this code is held jointly by the individual
012 * authors.  These should be listed in @author doc comments.
013 *
014 * For more information on the BioJava project and its aims,
015 * or to join the biojava-l mailing list, visit the home page
016 * at:
017 *
018 *      http://www.biojava.org/
019 *
020 */
021
022package org.biojava.nbio.structure.symmetry.utils;
023
024import java.math.BigInteger;
025
026/**
027 *
028 * @author Peter
029 */
030public class PermutationGenerator {
031//--------------------------------------
032// Systematically generate permutations.
033//--------------------------------------
034// http://www.merriampark.com/perm.htm // The PermutationGenerator Java class systematically generates permutations. It relies on the fact that any set with n elements can be placed in one-to-one correspondence with the set {1, 2, 3, ..., n}. The algorithm is described by Kenneth H. Rosen, Discrete Mathematics and Its Applications, 2nd edition (NY: McGraw-Hill, 1991), pp. 282-284.
035
036
037        private int[] a;
038        private BigInteger numLeft;
039        private BigInteger total;
040
041        //-----------------------------------------------------------
042        // Constructor. WARNING: Don't make n too large.
043        // Recall that the number of permutations is n!
044        // which can be very large, even when n is as small as 20 --
045        // 20! = 2,432,902,008,176,640,000 and
046        // 21! is too big to fit into a Java long, which is
047        // why we use BigInteger instead.
048        //----------------------------------------------------------
049
050        public PermutationGenerator (int n) {
051                if (n < 1) {
052                        throw new IllegalArgumentException ("Min 1");
053                }
054                a = new int[n];
055                total = getFactorial (n);
056                reset ();
057        }
058
059        //------
060        // Reset
061        //------
062
063        public void reset () {
064                for (int i = 0; i < a.length; i++) {
065                        a[i] = i;
066                }
067                numLeft = new BigInteger (total.toString ());
068        }
069
070        //------------------------------------------------
071        // Return number of permutations not yet generated
072        //------------------------------------------------
073
074        public BigInteger getNumLeft () {
075                return numLeft;
076        }
077
078        //------------------------------------
079        // Return total number of permutations
080        //------------------------------------
081
082        public BigInteger getTotal () {
083                return total;
084        }
085
086        //-----------------------------
087        // Are there more permutations?
088        //-----------------------------
089
090        public boolean hasMore () {
091                return numLeft.compareTo (BigInteger.ZERO) == 1;
092        }
093
094        //------------------
095        // Compute factorial
096        //------------------
097
098        private static BigInteger getFactorial (int n) {
099                BigInteger fact = BigInteger.ONE;
100                for (int i = n; i > 1; i--) {
101                        fact = fact.multiply (new BigInteger (Integer.toString (i)));
102                }
103                return fact;
104        }
105
106        //--------------------------------------------------------
107        // Generate next permutation (algorithm from Rosen p. 284)
108        //--------------------------------------------------------
109
110        public int[] getNext () {
111
112                if (numLeft.equals (total)) {
113                        numLeft = numLeft.subtract (BigInteger.ONE);
114                        return a;
115                }
116
117                int temp;
118
119                // Find largest index j with a[j] < a[j+1]
120
121                int j = a.length - 2;
122                while (a[j] > a[j+1]) {
123                        j--;
124                }
125
126                // Find index k such that a[k] is smallest integer
127                // greater than a[j] to the right of a[j]
128
129                int k = a.length - 1;
130                while (a[j] > a[k]) {
131                        k--;
132                }
133
134                // Interchange a[j] and a[k]
135
136                temp = a[k];
137                a[k] = a[j];
138                a[j] = temp;
139
140                // Put tail end of permutation after jth position in increasing order
141
142                int r = a.length - 1;
143                int s = j + 1;
144
145                while (r > s) {
146                        temp = a[s];
147                        a[s] = a[r];
148                        a[r] = temp;
149                        r--;
150                        s++;
151                }
152
153                numLeft = numLeft.subtract (BigInteger.ONE);
154                return a;
155
156        }
157
158}