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
