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! :-)