1 /*
2 * CombinatoricOperator.java
3 *
4 * Created on 7-mrt-2006
5 *
6 * Copyright (C) 2006 Hendrik Maryns <hendrik@sfs.uni-tuebingen.de>.
7 *
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License
10 * as published by the Free Software Foundation; either version 2
11 * of the License, or (at your option) any later version.
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19 */
20 package combinatorics;
21
22 import java.lang.reflect.Array;
23 import java.util.Collection;
24 import java.util.Iterator;
25
26 /**
27 * A common superclass for all combinatoric operators. Makes use of the
28 * template method pattern to define all others. </p>
29 * <p>Given an array of objects of type T, it returns all results of a certain
30 * combinatoric operation.</p>
31 *
32 * <p>For efficiency, I changed this class to use ints for the counters.
33 * This means that e.g. for permutations, the maximal size of the array is
34 * about 20. If larger arrays are needed, BigInteger should be used
35 * (reintroduced).
36 *
37 * TODO: make simultaneous iteration possible.
38 *
39 * @author <a href="mailto:hendrik.maryns@uni-tuebingen.de">Hendrik Maryns</a>
40 * @param <T>
41 * The type of the objects to operate on.
42 */
43 public abstract class CombinatoricOperator<T> implements Iterator<T[]>,
44 Iterable<T[]> {
45
46 /**
47 * Initialise a new operator, with given elements and size of the arrays
48 * to be returned.
49 *
50 * @param elements
51 * The elements on which this combinatoric operator has to act.
52 * @param r
53 * The size of the arrays to compute.
54 * @pre r should not be smaller than 0.
55 * | 0 <= r
56 * @post The total number of iterations is set to the correct number.
57 * | new.getTotal() == initialiseTotal();
58 * @post The number of variations left is set to the total number.
59 * | new.getNumLeft() == new.getTotal()
60 */
61 protected CombinatoricOperator(final T[] elements, final int r) {
62 assert 0 <= r;
63 this.indices = new int[r];
64 this.elements = elements.clone();
65 this.total = (int)this.initialiseTotal(elements.length, r);
66 this.reset();
67 }
68
69 /**
70 * The elements the operator works upon.
71 */
72 protected T[] elements;
73
74 /**
75 * An integer array backing up the original one to keep track of the
76 * indices.
77 */
78 protected int[] indices;
79
80 /**
81 * Initialise the array of indices. By default, it is initialised with
82 * incrementing integers.
83 */
84 protected void initialiseIndices() {
85 for (int i = 0; i < this.indices.length; i++) {
86 this.indices[i] = i;
87 }
88 }
89
90 /**
91 * The variations still to go.
92 */
93 private int numLeft;
94
95 /**
96 * The total number of variations to be computed.
97 */
98 final private int total;
99
100 /**
101 * Compute the total number of elements to return.
102 *
103 * @param n
104 * The number of elements the operator works on.
105 * @param r
106 * The size of the arrays to return.
107 * @return The total number of elements is always bigger than 0.
108 * | result >= 0
109 */
110 protected abstract double initialiseTotal(int n, int r);
111
112 /**
113 * Reset the iteration.
114 *
115 * @post The number of iterations to go is the same as the total number
116 * of iterations.
117 * | new.getNumLeft() == getTotal()
118 */
119 public void reset() {
120 this.initialiseIndices();
121 this.numLeft = this.total;
122 }
123
124 /**
125 * Return number of variations not yet generated.
126 *
127 * @return Return number of variations not yet generated.
128 */
129 public double getNumLeft() {
130 return this.numLeft;
131 }
132
133 /**
134 * Return the total number of variations.
135 *
136 * @return The factorial of the number of elements divided by the
137 * factorials of the size of the variations and the number of
138 * elements minus the size of the variations.
139 * That is, with n the number of elements and r the size of the
140 * variations: n^r
141 */
142 public double getTotal() {
143 return this.total;
144 }
145
146 /**
147 * Returns <tt>true</tt> if the iteration has more elements. This is the
148 * case if not all n! permutations have been covered.
149 *
150 * @return The number of permutations to go is bigger than zero.
151 * | result == getNumLeft() > 0;
152 * @see java.util.Iterator#hasNext()
153 */
154 public boolean hasNext() {
155 return this.numLeft > 0;
156 }
157
158 /**
159 * Compute the next combination.
160 *
161 * @see java.util.Iterator#next()
162 */
163 public T[] next() {
164 if (this.numLeft != this.total) {
165 this.computeNext();
166 }
167 this.numLeft--;
168 return this.getResult(this.indices);
169 }
170
171 /**
172 * Compute the next array of indices.
173 */
174 protected abstract void computeNext();
175
176 /**
177 * Compute the result, based on the given array of indices.
178 *
179 * @param indexes
180 * An array of indices into the element array.
181 * @return An array consisting of the elements at positions of the given
182 * array.
183 * | result[i] == elements[indexes[i]]
184 */
185 @SuppressWarnings("unchecked")
186 private T[] getResult(final int[] indexes) {
187 final T[] result = (T[]) Array.newInstance(this.elements.getClass()
188 .getComponentType(), indexes.length);
189 for (int i = 0; i < indexes.length; i++) {
190 result[i] = this.elements[indexes[i]];
191 }
192 return result;
193 }
194
195 /**
196 * Not supported.
197 *
198 * @see java.util.Iterator#remove()
199 */
200 public void remove() {
201 throw new UnsupportedOperationException();
202 }
203
204 /**
205 * A combinatoric operator is itself an iterator.
206 *
207 * @return Itself.
208 * | result == this
209 * @see java.lang.Iterable#iterator()
210 */
211 public Iterator<T[]> iterator() {
212 return this;
213 }
214
215 /**
216 * Compute the factorial of n.
217 */
218 public static double factorial(final int n) {
219 double fact = 1;
220 for (int i = n; i > 1; i--) {
221 fact = fact*i;
222 }
223 return fact;
224 }
225
226 /**
227 * Return an array that contains all the elements of the given collection.
228 * Convenience method for clients of the class that have to transform
229 * collections.
230 *
231 * @param coll
232 * The collection to transform.
233 * @param type
234 * The type of the elements in the collection. Unfortunately, this
235 * method argument is necessary to create an array of the
236 * appropriate type. Blame Java generics.
237 * @return An array containing all elements of the collection.
238 * | for each element in result
239 * | coll.contains(element)
240 */
241 @SuppressWarnings("unchecked")
242 public static <T> T[] collectionToArray(final Collection<T> coll, final Class<T> type) {
243 T[] result = (T[]) Array.newInstance(type, coll.size());
244 result = coll.toArray(result);
245 return result;
246 }
247
248 }