This is an automated email from the ASF dual-hosted git repository. aherbert pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/commons-math.git
The following commit(s) were added to refs/heads/master by this push: new 654697c04 Remove "CombinatoricsUtils" class 654697c04 is described below commit 654697c048b50b7e2ac28f012792098560df8db9 Author: aherbert <aherb...@apache.org> AuthorDate: Thu Nov 3 12:05:40 2022 +0000 Remove "CombinatoricsUtils" class Functionality is in "Commons Numbers" combinatorics package. --- .../math4/legacy/util/CombinatoricsUtils.java | 128 --------------------- .../math4/legacy/util/CombinatoricsUtilsTest.java | 89 -------------- src/changes/changes.xml | 4 + 3 files changed, 4 insertions(+), 217 deletions(-) diff --git a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/util/CombinatoricsUtils.java b/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/util/CombinatoricsUtils.java deleted file mode 100644 index e4e9c679b..000000000 --- a/commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/util/CombinatoricsUtils.java +++ /dev/null @@ -1,128 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math4.legacy.util; - -import java.util.concurrent.atomic.AtomicReference; - -import org.apache.commons.numbers.core.ArithmeticUtils; -import org.apache.commons.math4.legacy.exception.MathArithmeticException; -import org.apache.commons.math4.legacy.exception.NotPositiveException; -import org.apache.commons.math4.legacy.exception.NumberIsTooLargeException; -import org.apache.commons.math4.legacy.exception.util.LocalizedFormats; -import org.apache.commons.numbers.combinatorics.Factorial; -import org.apache.commons.numbers.combinatorics.BinomialCoefficient; - -/** - * Combinatorial utilities. - * - * @since 3.3 - */ -public final class CombinatoricsUtils { - /** Stirling numbers of the second kind. */ - static final AtomicReference<long[][]> STIRLING_S2 = new AtomicReference<> (null); - - /** Private constructor (class contains only static methods). */ - private CombinatoricsUtils() {} - - /** - * Returns the <a - * href="http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html"> - * Stirling number of the second kind</a>, "{@code S(n,k)}", the number of - * ways of partitioning an {@code n}-element set into {@code k} non-empty - * subsets. - * <p> - * The preconditions are {@code 0 <= k <= n } (otherwise - * {@code NotPositiveException} is thrown) - * </p> - * @param n the size of the set - * @param k the number of non-empty subsets - * @return {@code S(n,k)} - * @throws NotPositiveException if {@code k < 0}. - * @throws NumberIsTooLargeException if {@code k > n}. - * @throws MathArithmeticException if some overflow happens, typically for n exceeding 25 and - * k between 20 and n-2 (S(n,n-1) is handled specifically and does not overflow) - * @since 3.1 - */ - public static long stirlingS2(final int n, final int k) - throws NotPositiveException, NumberIsTooLargeException, MathArithmeticException { - if (k < 0) { - throw new NotPositiveException(k); - } - if (k > n) { - throw new NumberIsTooLargeException(k, n, true); - } - - long[][] stirlingS2 = STIRLING_S2.get(); - - if (stirlingS2 == null) { - // the cache has never been initialized, compute the first numbers - // by direct recurrence relation - - // as S(26,9) = 11201516780955125625 is larger than Long.MAX_VALUE - // we must stop computation at row 26 - final int maxIndex = 26; - stirlingS2 = new long[maxIndex][]; - stirlingS2[0] = new long[] { 1L }; - for (int i = 1; i < stirlingS2.length; ++i) { - stirlingS2[i] = new long[i + 1]; - stirlingS2[i][0] = 0; - stirlingS2[i][1] = 1; - stirlingS2[i][i] = 1; - for (int j = 2; j < i; ++j) { - stirlingS2[i][j] = j * stirlingS2[i - 1][j] + stirlingS2[i - 1][j - 1]; - } - } - - // atomically save the cache - STIRLING_S2.compareAndSet(null, stirlingS2); - } - - if (n < stirlingS2.length) { - // the number is in the small cache - return stirlingS2[n][k]; - } else { - // use explicit formula to compute the number without caching it - if (k == 0) { - return 0; - } else if (k == 1 || k == n) { - return 1; - } else if (k == 2) { - if (n > 64) { - throw new MathArithmeticException(LocalizedFormats.ARGUMENT_OUTSIDE_DOMAIN, - n, 0, stirlingS2.length - 1); - } - return (1L << (n - 1)) - 1L; - } else if (k == n - 1) { - return BinomialCoefficient.value(n, 2); - } else { - // definition formula: note that this may trigger some overflow - long sum = 0; - long sign = ((k & 0x1) == 0) ? 1 : -1; - for (int j = 1; j <= k; ++j) { - sign = -sign; - sum += sign * BinomialCoefficient.value(k, j) * ArithmeticUtils.pow(j, n); - if (sum < 0) { - // there was an overflow somewhere - throw new MathArithmeticException(LocalizedFormats.ARGUMENT_OUTSIDE_DOMAIN, - n, 0, stirlingS2.length - 1); - } - } - return sum / Factorial.value(k); - } - } - } -} diff --git a/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/util/CombinatoricsUtilsTest.java b/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/util/CombinatoricsUtilsTest.java deleted file mode 100644 index 19e5d8a59..000000000 --- a/commons-math-legacy/src/test/java/org/apache/commons/math4/legacy/util/CombinatoricsUtilsTest.java +++ /dev/null @@ -1,89 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math4.legacy.util; - -import org.apache.commons.math4.legacy.exception.MathArithmeticException; -import org.apache.commons.math4.legacy.exception.NotPositiveException; -import org.apache.commons.math4.legacy.exception.NumberIsTooLargeException; -import org.apache.commons.numbers.combinatorics.BinomialCoefficient; -import org.junit.jupiter.api.Assertions; -import org.junit.jupiter.api.Test; - -/** - * Test cases for the {@link CombinatoricsUtils} class. - */ -public class CombinatoricsUtilsTest { - - @Test - public void testStirlingS2() { - - Assertions.assertEquals(1, CombinatoricsUtils.stirlingS2(0, 0)); - - for (int n = 1; n < 30; ++n) { - Assertions.assertEquals(0, CombinatoricsUtils.stirlingS2(n, 0)); - Assertions.assertEquals(1, CombinatoricsUtils.stirlingS2(n, 1)); - if (n > 2) { - Assertions.assertEquals((1L << (n - 1)) - 1L, CombinatoricsUtils.stirlingS2(n, 2)); - Assertions.assertEquals(BinomialCoefficient.value(n, 2), - CombinatoricsUtils.stirlingS2(n, n - 1)); - } - Assertions.assertEquals(1, CombinatoricsUtils.stirlingS2(n, n)); - } - Assertions.assertEquals(536870911L, CombinatoricsUtils.stirlingS2(30, 2)); - Assertions.assertEquals(576460752303423487L, CombinatoricsUtils.stirlingS2(60, 2)); - - Assertions.assertEquals( 25, CombinatoricsUtils.stirlingS2( 5, 3)); - Assertions.assertEquals( 90, CombinatoricsUtils.stirlingS2( 6, 3)); - Assertions.assertEquals( 65, CombinatoricsUtils.stirlingS2( 6, 4)); - Assertions.assertEquals( 301, CombinatoricsUtils.stirlingS2( 7, 3)); - Assertions.assertEquals( 350, CombinatoricsUtils.stirlingS2( 7, 4)); - Assertions.assertEquals( 140, CombinatoricsUtils.stirlingS2( 7, 5)); - Assertions.assertEquals( 966, CombinatoricsUtils.stirlingS2( 8, 3)); - Assertions.assertEquals( 1701, CombinatoricsUtils.stirlingS2( 8, 4)); - Assertions.assertEquals( 1050, CombinatoricsUtils.stirlingS2( 8, 5)); - Assertions.assertEquals( 266, CombinatoricsUtils.stirlingS2( 8, 6)); - Assertions.assertEquals( 3025, CombinatoricsUtils.stirlingS2( 9, 3)); - Assertions.assertEquals( 7770, CombinatoricsUtils.stirlingS2( 9, 4)); - Assertions.assertEquals( 6951, CombinatoricsUtils.stirlingS2( 9, 5)); - Assertions.assertEquals( 2646, CombinatoricsUtils.stirlingS2( 9, 6)); - Assertions.assertEquals( 462, CombinatoricsUtils.stirlingS2( 9, 7)); - Assertions.assertEquals( 9330, CombinatoricsUtils.stirlingS2(10, 3)); - Assertions.assertEquals(34105, CombinatoricsUtils.stirlingS2(10, 4)); - Assertions.assertEquals(42525, CombinatoricsUtils.stirlingS2(10, 5)); - Assertions.assertEquals(22827, CombinatoricsUtils.stirlingS2(10, 6)); - Assertions.assertEquals( 5880, CombinatoricsUtils.stirlingS2(10, 7)); - Assertions.assertEquals( 750, CombinatoricsUtils.stirlingS2(10, 8)); - } - - @Test - public void testStirlingS2NegativeN() { - Assertions.assertThrows(NotPositiveException.class, () -> CombinatoricsUtils.stirlingS2(3, -1)); - } - - @Test - public void testStirlingS2LargeK() { - Assertions.assertThrows(NumberIsTooLargeException.class, () -> CombinatoricsUtils.stirlingS2(3, 4)); - } - - @Test - public void testStirlingS2Overflow() { - Assertions.assertThrows(MathArithmeticException.class, () -> CombinatoricsUtils.stirlingS2(26, 9)); - - Assertions.assertEquals(9223372036854775807L, CombinatoricsUtils.stirlingS2(64, 2)); - Assertions.assertThrows(MathArithmeticException.class, () -> CombinatoricsUtils.stirlingS2(65, 2)); - } -} diff --git a/src/changes/changes.xml b/src/changes/changes.xml index 44d534a8f..70d70f83d 100644 --- a/src/changes/changes.xml +++ b/src/changes/changes.xml @@ -97,6 +97,10 @@ Caveat: nightmare was one of the main reasons for creating more focused components.] "> + <action dev="aherbert" type="update" issue="MATH-1653"> + Remove class "CombinatoricsUtils" (in package "o.a.c.m.util"). + Functionality is in "Commons Numbers" combinatorics package. + </action> <action dev="erans" type="fix" issue="MATH-1647" due-to="Maksym Bohachov"> "HaltonSequenceGenerator": Raise exception when precondition is not met. </action>