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}