[Python-ideas] Extremely weird itertools.permutations

MRAB python at mrabarnett.plus.com
Tue Oct 15 03:17:56 CEST 2013


On 15/10/2013 01:48, Tim Peters wrote:
> [Raymond Hettinger]
>> Now that we have a good algorithm,  I'm open to adding this to itertools,
>
> I remain reluctant, because I still haven't seen a compelling use
> case.  Yes, it generates all distinct r-letter anagrams - but so what?
>   LOL ;-)  Seriously, I've written anagram programs several times in my
> life, and generating "all possible" never occurred to me because it's
> so crushingly inefficient.
>
>
>> but it would need to have a name that didn't create any confusion
>> with respect to the existing tools, perhaps something like:
>>
>>     anagrams(population, r)
>
> "anagrams" is great!  Inspired :-)
>
> What about an optional argument to define what the _user_ means by
> "equality"?  The algorithm I posted had an optional
> `equal=operator.__eq__` argument.  Else you're going to be pushed to
> add a clumsy `TransformAnagrams` later <0.4 wink>.
>
>>     Return an iterator over a all distinct r-length permutations
>>     of the population.
>>
>>     Unlike permutations(), element uniqueness is determined
>>     by value rather than by position.  Also, anagrams() makes
>>     no guarantees about the order the tuples are generated.
>
> Well, MRAB's algorithm (and my rewrite) guarantees that _if_ the
> elements support a total order, and appear in the iterable in
> non-decreasing order, then the anagrams are generated in
> non-decreasing lexicographic order.  And that may be a useful
> guarantee (hard to tell without a real use case, though!).
>
[snip]
I can see that one disadvantage of my algorithm is that the worst-case
storage requirement is O(n^2) (I think). This is because the set of
first items could have N members, the set of second items could have
N-1 members, etc. On the other hand, IMHO, the sheer number of
permutations will become a problem long before the memory requirement
does! :-)



More information about the Python-ideas mailing list