You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2022/11/03 12:06:26 UTC
[commons-math] branch master updated: Remove "CombinatoricsUtils" class
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 <ah...@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>