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 * http://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 package org.apache.commons.numbers.combinatorics; 19 20 import java.io.Serializable; 21 import java.util.Arrays; 22 import java.util.NoSuchElementException; 23 import java.util.Iterator; 24 import java.util.Comparator; 25 26 import org.apache.commons.numbers.core.ArithmeticUtils; 27 28 /** 29 * Utility to create <a href="http://en.wikipedia.org/wiki/Combination"> 30 * combinations</a> {@code (n, k)} of {@code k} elements in a set of 31 * {@code n} elements. 32 */ 33 public final class Combinations implements Iterable<int[]> { 34 /** Size of the set from which combinations are drawn. */ 35 private final int n; 36 /** Number of elements in each combination. */ 37 private final int k; 38 39 /** 40 * @param n Size of the set from which subsets are selected. 41 * @param k Size of the subsets to be enumerated. 42 * @throws IllegalArgumentException if {@code n < 0}. 43 * @throws IllegalArgumentException if {@code k > n} or {@code k < 0}. 44 */ 45 private Combinations(int n, 46 int k) { 47 BinomialCoefficient.checkBinomial(n, k); 48 this.n = n; 49 this.k = k; 50 } 51 52 /** 53 * @param n Size of the set from which subsets are selected. 54 * @param k Size of the subsets to be enumerated. 55 * @throws IllegalArgumentException if {@code n < 0}. 56 * @throws IllegalArgumentException if {@code k > n} or {@code k < 0}. 57 * @return a new instance. 58 */ 59 public static Combinations of(int n, 60 int k) { 61 return new Combinations(n, k); 62 } 63 64 /** 65 * Gets the size of the set from which combinations are drawn. 66 * 67 * @return the size of the universe. 68 */ 69 public int getN() { 70 return n; 71 } 72 73 /** 74 * Gets the number of elements in each combination. 75 * 76 * @return the size of the subsets to be enumerated. 77 */ 78 public int getK() { 79 return k; 80 } 81 82 /** 83 * Creates an iterator whose range is the k-element subsets of 84 * {0, ..., n - 1} represented as {@code int[]} arrays. 85 * <p> 86 * The iteration order is lexicographic: the arrays returned by the 87 * {@link #iterator() iterator} are sorted in descending order and 88 * they are visited in lexicographic order with significance from 89 * right to left. 90 * For example, {@code new Combinations(4, 2).iterator()} returns 91 * an iterator that will generate the following sequence of arrays 92 * on successive calls to 93 * {@code next()}:<br> 94 * {@code [0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]} 95 * </p> 96 * If {@code k == 0} an iterator containing an empty array is returned; 97 * if {@code k == n} an iterator containing [0, ..., n - 1] is returned. 98 */ 99 @Override 100 public Iterator<int[]> iterator() { 101 return k == 0 || k == n ? 102 new SingletonIterator(k) : 103 new LexicographicIterator(n, k); 104 } 105 106 /** 107 * Creates a comparator. 108 * When performing a comparison, if an element of the array is not 109 * within the interval [0, {@code n}), an {@code IllegalArgumentException} 110 * will be thrown. 111 * 112 * @return a comparator. 113 */ 114 public Comparator<int[]> comparator() { 115 return new LexicographicComparator(n, k); 116 } 117 118 /** 119 * Lexicographic combinations iterator. 120 * <p> 121 * Implementation follows Algorithm T in <i>The Art of Computer Programming</i> 122 * Internet Draft (PRE-FASCICLE 3A), "A Draft of Section 7.2.1.3 Generating All 123 * Combinations, D. Knuth, 2004.</p> 124 * <p> 125 * The degenerate cases {@code k == 0} and {@code k == n} are NOT handled by this 126 * implementation. It is assumed that {@code n > k > 0}. 127 * </p> 128 */ 129 private static class LexicographicIterator implements Iterator<int[]> { 130 /** Size of subsets returned by the iterator. */ 131 private final int k; 132 133 /** 134 * c[1], ..., c[k] stores the next combination; c[k + 1], c[k + 2] are 135 * sentinels. 136 * <p> 137 * Note that c[0] is "wasted" but this makes it a little easier to 138 * follow the code. 139 * </p> 140 */ 141 private final int[] c; 142 143 /** Return value for {@link #hasNext()}. */ 144 private boolean more = true; 145 146 /** Marker: smallest index such that {@code c[j + 1] > j}. */ 147 private int j; 148 149 /** 150 * Construct a CombinationIterator to enumerate {@code k}-sets from a set 151 * of size {@code n}. 152 * <p> 153 * NOTE: It is assumed that {@code n > k > 0}. 154 * </p> 155 * 156 * @param n Size of the set from which subsets are enumerated. 157 * @param k Size of the subsets to enumerate. 158 */ 159 LexicographicIterator(int n, int k) { 160 this.k = k; 161 c = new int[k + 3]; 162 // Initialize c to start with lexicographically first k-set 163 for (int i = 1; i <= k; i++) { 164 c[i] = i - 1; 165 } 166 // Initialize sentinels 167 c[k + 1] = n; 168 c[k + 2] = 0; 169 j = k; // Set up invariant: j is smallest index such that c[j + 1] > j 170 } 171 172 /** 173 * {@inheritDoc} 174 */ 175 @Override 176 public boolean hasNext() { 177 return more; 178 } 179 180 /** 181 * {@inheritDoc} 182 */ 183 @Override 184 public int[] next() { 185 if (!more) { 186 throw new NoSuchElementException(); 187 } 188 // Copy return value (prepared by last activation) 189 final int[] ret = new int[k]; 190 System.arraycopy(c, 1, ret, 0, k); 191 192 // Prepare next iteration 193 // T2 and T6 loop 194 int x = 0; 195 if (j > 0) { 196 x = j; 197 c[j] = x; 198 j--; 199 return ret; 200 } 201 // T3 202 if (c[1] + 1 < c[2]) { 203 c[1]++; 204 return ret; 205 } else { 206 j = 2; 207 } 208 // T4 209 boolean stepDone = false; 210 while (!stepDone) { 211 c[j - 1] = j - 2; 212 x = c[j] + 1; 213 if (x == c[j + 1]) { 214 j++; 215 } else { 216 stepDone = true; 217 } 218 } 219 // T5 220 if (j > k) { 221 more = false; 222 return ret; 223 } 224 // T6 225 c[j] = x; 226 j--; 227 return ret; 228 } 229 230 /** 231 * Not supported. 232 */ 233 @Override 234 public void remove() { 235 throw new UnsupportedOperationException(); 236 } 237 } 238 239 /** 240 * Iterator with just one element to handle degenerate cases (full array, 241 * empty array) for combination iterator. 242 */ 243 private static class SingletonIterator implements Iterator<int[]> { 244 /** Number of elements of the singleton array. */ 245 private final int n; 246 /** True on initialization, false after first call to next. */ 247 private boolean more = true; 248 /** 249 * Create a singleton iterator providing the given array. 250 * 251 * @param n Size of the singleton array returned by the iterator. 252 */ 253 SingletonIterator(final int n) { 254 this.n = n; 255 } 256 /** 257 * @return {@code true} until next is called the first time, 258 * then {@code false}. 259 **/ 260 @Override 261 public boolean hasNext() { 262 return more; 263 } 264 /** 265 * @return the singleton at the first activation. 266 * @throws NoSuchElementException after the first activation. 267 */ 268 @Override 269 public int[] next() { 270 if (more) { 271 more = false; 272 // Create singleton. 273 final int[] s = new int[n]; 274 for (int i = 0; i < n; i++) { 275 s[i] = i; 276 } 277 return s; 278 } else { 279 throw new NoSuchElementException(); 280 } 281 } 282 /** 283 * Unsupported. 284 * 285 * @throws UnsupportedOperationException Remove is not supported. 286 */ 287 @Override 288 public void remove() { 289 throw new UnsupportedOperationException(); 290 } 291 } 292 293 /** 294 * Defines a lexicographic ordering of the combinations. 295 * 296 * The comparison is based on the value (in base 10) represented 297 * by the digit (interpreted in base {@code n}) in the input array, 298 * in reverse order. 299 */ 300 private static class LexicographicComparator 301 implements Comparator<int[]>, 302 Serializable { 303 /** Serializable version identifier. */ 304 private static final long serialVersionUID = 20170520L; 305 /** Size of the set from which combinations are drawn. */ 306 private final int n; 307 /** Number of elements in each combination. */ 308 private final int k; 309 310 /** 311 * @param n Size of the set from which subsets are selected. 312 * @param k Size of the subsets to be enumerated. 313 */ 314 LexicographicComparator(int n, 315 int k) { 316 this.n = n; 317 this.k = k; 318 } 319 320 /** 321 * {@inheritDoc} 322 * 323 * @throws IllegalArgumentException if the array lengths are not 324 * equal to {@code k}. 325 * @throws IllegalArgumentException if an element of the array is not 326 * within the interval [0, {@code n}). 327 */ 328 @Override 329 public int compare(int[] c1, 330 int[] c2) { 331 if (c1.length != k) { 332 throw new CombinatoricsException(CombinatoricsException.MISMATCH, c1.length, k); 333 } 334 if (c2.length != k) { 335 throw new CombinatoricsException(CombinatoricsException.MISMATCH, c2.length, k); 336 } 337 338 // Method "lexNorm" works with ordered arrays. 339 final int[] c1s = Arrays.copyOf(c1, k); 340 final int[] c2s = Arrays.copyOf(c2, k); 341 Arrays.sort(c1s); 342 Arrays.sort(c2s); 343 344 final long v1 = lexNorm(c1s); 345 final long v2 = lexNorm(c2s); 346 347 return Long.compare(v1, v2); 348 } 349 350 /** 351 * Computes the value (in base 10) represented by the digit 352 * (interpreted in base {@code n}) in the input array in reverse 353 * order. 354 * For example if {@code c} is {@code {3, 2, 1}}, and {@code n} 355 * is 3, the method will return 18. 356 * 357 * @param c Input array. 358 * @return the lexicographic norm. 359 * @throws IllegalArgumentException if an element of the array is not 360 * within the interval [0, {@code n}). 361 */ 362 private long lexNorm(int[] c) { 363 long ret = 0; 364 for (int i = 0; i < c.length; i++) { 365 final int digit = c[i]; 366 if (digit < 0 || 367 digit >= n) { 368 throw new CombinatoricsException(CombinatoricsException.OUT_OF_RANGE, digit, 0, n - 1); 369 } 370 371 ret += c[i] * ArithmeticUtils.pow((long) n, i); 372 } 373 return ret; 374 } 375 } 376 }