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

[MRAB]

On 11/10/2013 23:03, David Mertz wrote:
> Bummer.  You are right, Neil.  I saw MRAB's suggestion about sorting,
> and falsely thought that would be general; but obviously it's not.
>
> So I guess the question is whether there is ANY way to do this without
> having to accumulate a 'seen' set (which can grow to size N!).  The
> answer isn't jumping out at me, but that doesn't mean there's not a way.
>
> I don't want itertools.permutations() to do "equality filtering", but
> assuming some other function in itertools were to do that, how could it
> do so algorithmically? Or whatever, same question if it is
> itertools.permutations(seq, distinct=True) as the API.
>
Here's an implementation:

def unique_permutations(iterable, count=None, key=None):
     def perm(items, count):
         if count:
             prev_item = object()

             for i, item in enumerate(items):
                 if item != prev_item:
                     for p in perm(items[ : i] + items[i + 1 : ], count 
- 1):
                         yield [item] + p

                 prev_item = item

         else:
             yield []

     if key is None:
         key = lambda item: item

     items = sorted(iterable, key=key)

     if count is None:
         count = len(items)

     yield from perm(items, count)


And some results:

 >>> print(list("".join(x) for x in unique_permutations('aaabb', 3)))
['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba']
 >>> print(list(unique_permutations([0, 'a', 0], key=str)))
[[0, 0, 'a'], [0, 'a', 0], ['a', 0, 0]]