You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by er...@apache.org on 2017/05/21 02:07:19 UTC
[2/2] commons-numbers git commit: NUMBERS-29: New module for
combinatorics utilities ported from "Commons Math".
NUMBERS-29: New module for combinatorics utilities ported from "Commons Math".
Project: http://git-wip-us.apache.org/repos/asf/commons-numbers/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-numbers/commit/5b140a0e
Tree: http://git-wip-us.apache.org/repos/asf/commons-numbers/tree/5b140a0e
Diff: http://git-wip-us.apache.org/repos/asf/commons-numbers/diff/5b140a0e
Branch: refs/heads/master
Commit: 5b140a0e2f8bd84e8c51b67ad478486835841798
Parents: 0ad65c0
Author: Gilles Sadowski <gi...@harfang.homelinux.org>
Authored: Sun May 21 04:01:34 2017 +0200
Committer: Gilles Sadowski <gi...@harfang.homelinux.org>
Committed: Sun May 21 04:01:34 2017 +0200
----------------------------------------------------------------------
commons-numbers-combinatorics/LICENSE.txt | 201 +++++++++
commons-numbers-combinatorics/NOTICE.txt | 6 +
commons-numbers-combinatorics/README.md | 98 +++++
commons-numbers-combinatorics/pom.xml | 59 +++
.../combinatorics/BinomialCoefficient.java | 119 +++++
.../BinomialCoefficientDouble.java | 66 +++
.../numbers/combinatorics/Combinations.java | 434 +++++++++++++++++++
.../combinatorics/CombinatoricsException.java | 55 +++
.../numbers/combinatorics/Factorial.java | 53 +++
.../numbers/combinatorics/FactorialDouble.java | 134 ++++++
.../combinatorics/LogBinomialCoefficient.java | 83 ++++
.../numbers/combinatorics/LogFactorial.java | 115 +++++
.../numbers/combinatorics/package-info.java | 21 +
commons-numbers-combinatorics/src/site/site.xml | 35 ++
.../src/site/xdoc/index.xml | 40 ++
.../BinomialCoefficientDoubleTest.java | 106 +++++
.../combinatorics/BinomialCoefficientTest.java | 195 +++++++++
.../numbers/combinatorics/CombinationsTest.java | 194 +++++++++
.../combinatorics/FactorialDoubleTest.java | 130 ++++++
.../numbers/combinatorics/FactorialTest.java | 58 +++
.../LogBinomialCoefficientTest.java | 101 +++++
.../numbers/combinatorics/LogFactorialTest.java | 118 +++++
22 files changed, 2421 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/LICENSE.txt
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/LICENSE.txt b/commons-numbers-combinatorics/LICENSE.txt
new file mode 100644
index 0000000..261eeb9
--- /dev/null
+++ b/commons-numbers-combinatorics/LICENSE.txt
@@ -0,0 +1,201 @@
+ Apache License
+ Version 2.0, January 2004
+ http://www.apache.org/licenses/
+
+ TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+ 1. Definitions.
+
+ "License" shall mean the terms and conditions for use, reproduction,
+ and distribution as defined by Sections 1 through 9 of this document.
+
+ "Licensor" shall mean the copyright owner or entity authorized by
+ the copyright owner that is granting the License.
+
+ "Legal Entity" shall mean the union of the acting entity and all
+ other entities that control, are controlled by, or are under common
+ control with that entity. For the purposes of this definition,
+ "control" means (i) the power, direct or indirect, to cause the
+ direction or management of such entity, whether by contract or
+ otherwise, or (ii) ownership of fifty percent (50%) or more of the
+ outstanding shares, or (iii) beneficial ownership of such entity.
+
+ "You" (or "Your") shall mean an individual or Legal Entity
+ exercising permissions granted by this License.
+
+ "Source" form shall mean the preferred form for making modifications,
+ including but not limited to software source code, documentation
+ source, and configuration files.
+
+ "Object" form shall mean any form resulting from mechanical
+ transformation or translation of a Source form, including but
+ not limited to compiled object code, generated documentation,
+ and conversions to other media types.
+
+ "Work" shall mean the work of authorship, whether in Source or
+ Object form, made available under the License, as indicated by a
+ copyright notice that is included in or attached to the work
+ (an example is provided in the Appendix below).
+
+ "Derivative Works" shall mean any work, whether in Source or Object
+ form, that is based on (or derived from) the Work and for which the
+ editorial revisions, annotations, elaborations, or other modifications
+ represent, as a whole, an original work of authorship. For the purposes
+ of this License, Derivative Works shall not include works that remain
+ separable from, or merely link (or bind by name) to the interfaces of,
+ the Work and Derivative Works thereof.
+
+ "Contribution" shall mean any work of authorship, including
+ the original version of the Work and any modifications or additions
+ to that Work or Derivative Works thereof, that is intentionally
+ submitted to Licensor for inclusion in the Work by the copyright owner
+ or by an individual or Legal Entity authorized to submit on behalf of
+ the copyright owner. For the purposes of this definition, "submitted"
+ means any form of electronic, verbal, or written communication sent
+ to the Licensor or its representatives, including but not limited to
+ communication on electronic mailing lists, source code control systems,
+ and issue tracking systems that are managed by, or on behalf of, the
+ Licensor for the purpose of discussing and improving the Work, but
+ excluding communication that is conspicuously marked or otherwise
+ designated in writing by the copyright owner as "Not a Contribution."
+
+ "Contributor" shall mean Licensor and any individual or Legal Entity
+ on behalf of whom a Contribution has been received by Licensor and
+ subsequently incorporated within the Work.
+
+ 2. Grant of Copyright License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ copyright license to reproduce, prepare Derivative Works of,
+ publicly display, publicly perform, sublicense, and distribute the
+ Work and such Derivative Works in Source or Object form.
+
+ 3. Grant of Patent License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ (except as stated in this section) patent license to make, have made,
+ use, offer to sell, sell, import, and otherwise transfer the Work,
+ where such license applies only to those patent claims licensable
+ by such Contributor that are necessarily infringed by their
+ Contribution(s) alone or by combination of their Contribution(s)
+ with the Work to which such Contribution(s) was submitted. If You
+ institute patent litigation against any entity (including a
+ cross-claim or counterclaim in a lawsuit) alleging that the Work
+ or a Contribution incorporated within the Work constitutes direct
+ or contributory patent infringement, then any patent licenses
+ granted to You under this License for that Work shall terminate
+ as of the date such litigation is filed.
+
+ 4. Redistribution. You may reproduce and distribute copies of the
+ Work or Derivative Works thereof in any medium, with or without
+ modifications, and in Source or Object form, provided that You
+ meet the following conditions:
+
+ (a) You must give any other recipients of the Work or
+ Derivative Works a copy of this License; and
+
+ (b) You must cause any modified files to carry prominent notices
+ stating that You changed the files; and
+
+ (c) You must retain, in the Source form of any Derivative Works
+ that You distribute, all copyright, patent, trademark, and
+ attribution notices from the Source form of the Work,
+ excluding those notices that do not pertain to any part of
+ the Derivative Works; and
+
+ (d) If the Work includes a "NOTICE" text file as part of its
+ distribution, then any Derivative Works that You distribute must
+ include a readable copy of the attribution notices contained
+ within such NOTICE file, excluding those notices that do not
+ pertain to any part of the Derivative Works, in at least one
+ of the following places: within a NOTICE text file distributed
+ as part of the Derivative Works; within the Source form or
+ documentation, if provided along with the Derivative Works; or,
+ within a display generated by the Derivative Works, if and
+ wherever such third-party notices normally appear. The contents
+ of the NOTICE file are for informational purposes only and
+ do not modify the License. You may add Your own attribution
+ notices within Derivative Works that You distribute, alongside
+ or as an addendum to the NOTICE text from the Work, provided
+ that such additional attribution notices cannot be construed
+ as modifying the License.
+
+ You may add Your own copyright statement to Your modifications and
+ may provide additional or different license terms and conditions
+ for use, reproduction, or distribution of Your modifications, or
+ for any such Derivative Works as a whole, provided Your use,
+ reproduction, and distribution of the Work otherwise complies with
+ the conditions stated in this License.
+
+ 5. Submission of Contributions. Unless You explicitly state otherwise,
+ any Contribution intentionally submitted for inclusion in the Work
+ by You to the Licensor shall be under the terms and conditions of
+ this License, without any additional terms or conditions.
+ Notwithstanding the above, nothing herein shall supersede or modify
+ the terms of any separate license agreement you may have executed
+ with Licensor regarding such Contributions.
+
+ 6. Trademarks. This License does not grant permission to use the trade
+ names, trademarks, service marks, or product names of the Licensor,
+ except as required for reasonable and customary use in describing the
+ origin of the Work and reproducing the content of the NOTICE file.
+
+ 7. Disclaimer of Warranty. Unless required by applicable law or
+ agreed to in writing, Licensor provides the Work (and each
+ Contributor provides its Contributions) on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ implied, including, without limitation, any warranties or conditions
+ of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+ PARTICULAR PURPOSE. You are solely responsible for determining the
+ appropriateness of using or redistributing the Work and assume any
+ risks associated with Your exercise of permissions under this License.
+
+ 8. Limitation of Liability. In no event and under no legal theory,
+ whether in tort (including negligence), contract, or otherwise,
+ unless required by applicable law (such as deliberate and grossly
+ negligent acts) or agreed to in writing, shall any Contributor be
+ liable to You for damages, including any direct, indirect, special,
+ incidental, or consequential damages of any character arising as a
+ result of this License or out of the use or inability to use the
+ Work (including but not limited to damages for loss of goodwill,
+ work stoppage, computer failure or malfunction, or any and all
+ other commercial damages or losses), even if such Contributor
+ has been advised of the possibility of such damages.
+
+ 9. Accepting Warranty or Additional Liability. While redistributing
+ the Work or Derivative Works thereof, You may choose to offer,
+ and charge a fee for, acceptance of support, warranty, indemnity,
+ or other liability obligations and/or rights consistent with this
+ License. However, in accepting such obligations, You may act only
+ on Your own behalf and on Your sole responsibility, not on behalf
+ of any other Contributor, and only if You agree to indemnify,
+ defend, and hold each Contributor harmless for any liability
+ incurred by, or claims asserted against, such Contributor by reason
+ of your accepting any such warranty or additional liability.
+
+ END OF TERMS AND CONDITIONS
+
+ APPENDIX: How to apply the Apache License to your work.
+
+ To apply the Apache License to your work, attach the following
+ boilerplate notice, with the fields enclosed by brackets "[]"
+ replaced with your own identifying information. (Don't include
+ the brackets!) The text should be enclosed in the appropriate
+ comment syntax for the file format. We also recommend that a
+ file or class name and description of purpose be included on the
+ same "printed page" as the copyright notice for easier
+ identification within third-party archives.
+
+ Copyright [yyyy] [name of copyright owner]
+
+ Licensed 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.
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/NOTICE.txt
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/NOTICE.txt b/commons-numbers-combinatorics/NOTICE.txt
new file mode 100644
index 0000000..9091baa
--- /dev/null
+++ b/commons-numbers-combinatorics/NOTICE.txt
@@ -0,0 +1,6 @@
+Apache Commons Numbers
+Copyright 2001-2017 The Apache Software Foundation
+
+This product includes software developed at
+The Apache Software Foundation (http://www.apache.org/).
+
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/README.md
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/README.md b/commons-numbers-combinatorics/README.md
new file mode 100644
index 0000000..cbbf01f
--- /dev/null
+++ b/commons-numbers-combinatorics/README.md
@@ -0,0 +1,98 @@
+<!---
+ 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.
+-->
+<!---
+ +======================================================================+
+ |**** ****|
+ |**** THIS FILE IS GENERATED BY THE COMMONS BUILD PLUGIN ****|
+ |**** DO NOT EDIT DIRECTLY ****|
+ |**** ****|
+ +======================================================================+
+ | TEMPLATE FILE: readme-md-template.md |
+ | commons-build-plugin/trunk/src/main/resources/commons-xdoc-templates |
+ +======================================================================+
+ | |
+ | 1) Re-generate using: mvn commons:readme-md |
+ | |
+ | 2) Set the following properties in the component's pom: |
+ | - commons.componentid (required, alphabetic, lower case) |
+ | - commons.release.version (required) |
+ | |
+ | 3) Example Properties |
+ | |
+ | <properties> |
+ | <commons.componentid>math</commons.componentid> |
+ | <commons.release.version>1.2</commons.release.version> |
+ | </properties> |
+ | |
+ +======================================================================+
+--->
+Apache Commons Numbers Combinatorics
+===================
+
+Combinatorics utilities such as factorial and binomial coefficients.
+
+Documentation
+-------------
+
+More information can be found on the [homepage](https://commons.apache.org/proper/commons-numbers).
+The [JavaDoc](https://commons.apache.org/proper/commons-numbers/javadocs/api-release) can be browsed.
+Questions related to the usage of Apache Commons Numbers Combinatorics should be posted to the [user mailing list][ml].
+
+Where can I get the latest release?
+-----------------------------------
+You can download source and binaries from our [download page](https://commons.apache.org/proper/commons-numbers/download_numbers.cgi).
+
+Alternatively you can pull it from the central Maven repositories:
+
+```xml
+<dependency>
+ <groupId>org.apache.commons</groupId>
+ <artifactId>commons-numbers-combinatorics</artifactId>
+ <version>1.0</version>
+</dependency>
+```
+
+Contributing
+------------
+
+We accept PRs via github. The [developer mailing list][ml] is the main channel of communication for contributors.
+There are some guidelines which will make applying PRs easier for us:
++ No tabs! Please use spaces for indentation.
++ Respect the code style.
++ Create minimal diffs - disable on save actions like reformat source code or organize imports. If you feel the source code should be reformatted create a separate PR for this change.
++ Provide JUnit tests for your changes and make sure your changes don't break any existing tests by running ```mvn clean test```.
+
+If you plan to contribute on a regular basis, please consider filing a [contributor license agreement](https://www.apache.org/licenses/#clas).
+You can learn more about contributing via GitHub in our [contribution guidelines](CONTRIBUTING.md).
+
+License
+-------
+Code is under the [Apache Licence v2](https://www.apache.org/licenses/LICENSE-2.0.txt).
+
+Donations
+---------
+You like Apache Commons Numbers Combinatorics? Then [donate back to the ASF](https://www.apache.org/foundation/contributing.html) to support the development.
+
+Additional Resources
+--------------------
+
++ [Apache Commons Homepage](https://commons.apache.org/)
++ [Apache Bugtracker (JIRA)](https://issues.apache.org/jira/)
++ [Apache Commons Twitter Account](https://twitter.com/ApacheCommons)
++ #apachecommons IRC channel on freenode.org
+
+[ml]:https://commons.apache.org/mail-lists.html
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/pom.xml
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/pom.xml b/commons-numbers-combinatorics/pom.xml
new file mode 100644
index 0000000..f619a71
--- /dev/null
+++ b/commons-numbers-combinatorics/pom.xml
@@ -0,0 +1,59 @@
+<?xml version="1.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.
+-->
+<project xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd"
+ xmlns="http://maven.apache.org/POM/4.0.0"
+ xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
+ <modelVersion>4.0.0</modelVersion>
+
+ <parent>
+ <groupId>org.apache.commons</groupId>
+ <artifactId>commons-numbers-parent</artifactId>
+ <version>1.0-SNAPSHOT</version>
+ </parent>
+
+ <groupId>org.apache.commons</groupId>
+ <artifactId>commons-numbers-combinatorics</artifactId>
+ <version>1.0-SNAPSHOT</version>
+ <name>Apache Commons Numbers Combinatorics</name>
+
+ <description>Combinatorics utilities such as factorial and binomial coefficients.</description>
+
+ <properties>
+ <!-- This value must reflect the current name of the base package. -->
+ <commons.osgi.symbolicName>org.apache.commons.numbers.combinatorics</commons.osgi.symbolicName>
+ <!-- OSGi -->
+ <commons.osgi.export>org.apache.commons.numbers.combinatorics</commons.osgi.export>
+ <!-- Workaround to avoid duplicating config files. -->
+ <numbers.parent.dir>${basedir}/..</numbers.parent.dir>
+ </properties>
+
+ <dependencies>
+ <dependency>
+ <groupId>org.apache.commons</groupId>
+ <artifactId>commons-numbers-gamma</artifactId>
+ <version>1.0-SNAPSHOT</version>
+ </dependency>
+
+ <dependency>
+ <groupId>org.apache.commons</groupId>
+ <artifactId>commons-numbers-core</artifactId>
+ <version>1.0-SNAPSHOT</version>
+ </dependency>
+ </dependencies>
+
+</project>
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/BinomialCoefficient.java
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/BinomialCoefficient.java b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/BinomialCoefficient.java
new file mode 100644
index 0000000..6da5a7d
--- /dev/null
+++ b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/BinomialCoefficient.java
@@ -0,0 +1,119 @@
+/*
+ * 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.numbers.combinatorics;
+
+import org.apache.commons.numbers.core.ArithmeticUtils;
+
+/**
+ * Representation of the <a href="http://mathworld.wolfram.com/BinomialCoefficient.html">
+ * binomial coefficient</a>.
+ * It is "{@code n choose k}", the number of {@code k}-element subsets that
+ * can be selected from an {@code n}-element set.
+ */
+public class BinomialCoefficient {
+ /**
+ * Computes de binomial coefficient.
+ * The largest value of {@code n} for which all coefficients can
+ * fit into a {@code long} is 66.
+ *
+ * @param n Size of the set.
+ * @param k Size of the subsets to be counted.
+ * @return {@code n choose k}.
+ * @throws IllegalArgumentException if {@code n < 0}.
+ * @throws IllegalArgumentException if {@code k > n}.
+ * @throws ArithmeticException if the result is too large to be
+ * represented by a {@code long}.
+ */
+ public static long value(int n, int k) {
+ checkBinomial(n, k);
+
+ if (n == k ||
+ k == 0) {
+ return 1;
+ }
+ if (k == 1 ||
+ k == n - 1) {
+ return n;
+ }
+ // Use symmetry for large k.
+ if (k > n / 2) {
+ return value(n, n - k);
+ }
+
+ // We use the formulae:
+ // (n choose k) = n! / (n-k)! / k!
+ // (n choose k) = ((n-k+1)*...*n) / (1*...*k)
+ // which can be written
+ // (n choose k) = (n-1 choose k-1) * n / k
+ long result = 1;
+ if (n <= 61) {
+ // For n <= 61, the naive implementation cannot overflow.
+ int i = n - k + 1;
+ for (int j = 1; j <= k; j++) {
+ result = result * i / j;
+ i++;
+ }
+ } else if (n <= 66) {
+ // For n > 61 but n <= 66, the result cannot overflow,
+ // but we must take care not to overflow intermediate values.
+ int i = n - k + 1;
+ for (int j = 1; j <= k; j++) {
+ // We know that (result * i) is divisible by j,
+ // but (result * i) may overflow, so we split j:
+ // Filter out the gcd, d, so j/d and i/d are integer.
+ // result is divisible by (j/d) because (j/d)
+ // is relative prime to (i/d) and is a divisor of
+ // result * (i/d).
+ final long d = ArithmeticUtils.gcd(i, j);
+ result = (result / (j / d)) * (i / d);
+ ++i;
+ }
+ } else {
+ // For n > 66, a result overflow might occur, so we check
+ // the multiplication, taking care to not overflow
+ // unnecessary.
+ int i = n - k + 1;
+ for (int j = 1; j <= k; j++) {
+ final long d = ArithmeticUtils.gcd(i, j);
+ result = ArithmeticUtils.mulAndCheck(result / (j / d), i / d);
+ ++i;
+ }
+ }
+
+ return result;
+ }
+
+ /**
+ * Check binomial preconditions.
+ *
+ * @param n Size of the set.
+ * @param k Size of the subsets to be counted.
+ * @throws IllegalArgumentException if {@code n < 0}.
+ * @throws IllegalArgumentException if {@code k > n} or {@code k < 0}.
+ */
+ static void checkBinomial(int n,
+ int k) {
+ if (n < 0) {
+ throw new CombinatoricsException(CombinatoricsException.NEGATIVE, n);
+ }
+ if (k > n ||
+ k < 0) {
+ throw new CombinatoricsException(CombinatoricsException.OUT_OF_RANGE, k, 0, n);
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/BinomialCoefficientDouble.java
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/BinomialCoefficientDouble.java b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/BinomialCoefficientDouble.java
new file mode 100644
index 0000000..609b13e
--- /dev/null
+++ b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/BinomialCoefficientDouble.java
@@ -0,0 +1,66 @@
+/*
+ * 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.numbers.combinatorics;
+
+/**
+ * Representation of the <a href="http://mathworld.wolfram.com/BinomialCoefficient.html">
+ * binomial coefficient</a>, as a {@code double}.
+ * It is "{@code n choose k}", the number of {@code k}-element subsets that
+ * can be selected from an {@code n}-element set.
+ */
+public class BinomialCoefficientDouble {
+ /**
+ * Computes de binomial coefficient.
+ * The largest value of {@code n} for which all coefficients can
+ * fit into a {@code long} is 66.
+ *
+ * @param n Size of the set.
+ * @param k Size of the subsets to be counted.
+ * @return {@code n choose k}.
+ * @throws IllegalArgumentException if {@code n < 0}.
+ * @throws IllegalArgumentException if {@code k > n}.
+ * @throws IllegalArgumentException if the result is too large to be
+ * represented by a {@code long}.
+ */
+ public static double value(int n, int k) {
+ BinomialCoefficient.checkBinomial(n, k);
+
+ if (n == k ||
+ k == 0) {
+ return 1;
+ }
+ if (k == 1 ||
+ k == n - 1) {
+ return n;
+ }
+ if (k > n / 2) {
+ return value(n, n - k);
+ }
+ if (n < 67) {
+ return BinomialCoefficient.value(n, k);
+ }
+
+ double result = 1;
+ for (int i = 1; i <= k; i++) {
+ result *= n - k + i;
+ result /= i;
+ }
+
+ return Math.floor(result + 0.5);
+ }
+}
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/Combinations.java
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/Combinations.java b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/Combinations.java
new file mode 100644
index 0000000..691b2c1
--- /dev/null
+++ b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/Combinations.java
@@ -0,0 +1,434 @@
+/*
+ * 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.numbers.combinatorics;
+
+import java.io.Serializable;
+import java.util.Arrays;
+import java.util.NoSuchElementException;
+import java.util.Iterator;
+import java.util.Comparator;
+
+import org.apache.commons.numbers.core.ArithmeticUtils;
+
+/**
+ * Utility to create <a href="http://en.wikipedia.org/wiki/Combination">
+ * combinations</a> {@code (n, k)} of {@code k} elements in a set of
+ * {@code n} elements.
+ */
+public class Combinations implements Iterable<int[]> {
+ /** Size of the set from which combinations are drawn. */
+ private final int n;
+ /** Number of elements in each combination. */
+ private final int k;
+ /** Iteration order. */
+ private final IterationOrder iterationOrder;
+
+ /**
+ * Describes the type of iteration performed by the
+ * {@link #iterator() iterator}.
+ */
+ private enum IterationOrder {
+ /** Lexicographic order. */
+ LEXICOGRAPHIC
+ }
+
+ /**
+ * Creates an instance whose range is the k-element subsets of
+ * {0, ..., n - 1} represented as {@code int[]} arrays.
+ * <p>
+ * The iteration order is lexicographic: the arrays returned by the
+ * {@link #iterator() iterator} are sorted in descending order and
+ * they are visited in lexicographic order with significance from
+ * right to left.
+ * For example, {@code new Combinations(4, 2).iterator()} returns
+ * an iterator that will generate the following sequence of arrays
+ * on successive calls to
+ * {@code next()}:<br>
+ * {@code [0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]}
+ * </p>
+ * If {@code k == 0} an iterator containing an empty array is returned;
+ * if {@code k == n} an iterator containing [0, ..., n - 1] is returned.
+ *
+ * @param n Size of the set from which subsets are selected.
+ * @param k Size of the subsets to be enumerated.
+ * @throws IllegalArgumentException if {@code n < 0}.
+ * @throws IllegalArgumentException if {@code k > n} or {@code k < 0}.
+ */
+ public Combinations(int n,
+ int k) {
+ this(n, k, IterationOrder.LEXICOGRAPHIC);
+ }
+
+ /**
+ * Creates an instance whose range is the k-element subsets of
+ * {0, ..., n - 1} represented as {@code int[]} arrays.
+ * <p>
+ * If the {@code iterationOrder} argument is set to
+ * {@link IterationOrder#LEXICOGRAPHIC}, the arrays returned by the
+ * {@link #iterator() iterator} are sorted in descending order and
+ * they are visited in lexicographic order with significance from
+ * right to left.
+ * For example, {@code new Combinations(4, 2).iterator()} returns
+ * an iterator that will generate the following sequence of arrays
+ * on successive calls to
+ * {@code next()}:<br>
+ * {@code [0, 1], [0, 2], [1, 2], [0, 3], [1, 3], [2, 3]}
+ * </p>
+ * If {@code k == 0} an iterator containing an empty array is returned;
+ * if {@code k == n} an iterator containing [0, ..., n - 1] is returned.
+ *
+ * @param n Size of the set from which subsets are selected.
+ * @param k Size of the subsets to be enumerated.
+ * @param iterationOrder Specifies the {@link #iterator() iteration order}.
+ * @throws IllegalArgumentException if {@code n < 0}.
+ * @throws IllegalArgumentException if {@code k > n} or {@code k < 0}.
+ */
+ private Combinations(int n,
+ int k,
+ IterationOrder iterationOrder) {
+ BinomialCoefficient.checkBinomial(n, k);
+ this.n = n;
+ this.k = k;
+ this.iterationOrder = iterationOrder;
+ }
+
+ /**
+ * Gets the size of the set from which combinations are drawn.
+ *
+ * @return the size of the universe.
+ */
+ public int getN() {
+ return n;
+ }
+
+ /**
+ * Gets the number of elements in each combination.
+ *
+ * @return the size of the subsets to be enumerated.
+ */
+ public int getK() {
+ return k;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public Iterator<int[]> iterator() {
+ if (k == 0 ||
+ k == n) {
+ return new SingletonIterator(k);
+ }
+
+ switch (iterationOrder) {
+ case LEXICOGRAPHIC:
+ return new LexicographicIterator(n, k);
+ default:
+ // Should never happen.
+ throw new UnsupportedOperationException("Please file a bug report");
+ }
+ }
+
+ /**
+ * Lexicographic combinations iterator.
+ * <p>
+ * Implementation follows Algorithm T in <i>The Art of Computer Programming</i>
+ * Internet Draft (PRE-FASCICLE 3A), "A Draft of Section 7.2.1.3 Generating All
+ * Combinations</a>, D. Knuth, 2004.</p>
+ * <p>
+ * The degenerate cases {@code k == 0} and {@code k == n} are NOT handled by this
+ * implementation. If constructor arguments satisfy {@code k == 0}
+ * or {@code k >= n}, no exception is generated, but the iterator is empty.
+ * </p>
+ *
+ */
+ private static class LexicographicIterator implements Iterator<int[]> {
+ /** Size of subsets returned by the iterator. */
+ private final int k;
+
+ /**
+ * c[1], ..., c[k] stores the next combination; c[k + 1], c[k + 2] are
+ * sentinels.
+ * <p>
+ * Note that c[0] is "wasted" but this makes it a little easier to
+ * follow the code.
+ * </p>
+ */
+ private final int[] c;
+
+ /** Return value for {@link #hasNext()} */
+ private boolean more = true;
+
+ /** Marker: smallest index such that {@code c[j + 1] > j}. */
+ private int j;
+
+ /**
+ * Construct a CombinationIterator to enumerate {@code k}-sets from a set
+ * of size {@code n}.
+ * <p>
+ * NOTE: If {@code k === 0} or {@code k >= n}, the Iterator will be empty
+ * (that is, {@link #hasNext()} will return {@code false} immediately.
+ * </p>
+ *
+ * @param n Size of the set from which subsets are enumerated.
+ * @param k Size of the subsets to enumerate.
+ */
+ LexicographicIterator(int n, int k) {
+ this.k = k;
+ c = new int[k + 3];
+ if (k == 0 || k >= n) {
+ more = false;
+ return;
+ }
+ // Initialize c to start with lexicographically first k-set
+ for (int i = 1; i <= k; i++) {
+ c[i] = i - 1;
+ }
+ // Initialize sentinels
+ c[k + 1] = n;
+ c[k + 2] = 0;
+ j = k; // Set up invariant: j is smallest index such that c[j + 1] > j
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public boolean hasNext() {
+ return more;
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public int[] next() {
+ if (!more) {
+ throw new NoSuchElementException();
+ }
+ // Copy return value (prepared by last activation)
+ final int[] ret = new int[k];
+ System.arraycopy(c, 1, ret, 0, k);
+
+ // Prepare next iteration
+ // T2 and T6 loop
+ int x = 0;
+ if (j > 0) {
+ x = j;
+ c[j] = x;
+ j--;
+ return ret;
+ }
+ // T3
+ if (c[1] + 1 < c[2]) {
+ c[1]++;
+ return ret;
+ } else {
+ j = 2;
+ }
+ // T4
+ boolean stepDone = false;
+ while (!stepDone) {
+ c[j - 1] = j - 2;
+ x = c[j] + 1;
+ if (x == c[j + 1]) {
+ j++;
+ } else {
+ stepDone = true;
+ }
+ }
+ // T5
+ if (j > k) {
+ more = false;
+ return ret;
+ }
+ // T6
+ c[j] = x;
+ j--;
+ return ret;
+ }
+
+ /**
+ * Not supported.
+ */
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ }
+
+ /**
+ * Iterator with just one element to handle degenerate cases (full array,
+ * empty array) for combination iterator.
+ */
+ private static class SingletonIterator implements Iterator<int[]> {
+ /** Number of elements of the singleton array. */
+ private final int n;
+ /** True on initialization, false after first call to next */
+ private boolean more = true;
+ /**
+ * Create a singleton iterator providing the given array.
+ *
+ * @param n Size of the singleton array returned by the iterator.
+ */
+ SingletonIterator(final int n) {
+ this.n = n;
+ }
+ /**
+ * @return {@code true} until next is called the first time,
+ * then {@code false}.
+ **/
+ @Override
+ public boolean hasNext() {
+ return more;
+ }
+ /**
+ * @return the singleton at the first activation.
+ * @throws NoSuchElementException after the first activation.
+ */
+ @Override
+ public int[] next() {
+ if (more) {
+ more = false;
+ // Create singleton.
+ final int[] s = new int[n];
+ for (int i = 0; i < n; i++) {
+ s[i] = i;
+ }
+ return s;
+ } else {
+ throw new NoSuchElementException();
+ }
+ }
+ /**
+ * Unsupported.
+ *
+ * @throws UnsupportedOperationException
+ */
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException();
+ }
+ }
+
+ /**
+ * Defines a lexicographic ordering of the combinations.
+ *
+ * The comparison is based on the value (in base 10) represented
+ * by the digit (interpreted in base {@code n}) in the input array,
+ * in reverse order.
+ * For example if {@code c} is {@code {3, 2, 1}}, and {@code n}
+ * is 3, the method will return 18.
+ */
+ public static class LexicographicComparator
+ implements Comparator<int[]>,
+ Serializable {
+ /** Serializable version identifier. */
+ private static final long serialVersionUID = 20170520L;
+ /** Size of the set from which combinations are drawn. */
+ private final int n;
+ /** Number of elements in each combination. */
+ private final int k;
+
+ /**
+ * @param n Size of the set from which subsets are selected.
+ * @param k Size of the subsets to be enumerated.
+ */
+ public LexicographicComparator(int n,
+ int k) {
+ this.n = n;
+ this.k = k;
+ }
+
+ /**
+ * Gets the size of the set from which combinations are drawn.
+ *
+ * @return the size of the universe.
+ */
+ public int getN() {
+ return n;
+ }
+
+ /**
+ * Gets the number of elements in each combination.
+ *
+ * @return the size of the subsets.
+ */
+ public int getK() {
+ return k;
+ }
+
+ /**
+ * {@inheritDoc}
+ *
+ * @throws IllegalArgumentException if the array lengths are not
+ * equal to {@code k}.
+ * @throws IllegalArgumentException if an element of the array is not
+ * within the interval [0, {@code n}).
+ */
+ @Override
+ public int compare(int[] c1,
+ int[] c2) {
+ if (c1.length != k) {
+ throw new CombinatoricsException(CombinatoricsException.MISMATCH, c1.length, k);
+ }
+ if (c2.length != k) {
+ throw new CombinatoricsException(CombinatoricsException.MISMATCH, c2.length, k);
+ }
+
+ // Method "lexNorm" works with ordered arrays.
+ final int[] c1s = Arrays.copyOf(c1, k);
+ final int[] c2s = Arrays.copyOf(c2, k);
+ Arrays.sort(c1s);
+ Arrays.sort(c2s);
+
+ final long v1 = lexNorm(c1s);
+ final long v2 = lexNorm(c2s);
+
+ if (v1 < v2) {
+ return -1;
+ } else if (v1 > v2) {
+ return 1;
+ } else {
+ return 0;
+ }
+ }
+
+ /**
+ * Computes the value (in base 10) represented by the digit
+ * (interpreted in base {@code n}) in the input array in reverse
+ * order.
+ *
+ * @param c Input array.
+ * @return the lexicographic norm.
+ * @throws IllegalArgumentException if an element of the array is not
+ * within the interval [0, {@code n}).
+ */
+ private long lexNorm(int[] c) {
+ long ret = 0;
+ for (int i = 0; i < c.length; i++) {
+ final int digit = c[i];
+ if (digit < 0 ||
+ digit >= n) {
+ throw new CombinatoricsException(CombinatoricsException.OUT_OF_RANGE, digit, 0, n - 1);
+ }
+
+ ret += c[i] * ArithmeticUtils.pow(n, i);
+ }
+ return ret;
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/CombinatoricsException.java
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/CombinatoricsException.java b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/CombinatoricsException.java
new file mode 100644
index 0000000..6514293
--- /dev/null
+++ b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/CombinatoricsException.java
@@ -0,0 +1,55 @@
+/*
+ * 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.numbers.combinatorics;
+
+import java.text.MessageFormat;
+
+/**
+ * Package private exception class with constants for frequently used messages.
+ */
+class CombinatoricsException extends IllegalArgumentException {
+ /** Error message for "out of range" condition. */
+ static final String OUT_OF_RANGE = "Number {0} is out of range [{1}, {2}]";
+ /** Error message for "out of range" condition. */
+ static final String NEGATIVE = "Number {0} is negative";
+ /** Error message for "mismatch" condition. */
+ static final String MISMATCH = "Expected {1} but was {0}";
+
+ /** Serializable version identifier. */
+ private static final long serialVersionUID = 20170515L;
+
+ /** Arguments for formatting the message. */
+ protected Object[] formatArguments;
+
+ /**
+ * Create an exception where the message is constructed by applying
+ * the {@code format()} method from {@code java.text.MessageFormat}.
+ *
+ * @param message the exception message with replaceable parameters
+ * @param formatArguments the arguments for formatting the message
+ */
+ CombinatoricsException(String message, Object... formatArguments) {
+ super(message);
+ this.formatArguments = formatArguments;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public String getMessage() {
+ return MessageFormat.format(super.getMessage(), formatArguments);
+ }
+}
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/Factorial.java
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/Factorial.java b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/Factorial.java
new file mode 100644
index 0000000..714830e
--- /dev/null
+++ b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/Factorial.java
@@ -0,0 +1,53 @@
+/*
+ * 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.numbers.combinatorics;
+
+/**
+ * <a href="http://mathworld.wolfram.com/Factorial.html">Factorial of a number</a>.
+ */
+public class Factorial {
+ /** All long-representable factorials */
+ static final long[] FACTORIALS = new long[] {
+ 1L, 1L, 2L,
+ 6L, 24L, 120L,
+ 720L, 5040L, 40320L,
+ 362880L, 3628800L, 39916800L,
+ 479001600L, 6227020800L, 87178291200L,
+ 1307674368000L, 20922789888000L, 355687428096000L,
+ 6402373705728000L, 121645100408832000L, 2432902008176640000L
+ };
+
+ /**
+ * Computes the factorial of {@code n}.
+ *
+ * @param n Argument.
+ * @return {@code n!}
+ * @throws IllegalArgumentException if {@code n < 0}.
+ * @throws IllegalArgumentException if {@code n > 20} (the factorial
+ * value is too large to fit in a {@code long}).
+ */
+ public static long value(int n) {
+ if (n < 0 ||
+ n > 20) {
+ throw new CombinatoricsException(CombinatoricsException.OUT_OF_RANGE,
+ n, 0, 20);
+ }
+
+ return FACTORIALS[n];
+ }
+}
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/FactorialDouble.java
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/FactorialDouble.java b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/FactorialDouble.java
new file mode 100644
index 0000000..df6942f
--- /dev/null
+++ b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/FactorialDouble.java
@@ -0,0 +1,134 @@
+/*
+ * 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.numbers.combinatorics;
+
+/**
+ * Class for computing the natural logarithm of the
+ * <a href="http://mathworld.wolfram.com/Factorial.html">factorial of a number</a>.
+ * It allows to allocate a cache of precomputed values.
+ */
+public class FactorialDouble {
+ /**
+ * Size of precomputed factorials.
+ * @see Factorial
+ */
+ private static final int FACTORIALS_LONG_CACHE_SIZE = 21;
+ /**
+ * Precomputed values of the function: {@code factorialsDouble[i] = i!}.
+ */
+ private final double[] factorialsDouble;
+
+ /**
+ * Creates an instance, reusing the already computed values if available.
+ *
+ * @param numValues Number of values of the function to compute.
+ * @param cache Cached values.
+ * @throw IllegalArgumentException if {@code n < 0}.
+ */
+ private FactorialDouble(int numValues,
+ double[] cache) {
+ if (numValues < 0) {
+ throw new CombinatoricsException(CombinatoricsException.NEGATIVE, numValues);
+ }
+
+ factorialsDouble = new double[numValues];
+ // Initialize first two entries.
+ for (int i = 0, max = numValues < 2 ? numValues : 2;
+ i < max; i++) {
+ factorialsDouble [i] = 1;
+ }
+
+ final int beginCopy = 2;
+ final int endCopy = cache == null || cache.length <= beginCopy ?
+ beginCopy : cache.length <= numValues ?
+ cache.length : numValues;
+
+ // Copy available values.
+ for (int i = beginCopy; i < endCopy; i++) {
+ factorialsDouble[i] = cache[i];
+ }
+
+ // Precompute.
+ for (int i = endCopy; i < numValues; i++) {
+ factorialsDouble[i] = i * factorialsDouble[i - 1];
+ }
+ }
+
+ /**
+ * Creates an instance with no precomputed values.
+ * @return instance with no precomputed values
+ */
+ public static FactorialDouble create() {
+ return new FactorialDouble(0, null);
+ }
+
+ /**
+ * Creates an instance with the specified cache size.
+ *
+ * @param cacheSize Number of precomputed values of the function.
+ * @return a new instance where {@code cacheSize} values have been
+ * precomputed.
+ * @throws IllegalArgumentException if {@code cacheSize < 0}.
+ */
+ public FactorialDouble withCache(final int cacheSize) {
+ return new FactorialDouble(cacheSize,
+ factorialsDouble);
+ }
+
+ /**
+ * Computes the factorial of {@code n}.
+ * The result should be small enough to fit into a {@code double}: The
+ * largest {@code n} for which {@code n!} does not exceed
+ * {@code Double.MAX_VALUE} is 170. {@code Double.POSITIVE_INFINITY} is
+ * returned for {@code n > 170}.
+ *
+ * @param n Argument.
+ * @return {@code n!}
+ * @throws IllegalArgumentException if {@code n < 0}.
+ */
+ public double value(int n) {
+ if (n < FACTORIALS_LONG_CACHE_SIZE) {
+ return Factorial.value(n);
+ }
+
+ if (n < factorialsDouble.length) {
+ // Use cache of precomputed values.
+ return factorialsDouble[n];
+ }
+
+ return compute(n);
+ }
+
+ /**
+ * @param n Argument.
+ * @return {@code n!} (approximated as a {@code double}).
+ */
+ private double compute(int n) {
+ int start = 2;
+ double result = 1;
+
+ if (factorialsDouble.length > 2) {
+ result = factorialsDouble[factorialsDouble.length - 1];
+ start = factorialsDouble.length;
+ }
+ for (int i = start; i <= n; i++) {
+ result *= i;
+ }
+ return result;
+ }
+}
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/LogBinomialCoefficient.java
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/LogBinomialCoefficient.java b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/LogBinomialCoefficient.java
new file mode 100644
index 0000000..d943fae
--- /dev/null
+++ b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/LogBinomialCoefficient.java
@@ -0,0 +1,83 @@
+/*
+ * 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.numbers.combinatorics;
+
+/**
+ * Natural logarithm of the <a href="http://mathworld.wolfram.com/BinomialCoefficient.html">
+ * binomial coefficient</a>.
+ * It is "{@code n choose k}", the number of {@code k}-element subsets that
+ * can be selected from an {@code n}-element set.
+ */
+public class LogBinomialCoefficient {
+ /**
+ * Computes the logarithm of the binomial coefficient.
+ * The largest value of {@code n} for which all coefficients can
+ * fit into a {@code long} is 66.
+ *
+ * @param n Size of the set.
+ * @param k Size of the subsets to be counted.
+ * @return {@code log(n choose k)}.
+ * @throws IllegalArgumentException if {@code n < 0}.
+ * @throws IllegalArgumentException if {@code k > n}.
+ * @throws IllegalArgumentException if the result is too large to be
+ * represented by a {@code long}.
+ */
+ public static double value(int n, int k) {
+ BinomialCoefficient.checkBinomial(n, k);
+
+ if (n == k ||
+ k == 0) {
+ return 0;
+ }
+ if (k == 1 ||
+ k == n - 1) {
+ return Math.log(n);
+ }
+
+ // For values small enough to do exact integer computation,
+ // return the log of the exact value.
+ if (n < 67) {
+ return Math.log(BinomialCoefficient.value(n, k));
+ }
+
+ // Logarithm of "BinomialCoefficientDouble" for values that
+ // will not overflow.
+ if (n < 1030) {
+ return Math.log(BinomialCoefficientDouble.value(n, k));
+ }
+
+ if (k > n / 2) {
+ return value(n, n - k);
+ }
+
+ // Sum for values that could overflow.
+ double logSum = 0;
+
+ // n! / (n - k)!
+ for (int i = n - k + 1; i <= n; i++) {
+ logSum += Math.log(i);
+ }
+
+ // Divide by k!
+ for (int i = 2; i <= k; i++) {
+ logSum -= Math.log(i);
+ }
+
+ return logSum;
+ }
+}
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/LogFactorial.java
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/LogFactorial.java b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/LogFactorial.java
new file mode 100644
index 0000000..db2c1dd
--- /dev/null
+++ b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/LogFactorial.java
@@ -0,0 +1,115 @@
+/*
+ * 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.numbers.combinatorics;
+
+import org.apache.commons.numbers.gamma.LogGamma;
+
+/**
+ * Class for computing the natural logarithm of the factorial of a number.
+ * It allows to allocate a cache of precomputed values.
+ * In case of cache miss, computation is performed by a call to
+ * {@link LogGamma#value(double)}.
+ */
+public class LogFactorial {
+ /**
+ * Size of precomputed factorials.
+ * @see Factorial
+ */
+ private static final int FACTORIALS_CACHE_SIZE = 21;
+ /**
+ * Precomputed values of the function: {@code logFactorials[i] = Math.log(i!)}.
+ */
+ private final double[] logFactorials;
+
+ /**
+ * Creates an instance, reusing the already computed values if available.
+ *
+ * @param numValues Number of values of the function to compute.
+ * @param cache Cached values.
+ * @throw IllegalArgumentException if {@code n < 0}.
+ */
+ private LogFactorial(int numValues,
+ double[] cache) {
+ if (numValues < 0) {
+ throw new CombinatoricsException(CombinatoricsException.NEGATIVE, numValues);
+ }
+
+ logFactorials = new double[numValues];
+
+ final int beginCopy = 2;
+ final int endCopy = cache == null || cache.length <= beginCopy ?
+ beginCopy : cache.length <= numValues ?
+ cache.length : numValues;
+
+ // Copy available values.
+ for (int i = beginCopy; i < endCopy; i++) {
+ logFactorials[i] = cache[i];
+ }
+
+ // Precompute.
+ for (int i = endCopy; i < numValues; i++) {
+ logFactorials[i] = logFactorials[i - 1] + Math.log(i);
+ }
+ }
+
+ /**
+ * Creates an instance with no precomputed values.
+ * @return instance with no precomputed values
+ */
+ public static LogFactorial create() {
+ return new LogFactorial(0, null);
+ }
+
+ /**
+ * Creates an instance with the specified cache size.
+ *
+ * @param cacheSize Number of precomputed values of the function.
+ * @return a new instance where {@code cacheSize} values have been
+ * precomputed.
+ * @throws IllegalArgumentException if {@code cacheSize < 0}.
+ */
+ public LogFactorial withCache(final int cacheSize) {
+ return new LogFactorial(cacheSize, logFactorials);
+ }
+
+ /**
+ * Computes \( log_e(n!) \).
+ *
+ * @param n Argument.
+ * @return {@code log(n!)}.
+ * @throws IllegalArgumentException if {@code n < 0}.
+ */
+ public double value(int n) {
+ if (n < 0) {
+ throw new CombinatoricsException(CombinatoricsException.NEGATIVE, n);
+ }
+
+ // Use cache of precomputed values.
+ if (n < logFactorials.length) {
+ return logFactorials[n];
+ }
+
+ // Use cache of precomputed factorial values.
+ if (n < FACTORIALS_CACHE_SIZE) {
+ return Math.log(Factorial.value(n));
+ }
+
+ // Delegate.
+ return LogGamma.value(n + 1);
+ }
+}
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/package-info.java
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/package-info.java b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/package-info.java
new file mode 100644
index 0000000..9fdc00d
--- /dev/null
+++ b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/package-info.java
@@ -0,0 +1,21 @@
+/*
+ * 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.
+ */
+
+/**
+ * Combinatorics.
+ */
+package org.apache.commons.numbers.combinatorics;
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/site/site.xml
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/src/site/site.xml b/commons-numbers-combinatorics/src/site/site.xml
new file mode 100644
index 0000000..6603587
--- /dev/null
+++ b/commons-numbers-combinatorics/src/site/site.xml
@@ -0,0 +1,35 @@
+<?xml version="1.0" encoding="ISO-8859-1"?>
+<!--
+ 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.
+-->
+<project name="Numbers">
+ <bannerRight>
+ <name>Apache Commons Numbers</name>
+ <src>/images/commons_numbers.small.png</src>
+ <href>/index.html</href>
+ </bannerRight>
+
+ <body>
+ <menu name="Numbers Combinatorics">
+ <item name="Overview" href="index.html"/>
+ <item name="Latest API docs (development)"
+ href="apidocs/index.html"/>
+ <!--item name="Javadoc (1.0 release)"
+ href="http://commons.apache.org/rng/commons-numbers-combinatorics/javadocs/api-1.0/index.html"/-->
+ </menu>
+
+ </body>
+</project>
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/site/xdoc/index.xml
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/src/site/xdoc/index.xml b/commons-numbers-combinatorics/src/site/xdoc/index.xml
new file mode 100644
index 0000000..e9c5c66
--- /dev/null
+++ b/commons-numbers-combinatorics/src/site/xdoc/index.xml
@@ -0,0 +1,40 @@
+<?xml version="1.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.
+ -->
+
+<document>
+
+ <properties>
+ <title>Commons Numbers Combinatorics</title>
+ </properties>
+
+ <body>
+
+ <section name="Apache Commons Numbers: Number types" href="summary">
+ <p>
+ Commons Numbers provides utilities such as complex numbers and fractions.
+ </p>
+
+ <p>
+ The "combinatorics" module contains utilities such as factorial and binomial coefficients.
+ </p>
+ </section>
+
+ </body>
+
+</document>
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/BinomialCoefficientDoubleTest.java
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/BinomialCoefficientDoubleTest.java b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/BinomialCoefficientDoubleTest.java
new file mode 100644
index 0000000..404bfed
--- /dev/null
+++ b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/BinomialCoefficientDoubleTest.java
@@ -0,0 +1,106 @@
+/*
+ * 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.numbers.combinatorics;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ * Test cases for the {@link BinomialCoefficient} class.
+ */
+public class BinomialCoefficientDoubleTest {
+ /** Verify that b(0,0) = 1 */
+ @Test
+ public void test0Choose0() {
+ Assert.assertEquals(BinomialCoefficientDouble.value(0, 0), 1d, 0);
+ }
+
+ @Test
+ public void testBinomialCoefficient() {
+ final long[] bcoef5 = { 1, 5, 10, 10, 5, 1 };
+ final long[] bcoef6 = { 1, 6, 15, 20, 15, 6, 1 };
+
+ for (int n = 1; n < 10; n++) {
+ for (int k = 0; k <= n; k++) {
+ Assert.assertEquals(n + " choose " + k,
+ BinomialCoefficientTest.binomialCoefficient(n, k),
+ BinomialCoefficientDouble.value(n, k),
+ Double.MIN_VALUE);
+ }
+ }
+
+ final int[] n = { 34, 66, 100, 1500, 1500 };
+ final int[] k = { 17, 33, 10, 1500 - 4, 4 };
+ for (int i = 0; i < n.length; i++) {
+ final long expected = BinomialCoefficientTest.binomialCoefficient(n[i], k[i]);
+ Assert.assertEquals(n[i] + " choose " + k[i], expected,
+ BinomialCoefficientDouble.value(n[i], k[i]), 0.0);
+ }
+ }
+
+ @Test(expected=CombinatoricsException.class)
+ public void testBinomialCoefficientFail1() {
+ BinomialCoefficientDouble.value(4, 5);
+ }
+
+ @Test(expected=CombinatoricsException.class)
+ public void testBinomialCoefficientFail2() {
+ BinomialCoefficientDouble.value(-1, -2);
+ }
+
+ @Test
+ public void testBinomialCoefficientFail3() {
+ final double x = BinomialCoefficientDouble.value(1030, 515);
+ Assert.assertTrue("expecting infinite binomial coefficient", Double.isInfinite(x));
+ }
+
+ /**
+ * Tests correctness for large n and sharpness of upper bound in API doc
+ * JIRA: MATH-241
+ */
+ @Test
+ public void testBinomialCoefficientLarge() throws Exception {
+ // This tests all legal and illegal values for n <= 200.
+ for (int n = 0; n <= 200; n++) {
+ for (int k = 0; k <= n; k++) {
+ long exactResult = -1;
+ boolean shouldThrow = false;
+ boolean didThrow = false;
+ try {
+ BinomialCoefficient.value(n, k);
+ } catch (ArithmeticException ex) {
+ didThrow = true;
+ }
+ try {
+ exactResult = BinomialCoefficientTest.binomialCoefficient(n, k);
+ } catch (ArithmeticException ex) {
+ shouldThrow = true;
+ }
+
+ if (!shouldThrow && exactResult > 1) {
+ Assert.assertEquals(n + " choose " + k, 1.,
+ BinomialCoefficientDouble.value(n, k) / exactResult, 1e-10);
+ }
+ }
+ }
+
+ final int n = 10000;
+ final double actualOverExpected = BinomialCoefficientDouble.value(n, 3) /
+ BinomialCoefficientTest.binomialCoefficient(n, 3);
+ Assert.assertEquals(1, actualOverExpected, 1e-10);
+ }
+}
http://git-wip-us.apache.org/repos/asf/commons-numbers/blob/5b140a0e/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/BinomialCoefficientTest.java
----------------------------------------------------------------------
diff --git a/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/BinomialCoefficientTest.java b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/BinomialCoefficientTest.java
new file mode 100644
index 0000000..d1dacc6
--- /dev/null
+++ b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/BinomialCoefficientTest.java
@@ -0,0 +1,195 @@
+/*
+ * 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.numbers.combinatorics;
+
+import java.util.List;
+import java.util.ArrayList;
+import java.util.Map;
+import java.util.HashMap;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+import org.apache.commons.numbers.core.ArithmeticUtils;
+
+/**
+ * Test cases for the {@link BinomialCoefficient} class.
+ */
+public class BinomialCoefficientTest {
+ /** Cached binomial coefficients. */
+ private static final List<Map<Integer, Long>> binomialCache =
+ new ArrayList<Map<Integer, Long>>();
+
+ /** Verify that b(0,0) = 1 */
+ @Test
+ public void test0Choose0() {
+ Assert.assertEquals(BinomialCoefficient.value(0, 0), 1);
+ }
+
+ @Test
+ public void testBinomialCoefficient() {
+ final long[] bcoef5 = { 1, 5, 10, 10, 5, 1 };
+ final long[] bcoef6 = { 1, 6, 15, 20, 15, 6, 1 };
+
+ for (int i = 0; i < 6; i++) {
+ Assert.assertEquals("5 choose " + i, bcoef5[i], BinomialCoefficient.value(5, i));
+ }
+ for (int i = 0; i < 7; i++) {
+ Assert.assertEquals("6 choose " + i, bcoef6[i], BinomialCoefficient.value(6, i));
+ }
+
+ for (int n = 1; n < 10; n++) {
+ for (int k = 0; k <= n; k++) {
+ Assert.assertEquals(n + " choose " + k,
+ binomialCoefficient(n, k),
+ BinomialCoefficient.value(n, k));
+ }
+ }
+
+ final int[] n = { 34, 66, 100, 1500, 1500 };
+ final int[] k = { 17, 33, 10, 1500 - 4, 4 };
+ for (int i = 0; i < n.length; i++) {
+ final long expected = binomialCoefficient(n[i], k[i]);
+ Assert.assertEquals(n[i] + " choose " + k[i],
+ expected,
+ BinomialCoefficient.value(n[i], k[i]));
+ }
+ }
+
+ @Test(expected=CombinatoricsException.class)
+ public void testBinomialCoefficientFail1() {
+ BinomialCoefficient.value(4, 5);
+ }
+
+ @Test(expected=CombinatoricsException.class)
+ public void testBinomialCoefficientFail2() {
+ BinomialCoefficient.value(-1, -2);
+ }
+
+ @Test(expected=ArithmeticException.class)
+ public void testBinomialCoefficientFail3() {
+ BinomialCoefficient.value(67, 30);
+ }
+
+ @Test(expected=ArithmeticException.class)
+ public void testBinomialCoefficientFail4() {
+ BinomialCoefficient.value(67, 34);
+ }
+
+ @Test(expected=ArithmeticException.class)
+ public void testBinomialCoefficientFail5() {
+ BinomialCoefficient.value(700, 300);
+ }
+
+ /**
+ * Tests correctness for large n and sharpness of upper bound in API doc
+ * JIRA: MATH-241
+ */
+ @Test
+ public void testBinomialCoefficientLarge() throws Exception {
+ // This tests all legal and illegal values for n <= 200.
+ for (int n = 0; n <= 200; n++) {
+ for (int k = 0; k <= n; k++) {
+ long ourResult = -1;
+ long exactResult = -1;
+ boolean shouldThrow = false;
+ boolean didThrow = false;
+ try {
+ ourResult = BinomialCoefficient.value(n, k);
+ } catch (ArithmeticException ex) {
+ didThrow = true;
+ }
+ try {
+ exactResult = binomialCoefficient(n, k);
+ } catch (ArithmeticException ex) {
+ shouldThrow = true;
+ }
+ Assert.assertEquals(n + " choose " + k, exactResult, ourResult);
+ Assert.assertEquals(n + " choose " + k, shouldThrow, didThrow);
+ Assert.assertTrue(n + " choose " + k, (n > 66 || !didThrow));
+ }
+ }
+
+ long ourResult = BinomialCoefficient.value(300, 3);
+ long exactResult = binomialCoefficient(300, 3);
+ Assert.assertEquals(exactResult, ourResult);
+
+ ourResult = BinomialCoefficient.value(700, 697);
+ exactResult = binomialCoefficient(700, 697);
+ Assert.assertEquals(exactResult, ourResult);
+
+ final int n = 10000;
+ ourResult = BinomialCoefficient.value(n, 3);
+ exactResult = binomialCoefficient(n, 3);
+ Assert.assertEquals(exactResult, ourResult);
+
+ }
+
+ @Test(expected=CombinatoricsException.class)
+ public void testCheckBinomial1() {
+ // n < 0
+ BinomialCoefficient.checkBinomial(-1, -2);
+ }
+
+ @Test(expected=CombinatoricsException.class)
+ public void testCheckBinomial2() {
+ // k > n
+ BinomialCoefficient.checkBinomial(4, 5);
+ }
+
+ @Test
+ public void testCheckBinomial3() {
+ // OK (no exception thrown)
+ BinomialCoefficient.checkBinomial(5, 4);
+ }
+
+ /**
+ * Exact (caching) recursive implementation to test against.
+ */
+ static long binomialCoefficient(int n, int k) {
+ if (binomialCache.size() > n) {
+ final Long cachedResult = binomialCache.get(n).get(Integer.valueOf(k));
+ if (cachedResult != null) {
+ return cachedResult.longValue();
+ }
+ }
+ long result = -1;
+ if ((n == k) || (k == 0)) {
+ result = 1;
+ } else if ((k == 1) || (k == n - 1)) {
+ result = n;
+ } else {
+ // Reduce stack depth for larger values of n.
+ if (k < n - 100) {
+ binomialCoefficient(n - 100, k);
+ }
+ if (k > 100) {
+ binomialCoefficient(n - 100, k - 100);
+ }
+ result = ArithmeticUtils.addAndCheck(binomialCoefficient(n - 1, k - 1),
+ binomialCoefficient(n - 1, k));
+ }
+ if (result == -1) {
+ throw new IllegalArgumentException();
+ }
+ for (int i = binomialCache.size(); i < n + 1; i++) {
+ binomialCache.add(new HashMap<Integer, Long>());
+ }
+ binomialCache.get(n).put(Integer.valueOf(k), Long.valueOf(result));
+ return result;
+ }
+}
[Numbers] NUMBERS-29: Combinatorics utilities ported from "Commons
Math"
Posted by Gilles <gi...@harfang.homelinux.org>.
Hi.
Please review
https://issues.apache.org/jira/browse/NUMBERS-29
Regards,
Gilles
On Sun, 21 May 2017 02:07:19 -0000, erans@apache.org wrote:
> NUMBERS-29: New module for combinatorics utilities ported from
> "Commons Math".
>
>
> Project: http://git-wip-us.apache.org/repos/asf/commons-numbers/repo
> Commit:
>
> http://git-wip-us.apache.org/repos/asf/commons-numbers/commit/5b140a0e
> Tree:
> http://git-wip-us.apache.org/repos/asf/commons-numbers/tree/5b140a0e
> Diff:
> http://git-wip-us.apache.org/repos/asf/commons-numbers/diff/5b140a0e
>
> Branch: refs/heads/master
> Commit: 5b140a0e2f8bd84e8c51b67ad478486835841798
> Parents: 0ad65c0
> Author: Gilles Sadowski <gi...@harfang.homelinux.org>
> Authored: Sun May 21 04:01:34 2017 +0200
> Committer: Gilles Sadowski <gi...@harfang.homelinux.org>
> Committed: Sun May 21 04:01:34 2017 +0200
>
>
> ----------------------------------------------------------------------
> commons-numbers-combinatorics/LICENSE.txt | 201 +++++++++
> commons-numbers-combinatorics/NOTICE.txt | 6 +
> commons-numbers-combinatorics/README.md | 98 +++++
> commons-numbers-combinatorics/pom.xml | 59 +++
> .../combinatorics/BinomialCoefficient.java | 119 +++++
> .../BinomialCoefficientDouble.java | 66 +++
> .../numbers/combinatorics/Combinations.java | 434
> +++++++++++++++++++
> .../combinatorics/CombinatoricsException.java | 55 +++
> .../numbers/combinatorics/Factorial.java | 53 +++
> .../numbers/combinatorics/FactorialDouble.java | 134 ++++++
> .../combinatorics/LogBinomialCoefficient.java | 83 ++++
> .../numbers/combinatorics/LogFactorial.java | 115 +++++
> .../numbers/combinatorics/package-info.java | 21 +
> commons-numbers-combinatorics/src/site/site.xml | 35 ++
> .../src/site/xdoc/index.xml | 40 ++
> .../BinomialCoefficientDoubleTest.java | 106 +++++
> .../combinatorics/BinomialCoefficientTest.java | 195 +++++++++
> .../numbers/combinatorics/CombinationsTest.java | 194 +++++++++
> .../combinatorics/FactorialDoubleTest.java | 130 ++++++
> .../numbers/combinatorics/FactorialTest.java | 58 +++
> .../LogBinomialCoefficientTest.java | 101 +++++
> .../numbers/combinatorics/LogFactorialTest.java | 118 +++++
> 22 files changed, 2421 insertions(+)
>
> ----------------------------------------------------------------------
>
>
> [...]
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org