Following up on the proposal below. Implementation is up:
*JIRA*: https://issues.apache.org/jira/browse/COLLECTIONS-897 *PR*: https://github.com/apache/commons-collections/pull/721 The PR is a first-time contribution, so CI is waiting on a maintainer to approve the workflow run. Could someone with commit-access approve it? Locally mvn passes tests.Happy to adjust the API shape - in particular whether this belongs as a standalone class or an IteratorUtils factory method. Best, Igor. On Tue, Jul 28, 2026 at 8:31 PM Igor r <[email protected]> wrote: > Hi all, > > org.apache.commons.collections4.iterators.PermutationIterator uses the > Steinhaus–Johnson–Trotter > <https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm> > algorithm and yields exactly n! permutations, treating equal elements as > distinct. For [A, B, B] it emits six lists, each distinct permutation > appearing twice. > > Would a complementary iterator based on Knuth's Algorithm L (the algorithm > behind C++ std::next_permutation > <https://en.cppreference.com/cpp/algorithm/next_permutation>) be in > scope? It differs in three ways: > > - emits only distinct permutations > - emits them in lexicographic order, which is deterministic and > reproducible > - accepts an optional Comparator to define that order > > Iterator<List<Character>> iterator = new > NextPermutationIterator<>(List.of('A', 'B', > 'B'));iterator.forEachRemaining(System.out::println);// prints out// [A, B, > B]// [B, A, B]// [B, B, A] > > Two design questions I'd like input on before writing anything: > > 1. Separate class, or an option/factory method on the existing > PermutationIterator? > 2. Should the constructor sort the input first? Algorithm L enumerates > forward from the given arrangement, so starting from [B, A, B] yields > only two lists. Sorting up front would make the output depend only on the > multiset, which seems the more natural contract for an Iterator, but > it diverges from std::next_permutation. > > I have a working implementation written for a personal project: > https://github.com/hextriclosan/algorithm/blob/main/src/main/java/io/github/hextriclosan/algorithm/iterators/NextPermutationIterator.java > . I'm the sole author and would be glad to contribute it under the Apache > License 2.0, reworked to match Commons style, the project's Java baseline, > and AbstractIteratorTest. > > Best regards, > Igor Rudenko > https://github.com/hextriclosan > > >
