1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 package org.hipparchus.util;
23
24 import org.hipparchus.exception.LocalizedCoreFormats;
25 import org.hipparchus.exception.MathIllegalArgumentException;
26 import org.hipparchus.exception.MathRuntimeException;
27 import org.junit.jupiter.api.Test;
28
29 import java.util.ArrayList;
30 import java.util.Arrays;
31 import java.util.Collections;
32 import java.util.HashMap;
33 import java.util.List;
34 import java.util.Map;
35 import java.util.NoSuchElementException;
36 import java.util.stream.Collectors;
37 import java.util.stream.IntStream;
38
39 import static org.junit.jupiter.api.Assertions.assertArrayEquals;
40 import static org.junit.jupiter.api.Assertions.assertEquals;
41 import static org.junit.jupiter.api.Assertions.assertFalse;
42 import static org.junit.jupiter.api.Assertions.assertThrows;
43 import static org.junit.jupiter.api.Assertions.assertTrue;
44 import static org.junit.jupiter.api.Assertions.fail;
45
46
47
48
49 class CombinatoricsUtilsTest {
50
51
52 private static final List<Map<Integer, Long>> binomialCache = new ArrayList<Map<Integer, Long>>();
53
54
55 @Test
56 void test0Choose0() {
57 assertEquals(1d, CombinatoricsUtils.binomialCoefficientDouble(0, 0), 0);
58 assertEquals(0d, CombinatoricsUtils.binomialCoefficientLog(0, 0), 0);
59 assertEquals(1, CombinatoricsUtils.binomialCoefficient(0, 0));
60 }
61
62 @Test
63 void testBinomialCoefficient() {
64 long[] bcoef5 = {
65 1,
66 5,
67 10,
68 10,
69 5,
70 1 };
71 long[] bcoef6 = {
72 1,
73 6,
74 15,
75 20,
76 15,
77 6,
78 1 };
79 for (int i = 0; i < 6; i++) {
80 assertEquals(bcoef5[i], CombinatoricsUtils.binomialCoefficient(5, i), "5 choose " + i);
81 }
82 for (int i = 0; i < 7; i++) {
83 assertEquals(bcoef6[i], CombinatoricsUtils.binomialCoefficient(6, i), "6 choose " + i);
84 }
85
86 for (int n = 1; n < 10; n++) {
87 for (int k = 0; k <= n; k++) {
88 assertEquals(binomialCoefficient(n, k), CombinatoricsUtils.binomialCoefficient(n, k), n + " choose " + k);
89 assertEquals(binomialCoefficient(n, k), CombinatoricsUtils.binomialCoefficientDouble(n, k), Double.MIN_VALUE, n + " choose " + k);
90 assertEquals(FastMath.log(binomialCoefficient(n, k)), CombinatoricsUtils.binomialCoefficientLog(n, k), 10E-12, n + " choose " + k);
91 }
92 }
93
94 int[] n = { 34, 66, 100, 1500, 1500 };
95 int[] k = { 17, 33, 10, 1500 - 4, 4 };
96 for (int i = 0; i < n.length; i++) {
97 long expected = binomialCoefficient(n[i], k[i]);
98 assertEquals(expected,
99 CombinatoricsUtils.binomialCoefficient(n[i], k[i]),
100 n[i] + " choose " + k[i]);
101 assertEquals(expected,
102 CombinatoricsUtils.binomialCoefficientDouble(n[i], k[i]), 0.0, n[i] + " choose " + k[i]);
103 assertEquals(FastMath.log(expected),
104 CombinatoricsUtils.binomialCoefficientLog(n[i], k[i]), 0.0, "log(" + n[i] + " choose " + k[i] + ")");
105 }
106 }
107
108 @Test
109 void testBinomialCoefficientFail() {
110 try {
111 CombinatoricsUtils.binomialCoefficient(4, 5);
112 fail("expecting MathIllegalArgumentException");
113 } catch (MathIllegalArgumentException ex) {
114
115 }
116
117 try {
118 CombinatoricsUtils.binomialCoefficientDouble(4, 5);
119 fail("expecting MathIllegalArgumentException");
120 } catch (MathIllegalArgumentException ex) {
121
122 }
123
124 try {
125 CombinatoricsUtils.binomialCoefficientLog(4, 5);
126 fail("expecting MathIllegalArgumentException");
127 } catch (MathIllegalArgumentException ex) {
128
129 }
130
131 try {
132 CombinatoricsUtils.binomialCoefficient(-1, -2);
133 fail("expecting MathIllegalArgumentException");
134 } catch (MathIllegalArgumentException ex) {
135
136 }
137 try {
138 CombinatoricsUtils.binomialCoefficientDouble(-1, -2);
139 fail("expecting MathIllegalArgumentException");
140 } catch (MathIllegalArgumentException ex) {
141
142 }
143 try {
144 CombinatoricsUtils.binomialCoefficientLog(-1, -2);
145 fail("expecting MathIllegalArgumentException");
146 } catch (MathIllegalArgumentException ex) {
147
148 }
149
150 try {
151 CombinatoricsUtils.binomialCoefficient(67, 30);
152 fail("expecting MathRuntimeException");
153 } catch (MathRuntimeException ex) {
154
155 }
156 try {
157 CombinatoricsUtils.binomialCoefficient(67, 34);
158 fail("expecting MathRuntimeException");
159 } catch (MathRuntimeException ex) {
160
161 }
162 double x = CombinatoricsUtils.binomialCoefficientDouble(1030, 515);
163 assertTrue(Double
164 .isInfinite(x), "expecting infinite binomial coefficient");
165 }
166
167
168
169
170
171 @Test
172 void testBinomialCoefficientLarge() throws Exception {
173
174 for (int n = 0; n <= 200; n++) {
175 for (int k = 0; k <= n; k++) {
176 long ourResult = -1;
177 long exactResult = -1;
178 boolean shouldThrow = false;
179 boolean didThrow = false;
180 try {
181 ourResult = CombinatoricsUtils.binomialCoefficient(n, k);
182 } catch (MathRuntimeException ex) {
183 didThrow = true;
184 }
185 try {
186 exactResult = binomialCoefficient(n, k);
187 } catch (MathRuntimeException ex) {
188 shouldThrow = true;
189 }
190 assertEquals(exactResult, ourResult, n + " choose " + k);
191 assertEquals(shouldThrow, didThrow, n + " choose " + k);
192 assertTrue((n > 66 || !didThrow), n + " choose " + k);
193
194 if (!shouldThrow && exactResult > 1) {
195 assertEquals(1.,
196 CombinatoricsUtils.binomialCoefficientDouble(n, k) / exactResult, 1e-10, n + " choose " + k);
197 assertEquals(1,
198 CombinatoricsUtils.binomialCoefficientLog(n, k) / FastMath.log(exactResult), 1e-10, n + " choose " + k);
199 }
200 }
201 }
202
203 long ourResult = CombinatoricsUtils.binomialCoefficient(300, 3);
204 long exactResult = binomialCoefficient(300, 3);
205 assertEquals(exactResult, ourResult);
206
207 ourResult = CombinatoricsUtils.binomialCoefficient(700, 697);
208 exactResult = binomialCoefficient(700, 697);
209 assertEquals(exactResult, ourResult);
210
211
212 try {
213 CombinatoricsUtils.binomialCoefficient(700, 300);
214 fail("Expecting MathRuntimeException");
215 } catch (MathRuntimeException ex) {
216
217 }
218
219 int n = 10000;
220 ourResult = CombinatoricsUtils.binomialCoefficient(n, 3);
221 exactResult = binomialCoefficient(n, 3);
222 assertEquals(exactResult, ourResult);
223 assertEquals(1, CombinatoricsUtils.binomialCoefficientDouble(n, 3) / exactResult, 1e-10);
224 assertEquals(1, CombinatoricsUtils.binomialCoefficientLog(n, 3) / FastMath.log(exactResult), 1e-10);
225
226 }
227
228 @Test
229 void testFactorial() {
230 for (int i = 1; i < 21; i++) {
231 assertEquals(factorial(i), CombinatoricsUtils.factorial(i), i + "! ");
232 assertEquals(factorial(i), CombinatoricsUtils.factorialDouble(i), Double.MIN_VALUE, i + "! ");
233 assertEquals(FastMath.log(factorial(i)), CombinatoricsUtils.factorialLog(i), 10E-12, i + "! ");
234 }
235
236 assertEquals(1, CombinatoricsUtils.factorial(0), "0");
237 assertEquals(1.0d, CombinatoricsUtils.factorialDouble(0), 1E-14, "0");
238 assertEquals(0.0d, CombinatoricsUtils.factorialLog(0), 1E-14, "0");
239 }
240
241 @Test
242 void testFactorialFail() {
243 try {
244 CombinatoricsUtils.factorial(-1);
245 fail("expecting MathIllegalArgumentException");
246 } catch (MathIllegalArgumentException ex) {
247
248 }
249 try {
250 CombinatoricsUtils.factorialDouble(-1);
251 fail("expecting MathIllegalArgumentException");
252 } catch (MathIllegalArgumentException ex) {
253
254 }
255 try {
256 CombinatoricsUtils.factorialLog(-1);
257 fail("expecting MathIllegalArgumentException");
258 } catch (MathIllegalArgumentException ex) {
259
260 }
261 try {
262 CombinatoricsUtils.factorial(21);
263 fail("expecting MathRuntimeException");
264 } catch (MathRuntimeException ex) {
265
266 }
267 assertTrue(Double.isInfinite(CombinatoricsUtils.factorialDouble(171)), "expecting infinite factorial value");
268 }
269
270 @Test
271 void testStirlingS2() {
272
273 assertEquals(1, CombinatoricsUtils.stirlingS2(0, 0));
274
275 for (int n = 1; n < 30; ++n) {
276 assertEquals(0, CombinatoricsUtils.stirlingS2(n, 0));
277 assertEquals(1, CombinatoricsUtils.stirlingS2(n, 1));
278 if (n > 2) {
279 assertEquals((1l << (n - 1)) - 1l, CombinatoricsUtils.stirlingS2(n, 2));
280 assertEquals(CombinatoricsUtils.binomialCoefficient(n, 2),
281 CombinatoricsUtils.stirlingS2(n, n - 1));
282 }
283 assertEquals(1, CombinatoricsUtils.stirlingS2(n, n));
284 }
285 assertEquals(536870911l, CombinatoricsUtils.stirlingS2(30, 2));
286 assertEquals(576460752303423487l, CombinatoricsUtils.stirlingS2(60, 2));
287
288 assertEquals( 25, CombinatoricsUtils.stirlingS2( 5, 3));
289 assertEquals( 90, CombinatoricsUtils.stirlingS2( 6, 3));
290 assertEquals( 65, CombinatoricsUtils.stirlingS2( 6, 4));
291 assertEquals( 301, CombinatoricsUtils.stirlingS2( 7, 3));
292 assertEquals( 350, CombinatoricsUtils.stirlingS2( 7, 4));
293 assertEquals( 140, CombinatoricsUtils.stirlingS2( 7, 5));
294 assertEquals( 966, CombinatoricsUtils.stirlingS2( 8, 3));
295 assertEquals( 1701, CombinatoricsUtils.stirlingS2( 8, 4));
296 assertEquals( 1050, CombinatoricsUtils.stirlingS2( 8, 5));
297 assertEquals( 266, CombinatoricsUtils.stirlingS2( 8, 6));
298 assertEquals( 3025, CombinatoricsUtils.stirlingS2( 9, 3));
299 assertEquals( 7770, CombinatoricsUtils.stirlingS2( 9, 4));
300 assertEquals( 6951, CombinatoricsUtils.stirlingS2( 9, 5));
301 assertEquals( 2646, CombinatoricsUtils.stirlingS2( 9, 6));
302 assertEquals( 462, CombinatoricsUtils.stirlingS2( 9, 7));
303 assertEquals( 9330, CombinatoricsUtils.stirlingS2(10, 3));
304 assertEquals(34105, CombinatoricsUtils.stirlingS2(10, 4));
305 assertEquals(42525, CombinatoricsUtils.stirlingS2(10, 5));
306 assertEquals(22827, CombinatoricsUtils.stirlingS2(10, 6));
307 assertEquals( 5880, CombinatoricsUtils.stirlingS2(10, 7));
308 assertEquals( 750, CombinatoricsUtils.stirlingS2(10, 8));
309
310 }
311
312 @Test
313 void testStirlingS2NegativeN() {
314 assertThrows(MathIllegalArgumentException.class, () -> {
315 CombinatoricsUtils.stirlingS2(3, -1);
316 });
317 }
318
319 @Test
320 void testStirlingS2LargeK() {
321 assertThrows(MathIllegalArgumentException.class, () -> {
322 CombinatoricsUtils.stirlingS2(3, 4);
323 });
324 }
325
326 @Test
327 void testStirlingS2Overflow() {
328 assertThrows(MathRuntimeException.class, () -> {
329 CombinatoricsUtils.stirlingS2(26, 9);
330 });
331 }
332
333 @Test
334 void testCheckBinomial1() {
335 assertThrows(MathIllegalArgumentException.class, () -> {
336
337 CombinatoricsUtils.checkBinomial(-1, -2);
338 });
339 }
340
341 @Test
342 void testCheckBinomial2() {
343 assertThrows(MathIllegalArgumentException.class, () -> {
344
345 CombinatoricsUtils.checkBinomial(4, 5);
346 });
347 }
348
349 @Test
350 void testCheckBinomial3() {
351
352 CombinatoricsUtils.checkBinomial(5, 4);
353 }
354
355 @Test
356 void testBellNumber() {
357
358 assertEquals( 1l, CombinatoricsUtils.bellNumber( 0));
359 assertEquals( 1l, CombinatoricsUtils.bellNumber( 1));
360 assertEquals( 2l, CombinatoricsUtils.bellNumber( 2));
361 assertEquals( 5l, CombinatoricsUtils.bellNumber( 3));
362 assertEquals( 15l, CombinatoricsUtils.bellNumber( 4));
363 assertEquals( 52l, CombinatoricsUtils.bellNumber( 5));
364 assertEquals( 203l, CombinatoricsUtils.bellNumber( 6));
365 assertEquals( 877l, CombinatoricsUtils.bellNumber( 7));
366 assertEquals( 4140l, CombinatoricsUtils.bellNumber( 8));
367 assertEquals( 21147l, CombinatoricsUtils.bellNumber( 9));
368 assertEquals( 115975l, CombinatoricsUtils.bellNumber(10));
369 assertEquals( 678570l, CombinatoricsUtils.bellNumber(11));
370 assertEquals( 4213597l, CombinatoricsUtils.bellNumber(12));
371 assertEquals( 27644437l, CombinatoricsUtils.bellNumber(13));
372 assertEquals( 190899322l, CombinatoricsUtils.bellNumber(14));
373 assertEquals( 1382958545l, CombinatoricsUtils.bellNumber(15));
374 assertEquals( 10480142147l, CombinatoricsUtils.bellNumber(16));
375 assertEquals( 82864869804l, CombinatoricsUtils.bellNumber(17));
376 assertEquals( 682076806159l, CombinatoricsUtils.bellNumber(18));
377 assertEquals( 5832742205057l, CombinatoricsUtils.bellNumber(19));
378 assertEquals(51724158235372l, CombinatoricsUtils.bellNumber(20));
379 }
380
381 @Test
382 void testBellNegative() {
383 try {
384 CombinatoricsUtils.bellNumber(-1);
385 fail("an exception should have been thrown");
386 } catch (MathIllegalArgumentException miae) {
387 assertEquals(LocalizedCoreFormats.NUMBER_TOO_SMALL, miae.getSpecifier());
388 assertEquals(-1, ((Integer) miae.getParts()[0]).intValue());
389 assertEquals( 0, ((Integer) miae.getParts()[1]).intValue());
390 }
391 }
392
393 @Test
394 void testBellLarge() {
395 try {
396 CombinatoricsUtils.bellNumber(26);
397 fail("an exception should have been thrown");
398 } catch (MathIllegalArgumentException miae) {
399 assertEquals(LocalizedCoreFormats.NUMBER_TOO_LARGE, miae.getSpecifier());
400 assertEquals(26, ((Integer) miae.getParts()[0]).intValue());
401 assertEquals(25, ((Integer) miae.getParts()[1]).intValue());
402 }
403 }
404
405 @Test
406 void testPartitions0() {
407 List<Integer> emptyList = Collections.emptyList();
408 final List<List<Integer>[]> partitions = CombinatoricsUtils.partitions(emptyList).
409 collect(Collectors.toList());
410 assertEquals(1, partitions.size());
411 assertEquals(1, partitions.get(0).length);
412 assertEquals(0, partitions.get(0)[0].size());
413 }
414
415 @Test
416 void testPartitions1() {
417 final List<List<Integer>[]> partitions = CombinatoricsUtils.partitions(Arrays.asList(1)).
418 collect(Collectors.toList());
419 assertEquals(1, partitions.size());
420 assertEquals(1, partitions.get(0).length);
421 assertEquals(1, partitions.get(0)[0].size());
422 }
423
424 @Test
425 void testPartitions4() {
426 final List<List<Integer>[]> partitions = CombinatoricsUtils.partitions(Arrays.asList(1, 2, 3, 4)).
427 collect(Collectors.toList());
428 assertEquals(15, partitions.size());
429
430 assertEquals(1, partitions.get(0).length);
431 assertArrayEquals(new Integer[] { 1, 2, 3, 4}, partitions.get(0)[0].toArray());
432
433 assertEquals(2, partitions.get(1).length);
434 assertArrayEquals(new Integer[] { 1, 2, 3 }, partitions.get(1)[0].toArray());
435 assertArrayEquals(new Integer[] { 4 }, partitions.get(1)[1].toArray());
436
437 assertEquals(2, partitions.get(2).length);
438 assertArrayEquals(new Integer[] { 1, 2, 4 }, partitions.get(2)[0].toArray());
439 assertArrayEquals(new Integer[] { 3 }, partitions.get(2)[1].toArray());
440
441 assertEquals(2, partitions.get(3).length);
442 assertArrayEquals(new Integer[] { 1, 2 }, partitions.get(3)[0].toArray());
443 assertArrayEquals(new Integer[] { 3, 4 }, partitions.get(3)[1].toArray());
444
445 assertEquals(3, partitions.get(4).length);
446 assertArrayEquals(new Integer[] { 1, 2 }, partitions.get(4)[0].toArray());
447 assertArrayEquals(new Integer[] { 3 }, partitions.get(4)[1].toArray());
448 assertArrayEquals(new Integer[] { 4 }, partitions.get(4)[2].toArray());
449
450 assertEquals(2, partitions.get(5).length);
451 assertArrayEquals(new Integer[] { 1, 3, 4 }, partitions.get(5)[0].toArray());
452 assertArrayEquals(new Integer[] { 2 }, partitions.get(5)[1].toArray());
453
454 assertEquals(2, partitions.get(6).length);
455 assertArrayEquals(new Integer[] { 1, 3 }, partitions.get(6)[0].toArray());
456 assertArrayEquals(new Integer[] { 2, 4 }, partitions.get(6)[1].toArray());
457
458 assertEquals(3, partitions.get(7).length);
459 assertArrayEquals(new Integer[] { 1, 3 }, partitions.get(7)[0].toArray());
460 assertArrayEquals(new Integer[] { 2 }, partitions.get(7)[1].toArray());
461 assertArrayEquals(new Integer[] { 4 }, partitions.get(7)[2].toArray());
462
463 assertEquals(2, partitions.get(8).length);
464 assertArrayEquals(new Integer[] { 1, 4 }, partitions.get(8)[0].toArray());
465 assertArrayEquals(new Integer[] { 2, 3 }, partitions.get(8)[1].toArray());
466
467 assertEquals(2, partitions.get(9).length);
468 assertArrayEquals(new Integer[] { 1 }, partitions.get(9)[0].toArray());
469 assertArrayEquals(new Integer[] { 2, 3, 4 }, partitions.get(9)[1].toArray());
470
471 assertEquals(3, partitions.get(10).length);
472 assertArrayEquals(new Integer[] { 1 }, partitions.get(10)[0].toArray());
473 assertArrayEquals(new Integer[] { 2, 3 }, partitions.get(10)[1].toArray());
474 assertArrayEquals(new Integer[] { 4 }, partitions.get(10)[2].toArray());
475
476 assertEquals(3, partitions.get(11).length);
477 assertArrayEquals(new Integer[] { 1, 4 }, partitions.get(11)[0].toArray());
478 assertArrayEquals(new Integer[] { 2 }, partitions.get(11)[1].toArray());
479 assertArrayEquals(new Integer[] { 3 }, partitions.get(11)[2].toArray());
480
481 assertEquals(3, partitions.get(12).length);
482 assertArrayEquals(new Integer[] { 1 }, partitions.get(12)[0].toArray());
483 assertArrayEquals(new Integer[] { 2, 4 }, partitions.get(12)[1].toArray());
484 assertArrayEquals(new Integer[] { 3 }, partitions.get(12)[2].toArray());
485
486 assertEquals(3, partitions.get(13).length);
487 assertArrayEquals(new Integer[] { 1 }, partitions.get(13)[0].toArray());
488 assertArrayEquals(new Integer[] { 2 }, partitions.get(13)[1].toArray());
489 assertArrayEquals(new Integer[] { 3, 4}, partitions.get(13)[2].toArray());
490
491 assertEquals(4, partitions.get(14).length);
492 assertArrayEquals(new Integer[] { 1 }, partitions.get(14)[0].toArray());
493 assertArrayEquals(new Integer[] { 2 }, partitions.get(14)[1].toArray());
494 assertArrayEquals(new Integer[] { 3 }, partitions.get(14)[2].toArray());
495 assertArrayEquals(new Integer[] { 4 }, partitions.get(14)[3].toArray());
496
497 }
498
499 @Test
500 void testPartitions42() {
501 final List<List<Integer>[]> partitions = CombinatoricsUtils.partitions(Arrays.asList(1, 2, 3, 4)).
502 filter(a -> a.length == 2).
503 collect(Collectors.toList());
504 assertEquals(7, partitions.size());
505
506 assertEquals(2, partitions.get(0).length);
507 assertArrayEquals(new Integer[] { 1, 2, 3 }, partitions.get(0)[0].toArray());
508 assertArrayEquals(new Integer[] { 4 }, partitions.get(0)[1].toArray());
509
510 assertEquals(2, partitions.get(1).length);
511 assertArrayEquals(new Integer[] { 1, 2, 4 }, partitions.get(1)[0].toArray());
512 assertArrayEquals(new Integer[] { 3 }, partitions.get(1)[1].toArray());
513
514 assertEquals(2, partitions.get(2).length);
515 assertArrayEquals(new Integer[] { 1, 2 }, partitions.get(2)[0].toArray());
516 assertArrayEquals(new Integer[] { 3, 4 }, partitions.get(2)[1].toArray());
517
518 assertEquals(2, partitions.get(3).length);
519 assertArrayEquals(new Integer[] { 1, 3, 4 }, partitions.get(3)[0].toArray());
520 assertArrayEquals(new Integer[] { 2 }, partitions.get(3)[1].toArray());
521
522 assertEquals(2, partitions.get(4).length);
523 assertArrayEquals(new Integer[] { 1, 3 }, partitions.get(4)[0].toArray());
524 assertArrayEquals(new Integer[] { 2, 4 }, partitions.get(4)[1].toArray());
525
526 assertEquals(2, partitions.get(5).length);
527 assertArrayEquals(new Integer[] { 1, 4 }, partitions.get(5)[0].toArray());
528 assertArrayEquals(new Integer[] { 2, 3 }, partitions.get(5)[1].toArray());
529
530 assertEquals(2, partitions.get(6).length);
531 assertArrayEquals(new Integer[] { 1 }, partitions.get(6)[0].toArray());
532 assertArrayEquals(new Integer[] { 2, 3, 4 }, partitions.get(6)[1].toArray());
533
534 }
535
536 @Test
537 void testPartitionsCount() {
538 for (int i = 0; i < 12; ++i) {
539 List<Integer> list = IntStream.range(0, i).collect(ArrayList::new, ArrayList::add, ArrayList::addAll);
540 long partitionsCount = CombinatoricsUtils.partitions(list).count();
541 assertEquals(CombinatoricsUtils.bellNumber(i), partitionsCount);
542 }
543 }
544
545 @Test
546 void testExhaustedPartitionsCount() {
547
548 PartitionsIterator<Integer> iterator = new PartitionsIterator<>(Arrays.asList(1, 2, 3));
549
550 assertTrue(iterator.hasNext());
551 assertEquals(1, iterator.next().length);
552 assertTrue(iterator.hasNext());
553 assertEquals(2, iterator.next().length);
554 assertTrue(iterator.hasNext());
555 assertEquals(2, iterator.next().length);
556 assertTrue(iterator.hasNext());
557 assertEquals(2, iterator.next().length);
558 assertTrue(iterator.hasNext());
559 assertEquals(3, iterator.next().length);
560
561 assertFalse(iterator.hasNext());
562 try {
563 iterator.next();
564 fail("an exception should have been thrown");
565 } catch (NoSuchElementException e) {
566
567 }
568 }
569
570 @Test
571 void testPermutations0() {
572 List<Integer> emptyList = Collections.emptyList();
573 final List<List<Integer>> permutations = CombinatoricsUtils.permutations(emptyList).
574 collect(Collectors.toList());
575 assertEquals(1, permutations.size());
576 assertEquals(0, permutations.get(0).size());
577 }
578
579 @Test
580 void testPermutations1() {
581 final List<List<Integer>> permutations = CombinatoricsUtils.permutations(Arrays.asList(1)).
582 collect(Collectors.toList());
583 assertEquals(1, permutations.size());
584 assertEquals(1, permutations.get(0).size());
585 }
586
587 @Test
588 void testPermutations3() {
589 final List<List<Integer>> permutations = CombinatoricsUtils.permutations(Arrays.asList(1, 2, 3)).
590 collect(Collectors.toList());
591 assertEquals(6, permutations.size());
592 assertArrayEquals(new Integer[] { 1, 2, 3 }, permutations.get(0).toArray(new Integer[0]));
593 assertArrayEquals(new Integer[] { 1, 3, 2 }, permutations.get(1).toArray(new Integer[0]));
594 assertArrayEquals(new Integer[] { 3, 1, 2 }, permutations.get(2).toArray(new Integer[0]));
595 assertArrayEquals(new Integer[] { 3, 2, 1 }, permutations.get(3).toArray(new Integer[0]));
596 assertArrayEquals(new Integer[] { 2, 3, 1 }, permutations.get(4).toArray(new Integer[0]));
597 assertArrayEquals(new Integer[] { 2, 1, 3 }, permutations.get(5).toArray(new Integer[0]));
598 }
599
600 @Test
601 void testPermutationsCount() {
602 for (int i = 0; i < 10; ++i) {
603 List<Integer> list = IntStream.range(0, i).collect(ArrayList::new, ArrayList::add, ArrayList::addAll);
604 long permutationsCount = CombinatoricsUtils.permutations(list).count();
605 assertEquals(CombinatoricsUtils.factorial(i), permutationsCount);
606 }
607 }
608
609 @Test
610 void testExhaustedPermutationsCount() {
611
612 PermutationsIterator<Integer> iterator = new PermutationsIterator<>(Arrays.asList(1, 2, 3));
613
614 assertTrue(iterator.hasNext());
615 assertEquals(3, iterator.next().size());
616 assertTrue(iterator.hasNext());
617 assertEquals(3, iterator.next().size());
618 assertTrue(iterator.hasNext());
619 assertEquals(3, iterator.next().size());
620 assertTrue(iterator.hasNext());
621 assertEquals(3, iterator.next().size());
622 assertTrue(iterator.hasNext());
623 assertEquals(3, iterator.next().size());
624 assertTrue(iterator.hasNext());
625 assertEquals(3, iterator.next().size());
626
627 assertFalse(iterator.hasNext());
628 try {
629 iterator.next();
630 fail("an exception should have been thrown");
631 } catch (NoSuchElementException e) {
632
633 }
634 }
635
636
637
638
639 private long binomialCoefficient(int n, int k) throws MathRuntimeException {
640 if (binomialCache.size() > n) {
641 Long cachedResult = binomialCache.get(n).get(Integer.valueOf(k));
642 if (cachedResult != null) {
643 return cachedResult.longValue();
644 }
645 }
646 long result = -1;
647 if ((n == k) || (k == 0)) {
648 result = 1;
649 } else if ((k == 1) || (k == n - 1)) {
650 result = n;
651 } else {
652
653 if (k < n - 100) {
654 binomialCoefficient(n - 100, k);
655 }
656 if (k > 100) {
657 binomialCoefficient(n - 100, k - 100);
658 }
659 result = ArithmeticUtils.addAndCheck(binomialCoefficient(n - 1, k - 1),
660 binomialCoefficient(n - 1, k));
661 }
662 if (result == -1) {
663 throw new MathRuntimeException(LocalizedCoreFormats.ARITHMETIC_EXCEPTION);
664 }
665 for (int i = binomialCache.size(); i < n + 1; i++) {
666 binomialCache.add(new HashMap<Integer, Long>());
667 }
668 binomialCache.get(n).put(Integer.valueOf(k), Long.valueOf(result));
669 return result;
670 }
671
672
673
674
675 private long factorial(int n) {
676 long result = 1;
677 for (int i = 2; i <= n; i++) {
678 result *= i;
679 }
680 return result;
681 }
682 }