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

[Neil Girdhar]

Beautiful!!


On Fri, Oct 11, 2013 at 6:19 PM, MRAB <python at mrabarnett.plus.com> wrote:

> 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]]
>
>
> ______________________________**_________________
> Python-ideas mailing list
> Python-ideas at python.org
> https://mail.python.org/**mailman/listinfo/python-ideas<https://mail.python.org/mailman/listinfo/python-ideas>
>
> --
>
> --- You received this message because you are subscribed to a topic in the
> Google Groups "python-ideas" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/**
> topic/python-ideas/**dDttJfkyu2k/unsubscribe<https://groups.google.com/d/topic/python-ideas/dDttJfkyu2k/unsubscribe>
> .
> To unsubscribe from this group and all its topics, send an email to
> python-ideas+unsubscribe@**googlegroups.com<python-ideas%2Bunsubscribe at googlegroups.com>
> .
> For more options, visit https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/opt_out>
> .
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20131011/8ccbdc82/attachment.html>