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