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

--000000000000c00e010657af3429
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi all,

org.apache.commons.collections4.iterators.PermutationIterator uses the
Steinhaus=E2=80=93Johnson=E2=80=93Trotter
<https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_al=
gorithm>
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 =3D 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 th=
e
   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

--000000000000c00e010657af3429--