[
https://issues.apache.org/jira/browse/NUMBERS-215?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18114872#comment-18114872
]
Alex Herbert commented on NUMBERS-215:
--------------------------------------
Looking at the code for Stirling.stirlingS2(n, k) it notes that the number can
readily overflow a 64-bit signed long: "typically for n exceeding 25 and k
between 20 and n-2". So your small N must be very small otherwise you could be
iterating for a long time.
Do you have an algorithm? I see no harm in adding it but it should be
documented as potentially iterating forever (since iterating 2^63 would require
days with current CPUs).
Since 0 <= k <= n we could avoid List (and object overhead) and use a single
array of size n for each partition, with elements [0, n) labelled with a subset
in [0, k). It depends on the use case for the consumer. Do you want to have k
subsets returned, each with their element indices; or each element index assign
to a subset?
{noformat}
Stirling S2(5, 3) = 25
[0, 0, 0, 1, 2] or [0, 1, 2], [3], [4]
[0, 0, 1, 1, 2] or [0, 1], [2, 3], [4]
[0, 1, 1, 1, 2] or [0], [1, 2, 3], [4]
...
{noformat}
> Stirling partitions generator
> -----------------------------
>
> Key: NUMBERS-215
> URL: https://issues.apache.org/jira/browse/NUMBERS-215
> Project: Commons Numbers
> Issue Type: New Feature
> Components: combinatorics
> Reporter: Gilles Sadowski
> Assignee: Gilles Sadowski
> Priority: Minor
> Fix For: 1.4
>
>
> Would it be useful to provide functionality to *iterate* over the partitions
> defined by "Stirling number of the second kind" (i.e. all partitions into K
> subsets, of a set of N elements)?
> Code would be in a nested static class of the existing
> [{{Stirling}}|https://commons.apache.org/proper/commons-numbers/commons-numbers-combinatorics/apidocs/src-html/org/apache/commons/numbers/combinatorics/Stirling.html]
> class:
> {code}
> public final class Stirling {
> // ...
> public static final class S2 implements Iterable<List<List<Integer>> {
> // ...
> public static S2 of(int n, int k) {
> // ...
> }
> }
> }
> {code}
> I have a potential use case (for very small "N").
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
