View Javadoc
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 }