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    *      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  package org.apache.commons.numbers.combinatorics;
18  
19  import java.util.stream.Stream;
20  import org.apache.commons.numbers.core.ArithmeticUtils;
21  import org.junit.jupiter.api.Assertions;
22  import org.junit.jupiter.api.Test;
23  import org.junit.jupiter.params.ParameterizedTest;
24  import org.junit.jupiter.params.provider.Arguments;
25  import org.junit.jupiter.params.provider.CsvSource;
26  import org.junit.jupiter.params.provider.MethodSource;
27  
28  /**
29   * Test cases for the {@link Stirling} class.
30   */
31  class StirlingTest {
32  
33      /**
34       * Arguments that are illegal for the Stirling number computations.
35       *
36       * @return the arguments
37       */
38      static Stream<Arguments> stirlingIllegalArguments() {
39          return Stream.of(
40              Arguments.of(1, -1),
41              Arguments.of(-1, -1),
42              Arguments.of(-1, 1),
43              Arguments.of(10, 15),
44              Arguments.of(Integer.MIN_VALUE, 1),
45              Arguments.of(1, Integer.MIN_VALUE),
46              Arguments.of(Integer.MIN_VALUE, Integer.MIN_VALUE),
47              Arguments.of(Integer.MAX_VALUE - 1, Integer.MAX_VALUE)
48          );
49      }
50  
51      /**
52       * Arguments that should easily overflow the Stirling number computations.
53       * Used to verify the exception is correct
54       * (e.g. no StackOverflowError occurs due to recursion).
55       *
56       * @return the arguments
57       */
58      static Stream<Arguments> stirlingOverflowArguments() {
59          return Stream.of(
60              Arguments.of(123, 32),
61              Arguments.of(612534, 56123),
62              Arguments.of(261388631, 213),
63              Arguments.of(678688997, 213879),
64              Arguments.of(1000000002, 1000000000),
65              Arguments.of(1000000003, 1000000000),
66              Arguments.of(1000000004, 1000000000),
67              Arguments.of(1000000005, 1000000000),
68              Arguments.of(1000000010, 1000000000),
69              Arguments.of(1000000100, 1000000000)
70          );
71      }
72  
73      @ParameterizedTest
74      @MethodSource(value = {"stirlingIllegalArguments"})
75      void testStirlingS1IllegalArgument(int n, int k) {
76          Assertions.assertThrows(IllegalArgumentException.class, () -> Stirling.stirlingS1(n, k));
77      }
78  
79      @Test
80      void testStirlingS1StandardCases() {
81          Assertions.assertEquals(1, Stirling.stirlingS1(0, 0));
82  
83          for (int n = 1; n < 64; ++n) {
84              Assertions.assertEquals(0, Stirling.stirlingS1(n, 0));
85              if (n < 21) {
86                  Assertions.assertEquals(ArithmeticUtils.pow(-1, n - 1) * Factorial.value(n - 1),
87                                          Stirling.stirlingS1(n, 1));
88                  if (n > 2) {
89                      Assertions.assertEquals(-BinomialCoefficient.value(n, 2),
90                                              Stirling.stirlingS1(n, n - 1));
91                  }
92              }
93              Assertions.assertEquals(1, Stirling.stirlingS1(n, n));
94          }
95      }
96  
97      @ParameterizedTest
98      @CsvSource({
99          // Data verified using Mathematica StirlingS1[n, k]
100         "5, 3, 35",
101         "6, 3, -225",
102         "6, 4, 85",
103         "7, 3, 1624",
104         "7, 4, -735",
105         "7, 5, 175",
106         "8, 3, -13132",
107         "8, 4, 6769",
108         "8, 5, -1960",
109         "8, 6, 322",
110         "9, 3, 118124",
111         "9, 4, -67284",
112         "9, 5, 22449",
113         "9, 6, -4536",
114         "9, 7, 546",
115         "10, 3, -1172700",
116         "10, 4, 723680",
117         "10, 5, -269325",
118         "10, 6, 63273",
119         "10, 7, -9450",
120         "10, 8, 870",
121         // n >= 21 is not cached
122         // ... k in [1, 7] require n <= 21
123         "21, 8, -311333643161390640",
124         "21, 9, 63030812099294896",
125         "22, 10, 276019109275035346",
126         "22, 11, -37600535086859745",
127         "23, 12, -129006659818331295",
128         "23, 13, 12363045847086207",
129         "24, 14, 34701806448704206",
130         "25, 15, 92446911376173550",
131         "25, 16, -5700586321864500",
132         "26, 17, -12972753318542875",
133         "27, 18, -28460103232088385",
134         "28, 19, -60383004803151030",
135         "29, 20, -124243455209483610",
136         // k in [n-8, n-2]
137         "33, 25, 42669229615802790",
138         "40, 33, -16386027912368400",
139         "66, 60, 98715435586436240",
140         "155, 150, -1849441185054164625",
141         "404, 400, 1793805203416799170",
142         "1003, 1000, -21063481189500750",
143         "10002, 10000, 1250583420837500",
144         // Limits for k in [n-1, n] use n = Integer.MAX_VALUE
145         "2147483647, 2147483646, -2305843005992468481",
146         "2147483647, 2147483647, 1",
147         // Data for s(n, n-2)
148         "21, 19, 20615",
149         "22, 20, 25025",
150         "23, 21, 30107",
151         "24, 22, 35926",
152         "25, 23, 42550",
153         "26, 24, 50050",
154         "27, 25, 58500",
155         "92679, 92677, 9221886003909976111",
156         "92680, 92678, 9222284027979459010",
157         "92681, 92679, 9222682064933083810",
158         // Data for s(n, n-3)
159         "21, 18, -1256850",
160         "22, 19, -1689765",
161         "23, 20, -2240315",
162         "24, 21, -2932776",
163         "25, 22, -3795000",
164         "26, 23, -4858750",
165         "27, 24, -6160050",
166         "2758, 2755, -9145798629595485585",
167         "2759, 2756, -9165721700732052911",
168         "2760, 2757, -9185680925511388200",
169     })
170     void testStirlingS1(int n, int k, long expected) {
171         Assertions.assertEquals(expected, Stirling.stirlingS1(n, k));
172     }
173 
174     @ParameterizedTest
175     @CsvSource({
176         // Upper limits for n with k in [1, 20]
177         "21, 1, 2432902008176640000",
178         "21, 2, -8752948036761600000",
179         "20, 3, -668609730341153280",
180         "20, 4, 610116075740491776",
181         "21, 5, 8037811822645051776",
182         "21, 6, -3599979517947607200",
183         "21, 7, 1206647803780373360",
184         "22, 8, 7744654310169576800",
185         "22, 9, -1634980697246583456",
186         "23, 10, -7707401101297361068",
187         "23, 11, 1103230881185949736",
188         "24, 12, 4070384057007569521",
189         "24, 13, -413356714301314056",
190         "25, 14, -1246200069070215000",
191         "26, 15, -3557372853474553750",
192         "26, 16, 234961569422786050",
193         "27, 17, 572253155704900800",
194         "28, 18, 1340675942971287195",
195         "29, 19, 3031400077459516035",
196         "30, 20, 6634460278534540725",
197         // Upper limits for n with k in [n-9, n-2]
198         "35, 26, -5576855646887454930",
199         "44, 36, 6364808704290634598",
200         "61, 54, -8424028440309413250",
201         "95, 89, 8864929183170733205",
202         "181, 176, -8872439767850041020",
203         "495, 491, 9161199664152744351",
204         "2761, 2758, -9205676356399769400",
205         "92682, 92680, 9223080114771128550",
206     })
207     void testStirlingS1LimitsN(int n, int k, long expected) {
208         Assertions.assertEquals(expected, Stirling.stirlingS1(n, k));
209         Assertions.assertThrows(ArithmeticException.class, () -> Stirling.stirlingS1(n + 1, k));
210         Assertions.assertThrows(ArithmeticException.class, () -> Stirling.stirlingS1(n + 100, k));
211         Assertions.assertThrows(ArithmeticException.class, () -> Stirling.stirlingS1(n + 10000, k));
212     }
213 
214     @ParameterizedTest
215     @MethodSource(value = {"stirlingOverflowArguments"})
216     void testStirlingS1Overflow(int n, int k) {
217         Assertions.assertThrows(ArithmeticException.class, () -> Stirling.stirlingS1(n, k));
218     }
219 
220     @ParameterizedTest
221     @MethodSource(value = {"stirlingIllegalArguments"})
222     void testStirlingS2IllegalArgument(int n, int k) {
223         Assertions.assertThrows(IllegalArgumentException.class, () -> Stirling.stirlingS2(n, k));
224     }
225 
226     @Test
227     void testStirlingS2StandardCases() {
228         Assertions.assertEquals(1, Stirling.stirlingS2(0, 0));
229 
230         for (int n = 1; n < 64; ++n) {
231             Assertions.assertEquals(0, Stirling.stirlingS2(n, 0));
232             Assertions.assertEquals(1, Stirling.stirlingS2(n, 1));
233             if (n > 2) {
234                 Assertions.assertEquals((1L << (n - 1)) - 1L, Stirling.stirlingS2(n, 2));
235                 Assertions.assertEquals(BinomialCoefficient.value(n, 2),
236                                         Stirling.stirlingS2(n, n - 1));
237             }
238             Assertions.assertEquals(1, Stirling.stirlingS2(n, n));
239         }
240     }
241 
242     @ParameterizedTest
243     @CsvSource({
244         // Data verified using Mathematica StirlingS2[n, k]
245         "5, 3, 25",
246         "6, 3, 90",
247         "6, 4, 65",
248         "7, 3, 301",
249         "7, 4, 350",
250         "7, 5, 140",
251         "8, 3, 966",
252         "8, 4, 1701",
253         "8, 5, 1050",
254         "8, 6, 266",
255         "9, 3, 3025",
256         "9, 4, 7770",
257         "9, 5, 6951",
258         "9, 6, 2646",
259         "9, 7, 462",
260         "10, 3, 9330",
261         "10, 4, 34105",
262         "10, 5, 42525",
263         "10, 6, 22827",
264         "10, 7, 5880",
265         "10, 8, 750",
266         // n >= 26 is not cached
267         "30, 2, 536870911",
268         "37, 3, 75047248929022825",
269         "31, 4, 192050639071964750",
270         "29, 5, 1540200411172850701",
271         "26, 6, 224595186974125331",
272         // ... k in [7, 13] require n < 26
273         "26, 14, 477898618396288260",
274         "26, 15, 90449030191104000",
275         "26, 16, 12725877242482560",
276         "27, 17, 35569317763922670",
277         "27, 18, 3270191625210510",
278         "28, 19, 7626292886912700",
279         "28, 20, 474194413703010",
280         // k in [n-6, n-2]
281         "56, 50, 8735311973699025",
282         "115, 110, 79593419077014150",
283         "204, 200, 7075992116527915",
284         "1003, 1000, 20979521187625000",
285         "10002, 10000, 1250416704167500",
286         // Limits for k in [n-1, n] use n = Integer.MAX_VALUE
287         "2147483647, 2147483646, 2305843005992468481",
288         "2147483647, 2147483647, 1",
289         // Data for S(n, n-2)
290         "26, 24, 47450",
291         "27, 25, 55575",
292         "28, 26, 64701",
293         "29, 27, 74907",
294         "30, 28, 86275",
295         "31, 29, 98890",
296         "32, 30, 112840",
297         "92680, 92678, 9222151351858080650",
298         "92681, 92679, 9222549384516960590",
299         "92682, 92680, 9222947430060167790",
300         // Data for S(n, n-3)
301         "26, 23, 4126200",
302         "27, 24, 5265000",
303         "28, 25, 6654375",
304         "29, 26, 8336601",
305         "30, 27, 10359090",
306         "31, 28, 12774790",
307         "32, 29, 15642600",
308         "2759, 2756, 9152435640507623646",
309         "2760, 2757, 9172370757033509130",
310         "2761, 2758, 9192342044684582630",
311     })
312     void testStirlingS2(int n, int k, long expected) {
313         Assertions.assertEquals(expected, Stirling.stirlingS2(n, k));
314     }
315 
316     @ParameterizedTest
317     @CsvSource({
318         // Upper limits for n with k in [2, 22]
319         "64, 2, 9223372036854775807",
320         "41, 3, 6078831630016836625",
321         "33, 4, 3073530837671316330",
322         "30, 5, 7713000216608565075",
323         "28, 6, 8220146115188676396",
324         "26, 7, 1631853797991016600",
325         "26, 8, 5749622251945664950",
326         "25, 9, 1167921451092973005",
327         "25, 10, 1203163392175387500",
328         "25, 11, 802355904438462660",
329         "26, 12, 5149507353856958820",
330         "26, 13, 1850568574253550060",
331         "27, 14, 8541149231801585700",
332         "27, 15, 1834634071262848260",
333         "28, 16, 6539643128396047620",
334         "28, 17, 898741468057510350",
335         "29, 18, 2598531274376323650",
336         "30, 19, 7145845579888333500",
337         "30, 20, 581535955088511150",
338         "31, 21, 1359760239259935240",
339         "32, 22, 3069483578649883980",
340         // Upper limits for n with k in [n-10, n-2]
341         "33, 23, 6708404338089491700",
342         "38, 29, 6766081393022256030",
343         "47, 39, 8248929419122431611",
344         "63, 56, 8426132708490143472",
345         "96, 90, 8130394568857873780",
346         "183, 178, 9208213764702344301",
347         "496, 492, 9161200151995742994",
348         "2762, 2759, 9212349555946145400",
349         "92683, 92681, 9223345488487980291",
350     })
351     void testStirlingS2LimitsN(int n, int k, long expected) {
352         Assertions.assertEquals(expected, Stirling.stirlingS2(n, k));
353         Assertions.assertThrows(ArithmeticException.class, () -> Stirling.stirlingS2(n + 1, k));
354         Assertions.assertThrows(ArithmeticException.class, () -> Stirling.stirlingS2(n + 100, k));
355         Assertions.assertThrows(ArithmeticException.class, () -> Stirling.stirlingS2(n + 10000, k));
356     }
357 
358     @ParameterizedTest
359     @MethodSource(value = {"stirlingOverflowArguments"})
360     void testStirlingS2Overflow(int n, int k) {
361         Assertions.assertThrows(ArithmeticException.class, () -> Stirling.stirlingS2(n, k));
362     }
363 }