001// ============================================================================ 002// Copyright 2006-2012 Daniel W. Dyer 003// 004// Licensed under the Apache License, Version 2.0 (the "License"); 005// you may not use this file except in compliance with the License. 006// You may obtain a copy of the License at 007// 008// http://www.apache.org/licenses/LICENSE-2.0 009// 010// Unless required by applicable law or agreed to in writing, software 011// distributed under the License is distributed on an "AS IS" BASIS, 012// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013// See the License for the specific language governing permissions and 014// limitations under the License. 015// ============================================================================ 016package squidpony.squidmath; 017 018import java.io.Serializable; 019import java.math.BigInteger; 020import java.util.ArrayList; 021import java.util.Collection; 022import java.util.Iterator; 023import java.util.List; 024 025/** 026 * Combination generator for generating all combinations of a given size from 027 * the specified set of elements. For performance reasons, this implementation 028 * is restricted to operating with set sizes and combination lengths that produce 029 * no more than 2^63 different combinations. 030 * <br> 031 * Originally part of the <a href="http://maths.uncommons.org/">Uncommon Maths software package</a>. 032 * @param <T> The type of element that the combinations are made from. 033 * @author Daniel Dyer (modified from the original version written by Michael 034 * Gilleland of Merriam Park Software - 035 * <a href="http://www.merriampark.com/perm.htm">http://www.merriampark.com/comb.htm</a>). 036 * @see PermutationGenerator 037 */ 038public class CombinationGenerator<T> implements Iterable<List<T>>, Serializable 039{ 040 private static final long serialVersionUID = 5998145341506278361L; 041 042 private final T[] elements; 043 private final int[] combinationIndices; 044 private long remainingCombinations; 045 private long totalCombinations; 046 047 private CombinationGenerator() 048 { 049 elements = null; 050 combinationIndices = null; 051 }; 052 /** 053 * Create a combination generator that generates all combinations of 054 * a specified length from the given set. 055 * @param elements The set from which to generate combinations; will be used directly (not copied) 056 * @param combinationLength The length of the combinations to be generated. 057 */ 058 public CombinationGenerator(T[] elements, 059 int combinationLength) 060 { 061 if (combinationLength > elements.length) 062 { 063 throw new IllegalArgumentException("Combination length cannot be greater than set size."); 064 } 065 066 this.elements = elements; 067 this.combinationIndices = new int[combinationLength]; 068 069 BigInteger sizeFactorial = MathExtras.bigFactorial(elements.length); 070 BigInteger lengthFactorial = MathExtras.bigFactorial(combinationLength); 071 BigInteger differenceFactorial = MathExtras.bigFactorial(elements.length - combinationLength); 072 BigInteger total = sizeFactorial.divide(differenceFactorial.multiply(lengthFactorial)); 073 074 if (total.compareTo(BigInteger.valueOf(Long.MAX_VALUE)) > 0) 075 { 076 throw new IllegalArgumentException("Total number of combinations must not be more than 2^63."); 077 } 078 079 totalCombinations = total.longValue(); 080 reset(); 081 } 082 083 084 /** 085 * Create a combination generator that generates all combinations of 086 * a specified length from the given set. 087 * @param elements The set from which to generate combinations. 088 * @param combinationLength The length of the combinations to be generated. 089 * @param filler An array of T with the same length as elements; needed because GWT can't create a generic array. 090 */ 091 @SuppressWarnings("unchecked") 092 public CombinationGenerator(Collection<T> elements, 093 int combinationLength, 094 T[] filler) 095 { 096 this(elements.toArray(filler), combinationLength); 097 } 098 099 100 /** 101 * Reset the combination generator. 102 */ 103 public final void reset() 104 { 105 for (int i = 0; i < combinationIndices.length; i++) 106 { 107 combinationIndices[i] = i; 108 } 109 remainingCombinations = totalCombinations; 110 } 111 112 113 /** 114 * @return The number of combinations not yet generated. 115 */ 116 public long getRemainingCombinations() 117 { 118 return remainingCombinations; 119 } 120 121 122 /** 123 * Are there more combinations? 124 * @return true if there are more combinations available, false otherwise. 125 */ 126 public boolean hasMore() 127 { 128 return remainingCombinations > 0; 129 } 130 131 132 /** 133 * @return The total number of combinations. 134 */ 135 public long getTotalCombinations() 136 { 137 return totalCombinations; 138 } 139 140 141 /** 142 * Generate the next combination and return an array containing 143 * the appropriate elements. This overloaded method allows the caller 144 * to provide an array that will be used and returned. 145 * The purpose of this is to improve performance when iterating over 146 * combinations. This method allows a single array instance to be reused. 147 * @param destination Provides an array to use to create the 148 * combination. The specified array must be the same length as a 149 * combination. 150 * @return The provided array now containing the elements of the combination. 151 */ 152 public T[] nextCombinationAsArray(T[] destination) 153 { 154 if (destination.length != combinationIndices.length) 155 { 156 throw new IllegalArgumentException("Destination array must be the same length as combinations."); 157 } 158 generateNextCombinationIndices(); 159 for (int i = 0; i < combinationIndices.length; i++) 160 { 161 destination[i] = elements[combinationIndices[i]]; 162 } 163 return destination; 164 } 165 166 167 /** 168 * Generate the next combination and return a list containing the 169 * appropriate elements. 170 * @see #nextCombinationAsList(List) 171 * @return A list containing the elements that make up the next combination. 172 */ 173 public List<T> nextCombinationAsList() 174 { 175 return nextCombinationAsList(new ArrayList<T>(elements.length)); 176 } 177 178 179 /** 180 * Generate the next combination and return a list containing 181 * the appropriate elements. This overloaded method allows the caller 182 * to provide a list that will be used and returned. 183 * The purpose of this is to improve performance when iterating over 184 * combinations. If the {@link #nextCombinationAsList()} method is 185 * used it will create a new list every time. When iterating over 186 * combinations this will result in lots of short-lived objects that 187 * have to be garbage collected. This method allows a single list 188 * instance to be reused in such circumstances. 189 * @param destination Provides a list to use to create the 190 * combination. 191 * @return The provided list now containing the elements of the combination. 192 */ 193 public List<T> nextCombinationAsList(List<T> destination) 194 { 195 generateNextCombinationIndices(); 196 // Generate actual combination. 197 destination.clear(); 198 for (int i : combinationIndices) 199 { 200 destination.add(elements[i]); 201 } 202 return destination; 203 } 204 205 206 207 /** 208 * Generate the indices into the elements array for the next combination. The 209 * algorithm is from Kenneth H. Rosen, Discrete Mathematics and Its Applications, 210 * 2nd edition (NY: McGraw-Hill, 1991), p. 286. 211 */ 212 private void generateNextCombinationIndices() 213 { 214 if (remainingCombinations == 0) 215 { 216 throw new IllegalStateException("There are no combinations remaining. " + 217 "Generator must have reset() called to continue."); 218 } 219 else if (remainingCombinations < totalCombinations) 220 { 221 int i = combinationIndices.length - 1; 222 while (combinationIndices[i] == elements.length - combinationIndices.length + i) 223 { 224 i--; 225 } 226 ++combinationIndices[i]; 227 for (int j = i + 1; j < combinationIndices.length; j++) 228 { 229 combinationIndices[j] = combinationIndices[i] + j - i; 230 } 231 } 232 --remainingCombinations; 233 } 234 235 236 /** 237 * <p>Provides a read-only iterator for iterating over the combinations 238 * generated by this object. This method is the implementation of the 239 * {@link Iterable} interface that permits instances of this class to be 240 * used with the new-style for loop.</p> 241 * <p>For example:</p> 242 * <pre> 243 * List<Integer> elements = Arrays.asList(1, 2, 3); 244 * CombinationGenerator<Integer> combinations = new CombinationGenerator(elements, 2); 245 * for (List<Integer> c : combinations) 246 * { 247 * // Do something with each combination. 248 * } 249 * </pre> 250 * @return An iterator. 251 * @since 1.1 252 */ 253 public Iterator<List<T>> iterator() 254 { 255 return new Iterator<List<T>>() 256 { 257 public boolean hasNext() 258 { 259 return hasMore(); 260 } 261 262 263 public List<T> next() 264 { 265 return nextCombinationAsList(); 266 } 267 268 269 public void remove() 270 { 271 throw new UnsupportedOperationException("Iterator does not support removal."); 272 } 273 }; 274 } 275 276}