This is an automated email from the ASF dual-hosted git repository.
asf-gitbox-commits pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-numbers.git
The following commit(s) were added to refs/heads/master by this push:
new 7834d1d7 NUMBERS-215: Iterate over partitions that contain k subsets.
7834d1d7 is described below
commit 7834d1d7d58c295c9394d78287421d339a9d0ac5
Author: Gilles Sadowski <[email protected]>
AuthorDate: Thu Sep 17 04:12:56 2026 +0200
NUMBERS-215: Iterate over partitions that contain k subsets.
---
.../commons/numbers/combinatorics/Stirling.java | 355 +++++++++++++++++++++
.../numbers/combinatorics/StirlingTest.java | 98 ++++++
2 files changed, 453 insertions(+)
diff --git
a/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/Stirling.java
b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/Stirling.java
index bad11ac5..33391544 100644
---
a/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/Stirling.java
+++
b/commons-numbers-combinatorics/src/main/java/org/apache/commons/numbers/combinatorics/Stirling.java
@@ -17,6 +17,16 @@
package org.apache.commons.numbers.combinatorics;
+import java.util.List;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.Spliterator;
+import java.util.Spliterators;
+import java.util.NoSuchElementException;
+import java.util.stream.Stream;
+import java.util.stream.StreamSupport;
+
/**
* Computation of <a
href="https://en.wikipedia.org/wiki/Stirling_number";>Stirling numbers</a>.
*
@@ -292,4 +302,349 @@ public final class Stirling {
((b >>> 1) * a) >>> 1 :
((a >>> 1) * b) >>> 1;
}
+
+ // CHECKSTYLE: stop regex
+ /**
+ * From a collection of {@code n} items, generates all partitions that
contains {@code k} subsets.
+ *
+ * For example:
+ * <pre>{@code
+ * Stirling.S2.of(4, 2)
+ * .stream()
+ * .forEach(p -> System.out.println(java.util.Arrays.deepToString(p)));
+ * }</pre>
+ * will output
+ * <pre>
+ * [[0, 1, 2], [3]]
+ * [[0, 1, 3], [2]]
+ * [[0, 1], [2, 3]]
+ * [[0, 2, 3], [1]]
+ * [[0, 2], [1, 3]]
+ * [[0, 3], [1, 2]]
+ * [[0], [1, 2, 3]]
+ * </pre>
+ *
+ * <p>
+ * Method {@link #get() S2.of(n, k).get()} returns the number of
partitions.
+ * </p>
+ *
+ * <p>
+ * A <a
href="https://mathworld.wolfram.com/RestrictedGrowthString.html";>restrictive
growth string
+ * (RGS)</a> is used internally. RGS uses integers to represent items:
Position (index) in the
+ * RGS array is the same as in the original list to be partitioned, value
is the "group" to which
+ * this element belongs in a given partition.
+ * </p>
+ */
+ // CHECKSTYLE: resume regex
+ public static final class S2 {
+ /** Number of sublists in every partition (aka "k"). */
+ private final int numberOfSubsets;
+ /** Number of partitions. */
+ private final long stirlingS2;
+ /** Number of elements in the original list (aka "n"). */
+ private final int numberOfElements;
+ /** Difference between the number of items and the required number of
subsets. */
+ private final int nMinusK;
+ /** Helper .*/
+ private final int nMinusOne;
+ /** Helper .*/
+ private final int kMinusOne;
+
+ /**
+ * Constructor.
+ *
+ * @param n Number of elements.
+ * @param k Number of sublists in each partition.
+ * @throws IllegalArgumentException if {@code n < 0}, {@code k < 0} or
{@code k > n}.
+ */
+ private S2(int n,
+ int k) {
+ stirlingS2 = stirlingS2(n, k);
+ numberOfElements = n;
+ numberOfSubsets = k;
+ nMinusK = n - k;
+ nMinusOne = n - 1;
+ kMinusOne = k - 1;
+ }
+
+ /**
+ * Factory.
+ *
+ * @param n Number of items to partition.
+ * @param k Number of sublists in each partition.
+ * @return a new instance.
+ */
+ public static S2 of(int n,
+ int k) {
+ return new S2(n, k);
+ }
+
+ /**
+ * Get the number of partitions (aka "Stirling number of the second
kind").
+ *
+ * @return the number of partitions.
+ */
+ public long get() {
+ return stirlingS2;
+ }
+
+ /**
+ * Iteration wrapped in a stream, where each element is a partition,
+ * into {@code k} subsets of a set of {@code n} elements.
+ *
+ * @return a stream (without duplicate or "null" elements).
+ */
+ public Stream<int[][]> stream() {
+ return streamInternal(partitionGenerator());
+ }
+
+ /**
+ * Factory method for iterating on the partitions of the given list
+ * of {@code items}.
+ *
+ * @param items Items to be partitioned.
+ * @param k Number of sublists in each partition.
+ * @return a stream (without duplicate or "null" elements).
+ *
+ * @param <T> Item type.
+ */
+ public static <T> Stream<List<List<T>>> stream(List<T> items,
+ int k) {
+ return of(items.size(), k).stream().map(o -> mapPartition(o,
items, k));
+ }
+
+ /**
+ * Creates a partition generator that returns each partition as
+ * indices between {@code 0} (included) and {@code n} (excluded).
+ *
+ * @return a new instance.
+ */
+ public Iterable<int[][]> partitionGenerator() {
+ return new Iterable<int[][]>() {
+ /** {@inheritDoc} */
+ @Override
+ public Iterator<int[][]> iterator() {
+ return new PartitionIterator();
+ }
+ };
+ }
+
+ // Commented out: Should RGS functionality be implemented in a
dedicated class?
+ // /**
+ // * Creates a partition generator that returns each partition as a
list
+ // * of {@code n} elements whose value, between {@code 0} (included)
and
+ // * {@code k} (excluded), indicates to which subsets that element
belongs.
+ // *
+ // * @return a new instance.
+ // */
+ // public Iterable<int[]> restrictedGrowthStringGenerator() {
+ // return new Iterable<int[]>() {
+ // /** {@inheritDoc} */
+ // @Override
+ // public Iterator<int[]> iterator() {
+ // return new RestrictedGrowthStringIterator();
+ // }
+ // };
+ // }
+
+ /**
+ * Converts {@link Iterable} to {@link Stream}.
+ *
+ * @param gen Partition generator.
+ * @return a stream (without duplicate or "null" elements).
+ *
+ * @param <T> Partition representation.
+ */
+ private <T> Stream<T> streamInternal(Iterable<T> gen) {
+ final int characteristics = Spliterator.DISTINCT |
Spliterator.NONNULL;
+ return
StreamSupport.stream(Spliterators.spliterator(gen.iterator(),
+ stirlingS2,
+
characteristics),
+ false);
+ }
+
+ /**
+ * Maps a given partition to a user-defined list of objects.
+ *
+ * @param p Partition.
+ * @param items List of objects.
+ * @param k Number of sublists.
+ * @return the mapped partition.
+ *
+ * @param <T> Item type.
+ */
+ private static <T> List<List<T>> mapPartition(int[][] p,
+ List<T> items,
+ int k) {
+ final List<List<T>> out = new ArrayList<>(k);
+
+ for (int[] subset : p) {
+ final List<T> customSubset = new ArrayList<>(subset.length);
+
+ for (int i : subset) {
+ customSubset.add(items.get(i));
+ }
+
+ out.add(customSubset);
+ }
+
+ return out;
+ }
+
+ /**
+ * Iterator.
+ */
+ private final class PartitionIterator implements Iterator<int[][]> {
+ /** Delegate to RGS implementation. */
+ private final RestrictedGrowthStringIterator delegate = new
RestrictedGrowthStringIterator();
+
+ /** {@inheritDoc} */
+ @Override
+ public boolean hasNext() {
+ return delegate.hasNext();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public int[][] next() {
+ return rgs2partition(delegate.next());
+ }
+
+ /**
+ * Maps a given RGS to a list of indices.
+ *
+ * @param rgs RGS.
+ * @return the partition.
+ */
+ private int[][] rgs2partition(int[] rgs) {
+ // Size of every subsets of the partition described by "rgs".
+ final int[] sizes = new int[numberOfSubsets];
+ for (int i = 0; i < numberOfElements; i++) {
+ ++sizes[rgs[i]];
+ }
+
+ final int[][] out = new int[numberOfSubsets][];
+ for (int i = 0; i < numberOfSubsets; i++) {
+ out[i] = new int[sizes[i]];
+ }
+
+ final int[] counts = new int[numberOfSubsets];
+ for (int i = 0; i < numberOfElements; i++) {
+ final int groupIdx = rgs[i];
+ out[groupIdx][counts[groupIdx]++] = i;
+ }
+
+ return out;
+ }
+ }
+
+ /**
+ * Iterator.
+ */
+ private final class RestrictedGrowthStringIterator implements
Iterator<int[]> {
+ /** RGS array (current state). */
+ private final int[] rgs = new int[numberOfElements];
+ /** RGS array (current state). */
+ private final int[] maxRgs = new int[numberOfElements];
+ /** Current partition. */
+ private final int[] currentRGS = new int[numberOfElements];
+ /** Number of generated partitions. */
+ private long partitionCount = 0;
+ /** Whether there is another partition. */
+ private boolean hasNext = true;
+
+ /**
+ * Constructor.
+ */
+ /* package-private */ RestrictedGrowthStringIterator() {
+ // Initialize the first valid lexicographical RGS matching
k-subsets.
+ for (int i = nMinusK + 1; i < numberOfElements; i++) {
+ rgs[i] = i - nMinusK;
+ }
+ for (int i = 1; i < numberOfElements; i++) {
+ final int iMinusOne = i - 1;
+ maxRgs[i] = Math.max(maxRgs[iMinusOne],
+ rgs[iMinusOne]);
+ }
+
+ calculateNext();
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public boolean hasNext() {
+ return hasNext;
+ }
+
+ /** {@inheritDoc} */
+ @Override
+ public int[] next() {
+ if (!hasNext) {
+ throw new NoSuchElementException();
+ }
+
+ // Copy to prevent exposing internal data.
+ final int[] c = Arrays.copyOf(currentRGS, numberOfElements);
+
+ calculateNext();
+
+ return c;
+ }
+
+ /** Generates next partition. */
+ private void calculateNext() {
+ hasNext = partitionCount < stirlingS2;
+
+ if (numberOfElements > 0) {
+ while (true) {
+ if (maxRgs[nMinusOne] == kMinusOne ||
+ rgs[nMinusOne] == kMinusOne) { // Partition
contains "k" blocks.
+ build();
+ updateRgs();
+ return;
+ }
+
+ updateRgs();
+ }
+ } else {
+ build();
+ }
+ }
+
+ /** Updates RGS. */
+ private void updateRgs() {
+ int i = nMinusOne;
+ while (i > 0) {
+ if (rgs[i] < kMinusOne &&
+ rgs[i] <= maxRgs[i]) {
+ ++rgs[i];
+ break;
+ }
+ --i;
+ }
+
+ if (i == 0) {
+ return;
+ }
+
+ Arrays.fill(rgs, i + 1, numberOfElements, 0);
+
+ for (int j = i; j < numberOfElements; j++) {
+ final int jMinusOne = j - 1;
+ maxRgs[j] = Math.max(maxRgs[jMinusOne],
+ rgs[jMinusOne]);
+ }
+ }
+
+ /**
+ * Generates state to be returned by {@link #next()}.
+ */
+ private void build() {
+ System.arraycopy(rgs, 0, currentRGS, 0, numberOfElements);
+
+ // Keep count to prevent infinite loop in "calculateNext()".
+ ++partitionCount;
+ }
+ }
+ }
}
diff --git
a/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/StirlingTest.java
b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/StirlingTest.java
index 67af0ca2..d6b49a41 100644
---
a/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/StirlingTest.java
+++
b/commons-numbers-combinatorics/src/test/java/org/apache/commons/numbers/combinatorics/StirlingTest.java
@@ -16,7 +16,12 @@
*/
package org.apache.commons.numbers.combinatorics;
+import java.util.List;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
import java.util.stream.Stream;
+import java.util.stream.Collectors;
import org.apache.commons.numbers.core.ArithmeticUtils;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
@@ -360,4 +365,97 @@ class StirlingTest {
void testStirlingS2Overflow(int n, int k) {
Assertions.assertThrows(ArithmeticException.class, () ->
Stirling.stirlingS2(n, k));
}
+
+ @Test
+ void testS2Get() {
+ final int n = 23;
+ final int k = 17;
+ Assertions.assertEquals(Stirling.stirlingS2(n, k),
+ Stirling.S2.of(n, k).get());
+ }
+
+ @Test
+ void testS2PartitionGeneration() {
+ Assertions.assertEquals(1, s2PartitionGenerator(2, 1).size());
+ Assertions.assertEquals(1, s2PartitionGenerator(2, 2).size());
+ Assertions.assertEquals(1, s2PartitionGenerator(3, 1).size());
+ Assertions.assertEquals(3, s2PartitionGenerator(3, 2).size());
+ Assertions.assertEquals(1, s2PartitionGenerator(3, 3).size());
+ Assertions.assertEquals(1, s2PartitionGenerator(4, 1).size());
+ Assertions.assertEquals(7, s2PartitionGenerator(4, 2).size());
+ Assertions.assertEquals(6, s2PartitionGenerator(4, 3).size());
+ Assertions.assertEquals(1, s2PartitionGenerator(4, 4).size());
+ Assertions.assertEquals(1, s2PartitionGenerator(5, 1).size());
+ Assertions.assertEquals(15, s2PartitionGenerator(5, 2).size());
+ Assertions.assertEquals(25, s2PartitionGenerator(5, 3).size());
+ Assertions.assertEquals(10, s2PartitionGenerator(5, 4).size());
+ Assertions.assertEquals(1, s2PartitionGenerator(5, 5).size());
+ }
+
+ @Test
+ void testS2ItemsStream() {
+ final String a = "A";
+ final String b = "B";
+ final String c = "C";
+ final List<String> items = new ArrayList<>();
+ items.add(a);
+ items.add(b);
+ items.add(c);
+ final List<List<List<String>>> out = Stirling.S2.stream(items, 2)
+ .collect(Collectors.toList());
+
+ Assertions.assertEquals(3, out.size());
+
+ List<List<String>> part = out.get(0);
+ Assertions.assertEquals(a, part.get(0).get(0));
+ Assertions.assertEquals(b, part.get(0).get(1));
+ Assertions.assertEquals(c, part.get(1).get(0));
+
+ part = out.get(1);
+ Assertions.assertEquals(a, part.get(0).get(0));
+ Assertions.assertEquals(c, part.get(0).get(1));
+ Assertions.assertEquals(b, part.get(1).get(0));
+
+ part = out.get(2);
+ Assertions.assertEquals(a, part.get(0).get(0));
+ Assertions.assertEquals(b, part.get(1).get(0));
+ Assertions.assertEquals(c, part.get(1).get(1));
+ }
+
+ @Test
+ void testS2PartitionGenerationEmptyList() {
+ Assertions.assertEquals(1, s2PartitionGenerator(0, 0).size());
+ }
+
+ @Test
+ void testS2MoreRequiredSubsetThanItems() {
+ Assertions.assertThrows(IllegalArgumentException.class,
+ () -> s2PartitionGenerator(2, 3));
+ }
+
+ @Test
+ void testS2NegativeK() {
+ Assertions.assertThrows(IllegalArgumentException.class,
+ () -> Stirling.S2.of(3, -1));
+ }
+
+ @Test
+ void testS2InvalidNext() {
+ Assertions.assertThrows(NoSuchElementException.class,
+ () -> {
+ final Iterator<int[][]> s =
+ Stirling.S2.of(5,
5).partitionGenerator().iterator();
+ s.next(); // OK.
+ s.next(); // Must fail.
+ });
+ }
+
+ /**
+ * @param n Number of items.
+ * @param k Number of sublists.
+ */
+ private List<int[][]> s2PartitionGenerator(int n,
+ int k) {
+ return Stirling.S2.of(n, k).stream().collect(Collectors.toList());
+ }
}
