001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 018package org.apache.commons.numbers.combinatorics; 019 020import java.io.Serializable; 021import java.util.Arrays; 022import java.util.NoSuchElementException; 023import java.util.Iterator; 024import java.util.Comparator; 025 026import org.apache.commons.numbers.core.ArithmeticUtils; 027 028/** 029 * Utility to create <a href="http://en.wikipedia.org/wiki/Combination"> 030 * combinations</a> {@code (n, k)} of {@code k} elements in a set of 031 * {@code n} elements. 032 */ 033public final class Combinations implements Iterable<int[]> { 034 /** Size of the set from which combinations are drawn. */ 035 private final int n; 036 /** Number of elements in each combination. */ 037 private final int k; 038 039 /** 040 * @param n Size of the set from which subsets are selected. 041 * @param k Size of the subsets to be enumerated. 042 * @throws IllegalArgumentException if {@code n < 0}. 043 * @throws IllegalArgumentException if {@code k > n} or {@code k < 0}. 044 */ 045 private Combinations(int n, 046 int k) { 047 BinomialCoefficient.checkBinomial(n, k); 048 this.n = n; 049 this.k = k; 050 } 051 052 /** 053 * @param n Size of the set from which subsets are selected. 054 * @param k Size of the subsets to be enumerated. 055 * @throws IllegalArgumentException if {@code n < 0}. 056 * @throws IllegalArgumentException if {@code k > n} or {@code k < 0}. 057 * @return a new instance. 058 */ 059 public static Combinations of(int n, 060 int k) { 061 return new Combinations(n, k); 062 } 063 064 /** 065 * Gets the size of the set from which combinations are drawn. 066 * 067 * @return the size of the universe. 068 */ 069 public int getN() { 070 return n; 071 } 072 073 /** 074 * Gets the number of elements in each combination. 075 * 076 * @return the size of the subsets to be enumerated. 077 */ 078 public int getK() { 079 return k; 080 } 081 082 /** 083 * Creates an iterator whose range is the k-element subsets of 084 * {0, ..., n - 1} represented as {@code int[]} arrays. 085 * <p> 086 * The iteration order is lexicographic: the arrays returned by the 087 * {@link #iterator() iterator} are sorted in descending order and 088 * they are visited in lexicographic order with significance from 089 * right to left. 090 * For example, {@code new Combinations(4, 2).iterator()} returns 091 * an iterator that will generate the following sequence of arrays 092 * on successive calls to 093 * {@code next()}:<br> 094 * {@code [0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]} 095 * </p> 096 * If {@code k == 0} an iterator containing an empty array is returned; 097 * if {@code k == n} an iterator containing [0, ..., n - 1] is returned. 098 */ 099 @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}