I have been reading about algorithms like Steinhaus-Johnson-Trotter and Heap to generate permutations, including Sedgewick’s paper on the subject. But it seems these all work when all elements are distinct. What happens if I have elements that can share values, and I want to filter out the portion of the N! exhaustive permutations that are observationally repeats?
I heard about the lexicographic approach. There’s even two functions in the C++ library concerning them. But what if the data is unordered; that is, I only have an equivalence predicate, not an ordering one.
Could those algorithms that Sedgewick looked at be adapted to skip over equivalent permutations (besides the first, of course)?
There is an existing query, “distinct permutations of a list with repetitions,” that may come close, but its problem and solution set are in R, and not general.