erikrose/more-itertools — pull request #36 by bbayles (2014-03-16 03:41:59+00:00)
Title: Add distinct_permutations function

`itertools.permutations(iterable)` generates all permutations of the input iterable. If there are duplicate items in the input iterable there will be duplicate items in the output sequence.

If you only need the distinct permutations you're stuck filtering out duplicates. This requires lots of memory, plus it's slower than not generating them at all.

The code for this new `distinct_permutations(iterable)` function is adapted from [this StackOverflow question](http://stackoverflow.com/questions/22431637/unique-permutation-generator/22431823#22431823). It avoids generating duplicates.

On my laptop the difference is clear...
````python
>>> from __future__ import print_function
... from itertools import permutations
... from more_itertools import distinct_permutations
... from random import randrange
... from time import clock
...
... L = 10
... iterable = "mississipp"
...
... start_time = clock()
... for perm in distinct_permutations(iterable):
... pass
... end_time = clock()
... print("New way: %s" % round(end_time - start_time, 4))
...
... start_time = clock()
... for perm in set(permutations(iterable)):
... pass
... end_time = clock()
... print("Old way: %s" % round(end_time - start_time, 4))
New way: 0.415
Old way: 4.9132
````

For an input of `mississippi` the new way takes 1.274 seconds and the old way runs out of memory.