1 /*
2 * CartesianProduct.java
3 *
4 * Created on 8-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.Arrays;
24 import java.util.Iterator;
25
26 /**
27 * A class that sequentially returns the cartesian product of sets, represented
28 * as a two-dimensional array.
29 *
30 * TODO: incorporate this into my CombinatoricOperator frame.
31 *
32 * @author <a href="mailto:hendrik.maryns@uni-tuebingen.de">Hendrik Maryns</a>
33 */
34 public class CartesianProduct<T> implements Iterator<T[]>, Iterable<T[]> {
35
36 /**
37 * Initialise a new operator, with given elements and size of the arrays
38 * to be returned.
39 *
40 * @param elements
41 * The elements on which this combinatoric operator has to act.
42 * @post The total number of iterations is set to the product of the
43 * lengths of all subarrays.
44 * | let sum = BigInteger.ONE
45 * | for 0 <= i < elements.length
46 * | sum.multiply(elements[i].length)
47 * | new.getTotal() == sum
48 * @post The number of variations left is set to the total number.
49 * | new.getNumLeft() == new.getTotal()
50 */
51 public CartesianProduct(final T[][] elements) {
52 this.elements = elements.clone();
53 this.indices = new int[elements.length];
54 this.total = this.initialiseTotal();
55 this.reset();
56 }
57
58 /**
59 * The elements the operator works upon.
60 */
61 protected T[][] elements;
62
63 /**
64 * An integer array backing up the original one to keep track of the
65 * indices.
66 */
67 protected int[] indices;
68
69 /**
70 * Initialise the array of indices. By default, it is initialised with
71 * incrementing integers.
72 */
73 protected void initialiseIndices() {
74 Arrays.fill(this.indices, 0);
75 }
76
77 /**
78 * The variations still to go.
79 */
80 private int numLeft;
81
82 /**
83 * The total number of variations to be computed.
84 */
85 final private int total;
86
87 /**
88 * Compute the total number of elements to return.
89 *
90 * @param n
91 * The number of elements the operator works on.
92 * @param r
93 * The size of the arrays to return.
94 * @return The total number of elements is always bigger than 0.
95 * | result >= 0
96 */
97 protected int initialiseTotal() {
98 int result = 1;
99 for (final T[] set: this.elements) {
100 result *= set.length;
101 }
102 return result;
103 }
104
105 /**
106 * Reset the iteration.
107 *
108 * @post The number of iterations to go is the same as the total number
109 * of iterations.
110 * | new.getNumLeft() == getTotal()
111 */
112 public void reset() {
113 this.initialiseIndices();
114 this.numLeft = this.total;
115 }
116
117 /**
118 * Return number of variations not yet generated.
119 */
120 public int getNumLeft() {
121 return this.numLeft;
122 }
123
124 /**
125 * Return the total number of variations.
126 *
127 * @return The factorial of the number of elements divided by the
128 * factorials of the size of the variations and the number of
129 * elements minus the size of the variations.
130 * That is, with the number of elements = n and the size of the
131 * variations = r: n^r
132 */
133 public int getTotal() {
134 return this.total;
135 }
136
137 /**
138 * Returns <tt>true</tt> if the iteration has more elements. This is the
139 * case if not all n! permutations have been covered.
140 *
141 * @return The number of permutations to go is bigger than zero.
142 * | result == getNumLeft().compareTo(BigInteger.ZERO) > 0;
143 * @see java.util.Iterator#hasNext()
144 */
145 public boolean hasNext() {
146 return this.numLeft > 0;
147 }
148
149 /**
150 * Compute the next combination.
151 *
152 * @see java.util.Iterator#next()
153 */
154 public T[] next() {
155 if (this.numLeft != this.total) {
156 this.computeNext();
157 }
158 this.numLeft--;
159 return this.getResult(this.indices);
160 }
161
162 /**
163 * Compute the next array of indices.
164 */
165 protected void computeNext() {
166 int i = this.indices.length -1 ;
167 while (++this.indices[i] == this.elements[i].length && i > 0) {
168 this.indices[i--] = 0;
169 }
170 }
171
172 /**
173 * Compute the result, based on the given array of indices.
174 *
175 * @param indexes
176 * An array of indices into the element array.
177 * @return An array consisting of the elements at positions of the given
178 * array.
179 * | result[i] == elements[indexes[i]]
180 */
181 @SuppressWarnings("unchecked")
182 private T[] getResult(final int[] indexes) {
183 final T[] result = (T[]) Array.newInstance(this.elements.getClass()
184 .getComponentType().getComponentType(), indexes.length);
185 for (int i = 0; i < indexes.length; i++) {
186 result[i] = this.elements[i][indexes[i]];
187 }
188 return result;
189 }
190
191 /**
192 * Not supported.
193 *
194 * @see java.util.Iterator#remove()
195 */
196 public void remove() {
197 throw new UnsupportedOperationException();
198 }
199
200 /**
201 * A combinatoric operator is itself an iterator.
202 *
203 * @return Itself.
204 * | result == this
205 * @see java.lang.Iterable#iterator()
206 */
207 public Iterator<T[]> iterator() {
208 return this;
209 }
210
211 }