exercise: partition a list by equivalence

[Reinhold Birkenfeld]

John Machin wrote:
> Reinhold Birkenfeld wrote:
>> Reinhold Birkenfeld wrote:
>>
>> > My solution (which may not be the fastest or most effective, but
> till
>> > now is the shortest <wink> and it works):
> 
> [snip RB]
>>
>> A recursive solution (around twice as fast as the above, though very
>> slow still...)
>>
> [snip RB2]
>>
>> Another one:
>>
> 
> [snip RB3]
> 
> Dunno what data you are using for timing, but my tests suggest that RB
> is fast enough, RB3 is slightly faster, but RB2 is a real dog and
> appears to be quadratic [hint: it has that same for-for-for-update
> signature found in phase 2 of Xah's effort]. Not only that, but it
> seems to be somewhat irregular. Below are some results on trivial test
> data:
[snip]

Yes, I don't know exactly how I timed this, and I just posted the
solutions to show that there are very different solutions possible. They
are surely not using the best algorithms, as bearophile's function showed.

Reinhold