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&lt;Integer&gt; elements = Arrays.asList(1, 2, 3);
244     * CombinationGenerator&lt;Integer&gt; combinations = new CombinationGenerator(elements, 2);
245     * for (List&lt;Integer&gt; 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}