[Python-ideas] Fwd: Extremely weird itertools.permutations

[Tim Peters]

[Tim]
>> [MRAB, posts a beautiful solution]
>>
>> I don't really have a use for this, but it was a lovely programming
>> puzzle, so I'll include an elaborate elaboration of MRAB's algorithm
>> below.  And that's the end of my interest in this ;-)
>>
>> It doesn't require that elements be orderable or even hashable.  It
>> does require that they can be compared for equality, but it's pretty
>> clear that if we _do_ include something like this, "equality" has to
>> be pluggable.
>> ...

[MRAB]
> I posted yet another implementation after that one.

I know.  I was talking about the beautiful one ;-)  The later one
could build equivalence classes faster (than mine) in many cases, but
I don't care much about the startup costs.  I care a lot more about:

1. Avoiding searches in the recursive function; i.e., this:

         for i, item in enumerate(items):
            if item != prev_item:

Making such tests millions (billions ...) of times adds up - and
equality testing may not be cheap.  The algorithm I posted does no
item testing after the setup is done (none in its recursive function).

2. Making "equality" pluggable.  Your later algorithm bought "find
equivalence classes" speed for hashable elements by using a dict, but
a dict's notion of equality can't be changed.  So, make equality
pluggable, and that startup-time speed advantage vanishes for all but
operator.__eq__'s idea of equality.