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 */
021package org.biojava.nbio.structure.symmetry.utils;
022
023
024
025
026/**
027 *
028 * @author Peter
029 */
030// Changed hasMore to hasNext
031// Added a check in getNext whether there are more elements.
032// http://www.merriampark.com/comb.htm
033// Author: Michael Gilleland, Merriam Park Software
034//The CombinationGenerator Java class systematically generates all combinations of n elements, taken r at a time. The algorithm is described by Kenneth H. Rosen, Discrete Mathematics and Its Applications, 2nd edition (NY: McGraw-Hill, 1991), pp. 284-286.
035//
036//The class is very easy to use. Suppose that you wish to generate all possible three-letter combinations of the letters "a", "b", "c", "d", "e", "f", "g". Put the letters into an array. Keep calling the combination generator's getNext () method until there are no more combinations left. The getNext () method returns an array of integers, which tell you the order in which to arrange your original array of letters. Here is a snippet of code which illustrates how to use the CombinationGenerator class.
037//
038//String[] elements = {"a", "b", "c", "d", "e", "f", "g"};
039//int[] indices;
040//CombinationGenerator x = new CombinationGenerator (elements.length, 3);
041//StringBuffer combination;
042//while (x.hasNext ()) {
043//  combination = new StringBuffer ();
044//  indices = x.getNext ();
045//  for (int i = 0; i < indices.length; i++) {
046//    combination.append (elements[indices[i]]);
047//  }
048//  System.out.println (combination.toString ());
049//}
050//
051//Another example of the usage of the CombinationGenerator is shown below in connection with the Zen Archery problem.
052//
053//Source Code
054//The source code is free for you to use in whatever way you wish.
055
056//--------------------------------------
057// Systematically generate combinations.
058//--------------------------------------
059
060import java.math.BigInteger;
061import java.util.NoSuchElementException;
062
063public class CombinationGenerator {
064
065        private int[] a;
066        private int n;
067        private int r;
068        private BigInteger numLeft;
069        private BigInteger total;
070
071        //------------
072        // Constructor
073        //------------
074
075        public CombinationGenerator(int n, int r) {
076                if (r > n) {
077                        throw new IllegalArgumentException();
078                }
079                if (n < 1) {
080                        throw new IllegalArgumentException();
081                }
082                this.n = n;
083                this.r = r;
084                a = new int[r];
085                BigInteger nFact = getFactorial(n);
086                BigInteger rFact = getFactorial(r);
087                BigInteger nminusrFact = getFactorial(n - r);
088                total = nFact.divide(rFact.multiply(nminusrFact));
089                reset();
090        }
091
092        //------
093        // Reset
094        //------
095
096        public void reset() {
097                for (int i = 0; i < a.length; i++) {
098                        a[i] = i;
099                }
100                numLeft = new BigInteger(total.toString());
101        }
102
103        //------------------------------------------------
104        // Return number of combinations not yet generated
105        //------------------------------------------------
106
107        public BigInteger getNumLeft() {
108                return numLeft;
109        }
110
111        //-----------------------------
112        // Are there more combinations?
113        //-----------------------------
114
115        public boolean hasNext() {
116                return numLeft.compareTo(BigInteger.ZERO) == 1;
117        }
118
119        //------------------------------------
120        // Return total number of combinations
121        //------------------------------------
122
123        public BigInteger getTotal() {
124                return total;
125        }
126
127        //------------------
128        // Compute factorial
129        //------------------
130
131        private static BigInteger getFactorial(int n) {
132                BigInteger fact = BigInteger.ONE;
133                for (int i = n; i > 1; i--) {
134                        fact = fact.multiply(new BigInteger(Integer.toString(i)));
135                }
136                return fact;
137        }
138
139        //--------------------------------------------------------
140        // Generate next combination (algorithm from Rosen p. 286)
141        //--------------------------------------------------------
142
143        public int[] getNext() {
144                if (hasNext()) {
145                        if (numLeft.equals(total)) {
146                                numLeft = numLeft.subtract(BigInteger.ONE);
147                                return a;
148                        }
149
150                        int i = r - 1;
151                        while (a[i] == n - r + i) {
152                                i--;
153                        }
154                        a[i] = a[i] + 1;
155                        for (int j = i + 1; j < r; j++) {
156                                a[j] = a[i] + j - i;
157                        }
158
159                        numLeft = numLeft.subtract(BigInteger.ONE);
160                        return a;
161                } else {
162                        throw new NoSuchElementException();
163                }
164        }
165
166}