1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * https://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 /*
19 * This is not the original file distributed by the Apache Software Foundation
20 * It has been modified by the Hipparchus project
21 */
22 package org.hipparchus.util;
23
24 import java.io.Serializable;
25 import java.util.Arrays;
26 import java.util.Comparator;
27 import java.util.Iterator;
28 import java.util.NoSuchElementException;
29
30 import org.hipparchus.exception.MathRuntimeException;
31
32 /**
33 * Utility to create combinations {@code (n, k)} of {@code k} elements
34 * in a set of {@code n} elements.
35 *
36 * @see <a href="http://en.wikipedia.org/wiki/Combination">
37 * Combination @ Wikipedia</a>
38 */
39 public class Combinations implements Iterable<int[]> {
40 /** Size of the set from which combinations are drawn. */
41 private final int n;
42 /** Number of elements in each combination. */
43 private final int k;
44 /** Iteration order. */
45 private final IterationOrder iterationOrder;
46
47 /**
48 * Describes the type of iteration performed by the
49 * {@link #iterator() iterator}.
50 */
51 private enum IterationOrder {
52 /** Lexicographic order. */
53 LEXICOGRAPHIC
54 }
55
56 /**
57 * Creates an instance whose range is the k-element subsets of
58 * {0, ..., n - 1} represented as {@code int[]} arrays.
59 * <p>
60 * The iteration order is lexicographic: the arrays returned by the
61 * {@link #iterator() iterator} are sorted in descending order and
62 * they are visited in lexicographic order with significance from
63 * right to left.
64 * For example, {@code new Combinations(4, 2).iterator()} returns
65 * an iterator that will generate the following sequence of arrays
66 * on successive calls to
67 * {@code next()}:<br>
68 * {@code [0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]}
69 * </p>
70 * If {@code k == 0} an iterator containing an empty array is returned;
71 * if {@code k == n} an iterator containing [0, ..., n - 1] is returned.
72 *
73 * @param n Size of the set from which subsets are selected.
74 * @param k Size of the subsets to be enumerated.
75 * @throws org.hipparchus.exception.MathIllegalArgumentException if {@code n < 0}.
76 * @throws org.hipparchus.exception.MathIllegalArgumentException if {@code k > n}.
77 */
78 public Combinations(int n,
79 int k) {
80 this(n, k, IterationOrder.LEXICOGRAPHIC);
81 }
82
83 /**
84 * Creates an instance whose range is the k-element subsets of
85 * {0, ..., n - 1} represented as {@code int[]} arrays.
86 * <p>
87 * If the {@code iterationOrder} argument is set to
88 * {@link IterationOrder#LEXICOGRAPHIC}, the arrays returned by the
89 * {@link #iterator() iterator} are sorted in descending order and
90 * they are visited in lexicographic order with significance from
91 * right to left.
92 * For example, {@code new Combinations(4, 2).iterator()} returns
93 * an iterator that will generate the following sequence of arrays
94 * on successive calls to
95 * {@code next()}:<br>
96 * {@code [0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]}
97 * </p>
98 * If {@code k == 0} an iterator containing an empty array is returned;
99 * if {@code k == n} an iterator containing [0, ..., n - 1] is returned.
100 *
101 * @param n Size of the set from which subsets are selected.
102 * @param k Size of the subsets to be enumerated.
103 * @param iterationOrder Specifies the {@link #iterator() iteration order}.
104 * @throws org.hipparchus.exception.MathIllegalArgumentException if {@code n < 0}.
105 * @throws org.hipparchus.exception.MathIllegalArgumentException if {@code k > n}.
106 */
107 private Combinations(int n,
108 int k,
109 IterationOrder iterationOrder) {
110 CombinatoricsUtils.checkBinomial(n, k);
111 this.n = n;
112 this.k = k;
113 this.iterationOrder = iterationOrder;
114 }
115
116 /**
117 * Gets the size of the set from which combinations are drawn.
118 *
119 * @return the size of the universe.
120 */
121 public int getN() {
122 return n;
123 }
124
125 /**
126 * Gets the number of elements in each combination.
127 *
128 * @return the size of the subsets to be enumerated.
129 */
130 public int getK() {
131 return k;
132 }
133
134 /** {@inheritDoc} */
135 @Override
136 public Iterator<int[]> iterator() {
137 if (k == 0 ||
138 k == n) {
139 return new SingletonIterator(k);
140 }
141
142 if (iterationOrder == IterationOrder.LEXICOGRAPHIC) {
143 return new LexicographicIterator(n, k);
144 } else {
145 throw MathRuntimeException.createInternalError(); // Should never happen.
146 }
147 }
148
149 /**
150 * Defines a lexicographic ordering of combinations.
151 * The returned comparator allows to compare any two combinations
152 * that can be produced by this instance's {@link #iterator() iterator}.
153 * Its {@code compare(int[],int[])} method will throw exceptions if
154 * passed combinations that are inconsistent with this instance:
155 * <ul>
156 * <li>if the array lengths are not equal to {@code k},</li>
157 * <li>if an element of the array is not within the interval [0, {@code n}).</li>
158 * </ul>
159 * @return a lexicographic comparator.
160 */
161 public Comparator<int[]> comparator() {
162 return new LexicographicComparator(n, k);
163 }
164
165 /**
166 * Lexicographic combinations iterator.
167 * <p>
168 * Implementation follows Algorithm T in <i>The Art of Computer Programming</i>
169 * Internet Draft (PRE-FASCICLE 3A), "A Draft of Section 7.2.1.3 Generating All
170 * Combinations</a>, D. Knuth, 2004.</p>
171 * <p>
172 * The degenerate cases {@code k == 0} and {@code k == n} are NOT handled by this
173 * implementation. If constructor arguments satisfy {@code k == 0}
174 * or {@code k >= n}, no exception is generated, but the iterator is empty.
175 */
176 private static class LexicographicIterator implements Iterator<int[]> {
177 /** Size of subsets returned by the iterator */
178 private final int k;
179
180 /**
181 * c[1], ..., c[k] stores the next combination; c[k + 1], c[k + 2] are
182 * sentinels.
183 * <p>
184 * Note that c[0] is "wasted" but this makes it a little easier to
185 * follow the code.
186 */
187 private final int[] c;
188
189 /** Return value for {@link #hasNext()} */
190 private boolean more = true;
191
192 /** Marker: smallest index such that c[j + 1] > j */
193 private int j;
194
195 /**
196 * Construct a CombinationIterator to enumerate k-sets from n.
197 * <p>
198 * NOTE: If {@code k === 0} or {@code k >= n}, the Iterator will be empty
199 * (that is, {@link #hasNext()} will return {@code false} immediately.
200 *
201 * @param n size of the set from which subsets are enumerated
202 * @param k size of the subsets to enumerate
203 */
204 LexicographicIterator(int n, int k) {
205 this.k = k;
206 c = new int[k + 3];
207 if (k == 0 || k >= n) {
208 more = false;
209 return;
210 }
211 // Initialize c to start with lexicographically first k-set
212 for (int i = 1; i <= k; i++) {
213 c[i] = i - 1;
214 }
215 // Initialize sentinels
216 c[k + 1] = n;
217 c[k + 2] = 0;
218 j = k; // Set up invariant: j is smallest index such that c[j + 1] > j
219 }
220
221 /**
222 * {@inheritDoc}
223 */
224 @Override
225 public boolean hasNext() {
226 return more;
227 }
228
229 /**
230 * {@inheritDoc}
231 */
232 @Override
233 public int[] next() {
234 if (!more) {
235 throw new NoSuchElementException();
236 }
237 // Copy return value (prepared by last activation)
238 final int[] ret = new int[k];
239 System.arraycopy(c, 1, ret, 0, k);
240
241 // Prepare next iteration
242 // T2 and T6 loop
243 int x = 0;
244 if (j > 0) {
245 x = j;
246 c[j] = x;
247 j--;
248 return ret;
249 }
250 // T3
251 if (c[1] + 1 < c[2]) {
252 c[1]++;
253 return ret;
254 } else {
255 j = 2;
256 }
257 // T4
258 boolean stepDone = false;
259 while (!stepDone) {
260 c[j - 1] = j - 2;
261 x = c[j] + 1;
262 if (x == c[j + 1]) {
263 j++;
264 } else {
265 stepDone = true;
266 }
267 }
268 // T5
269 if (j > k) {
270 more = false;
271 return ret;
272 }
273 // T6
274 c[j] = x;
275 j--;
276 return ret;
277 }
278
279 /**
280 * Not supported.
281 */
282 @Override
283 public void remove() {
284 throw new UnsupportedOperationException();
285 }
286 }
287
288 /**
289 * Iterator with just one element to handle degenerate cases (full array,
290 * empty array) for combination iterator.
291 */
292 private static class SingletonIterator implements Iterator<int[]> {
293 /** Singleton array */
294 private final int[] singleton;
295 /** True on initialization, false after first call to next */
296 private boolean more = true;
297 /**
298 * Create a singleton iterator providing the given array.
299 * @param k number of entries (i.e. entries will be 0..k-1)
300 */
301 SingletonIterator(final int k) {
302 this.singleton = MathArrays.natural(k);
303 }
304 /** @return True until next is called the first time, then false */
305 @Override
306 public boolean hasNext() {
307 return more;
308 }
309 /** @return the singleton in first activation; throws NSEE thereafter */
310 @Override
311 public int[] next() {
312 if (more) {
313 more = false;
314 return singleton.clone();
315 } else {
316 throw new NoSuchElementException();
317 }
318 }
319 /** Not supported */
320 @Override
321 public void remove() {
322 throw new UnsupportedOperationException();
323 }
324 }
325
326 /**
327 * Defines the lexicographic ordering of combinations, using
328 * the {@link #lexNorm(int[])} method.
329 */
330 private static class LexicographicComparator
331 implements Comparator<int[]>, Serializable {
332 /** Serializable version identifier. */
333 private static final long serialVersionUID = 20130906L;
334 /** Size of the set from which combinations are drawn. */
335 private final int n;
336 /** Number of elements in each combination. */
337 private final int k;
338
339 /**
340 * @param n Size of the set from which subsets are selected.
341 * @param k Size of the subsets to be enumerated.
342 */
343 LexicographicComparator(int n, int k) {
344 this.n = n;
345 this.k = k;
346 }
347
348 /**
349 * {@inheritDoc}
350 *
351 * @throws org.hipparchus.exception.MathIllegalArgumentException
352 * if the array lengths are not equal to {@code k}.
353 * @throws org.hipparchus.exception.MathIllegalArgumentException
354 * if an element of the array is not within the interval [0, {@code n}).
355 */
356 @Override
357 public int compare(int[] c1, int[] c2) {
358 MathUtils.checkDimension(c1.length, k);
359 MathUtils.checkDimension(c2.length, k);
360
361 // Method "lexNorm" works with ordered arrays.
362 final int[] c1s = c1.clone();
363 Arrays.sort(c1s);
364 final int[] c2s = c2.clone();
365 Arrays.sort(c2s);
366
367 final long v1 = lexNorm(c1s);
368 final long v2 = lexNorm(c2s);
369
370 if (v1 < v2) {
371 return -1;
372 } else if (v1 > v2) {
373 return 1;
374 } else {
375 return 0;
376 }
377 }
378
379 /**
380 * Computes the value (in base 10) represented by the digit
381 * (interpreted in base {@code n}) in the input array in reverse
382 * order.
383 * For example if {@code c} is {@code {3, 2, 1}}, and {@code n}
384 * is 3, the method will return 18.
385 *
386 * @param c Input array.
387 * @return the lexicographic norm.
388 * @throws org.hipparchus.exception.MathIllegalArgumentException
389 * if an element of the array is not within the interval [0, {@code n}).
390 */
391 private long lexNorm(int[] c) {
392 long ret = 0;
393 for (int i = 0; i < c.length; i++) {
394 final int digit = c[i];
395 MathUtils.checkRangeInclusive(digit, 0, n - 1);
396
397 ret += c[i] * ArithmeticUtils.pow(n, i);
398 }
399 return ret;
400 }
401 }
402 }