[
https://issues.apache.org/jira/browse/NUMBERS-215?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18114919#comment-18114919
]
Gilles Sadowski commented on NUMBERS-215:
-----------------------------------------
bq. [...] your small N must be very small otherwise you could be iterating for
a long time.
Yes, indeed: 2, 3 and 4. ;-)
bq. Do you have an algorithm?
Even though for the above cases the partitions can be easily laid out by hand,
I thought that an algorithmic way could prove useful; so I looked for a
reference, and "Gemini" answered with an implementation. It was buggy
(infinite loop). I'll upload the refactored code in a feature branch.
bq. [...] it should be documented as potentially iterating forever [...]
Of course the documentation can stress this; but it is already fairly obvious
from the unit tests dedicated to function {{stirlingS2}}.
By the way, the nested class would be an alternative API for providing the
value of the Stirling number; (function {{stirlingS2}} could be deprecated
after moving its implementation into the new class).
bq. [...] 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). [...]
Yes; that's what they call [Restricted Growth
String|https://mathworld.wolfram.com/RestrictedGrowthString.html] (RGS) and
what Gemini uses in its suggested implementation.
It might be interesting to represent that concept separately in "Commons
Numbers" (but it's "implementation detail" for this ticket, and could be added
later).
bq. Do you want to have k subsets returned, each with their element indices; or
each element index assign to a subset?
I intended the former, as that seems most natural (and fits my use case); but
the latter could certainly be provided as an alternative.
Instead of
{code}
public static final class S2 implements Iterable<List<List<Integer>>> { /* ...
*/ }
{code}
API could be
{code}
public static final class S2 implements Iterable<int[][]> { /* ... */ }
{code}
although I'm not sure there is much to be gained since the nested arrays will
need to reallocated anyways.
However, to cater for alternative outputs (RGS vs list of subsets), the API
must be redesigned in order to provide something like
{code}
public static final class S2 {
// ...
public Iterable<List<List<Integer>>> asList() { /* ... */ }
public Iterable<int[]> asRGS() { /* ... */ }
public Iterable<int[][]> asArray() { /* ... */ }
}
{code}
> 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)
