Re: [COLLECTIONS] Lexicographic permutation iterator (Knuth's Algorithm L)

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
>
>
>