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

[Nick Coghlan]

On 12 Oct 2013 08:45, "David Mertz" <mertz at gnosis.cx> wrote:
>
>
> I realize after reading
http://stackoverflow.com/questions/6284396/permutations-with-unique-valuesthat
my version was ALMOST right:
>
> def nonredundant_permutations(seq, r=None):
>     last = ()
>     for perm in permutations(sorted(seq), r):
>         if perm > last:
>             yield perm
>             last = perm
>
> I can't look only for inequality, but must use the actual comparison.
>
> >>> ["".join(x) for x in nonredundant_permutations('aaabb',3)]
> ['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba']
> >>> list(nonredundant_permutations([F(3,1), D(3.0), 3.0]))
> [(Fraction(3, 1), Decimal('3'), 3.0)]
>
> Of course, this approach DOES rely on the order in which
itertools.permutations() returns values.  However, it's a bit more compact
than MRAB's version.

As there is no requirement that entries in a sequence handled by
itertools.permutations be sortable, so the original question of why this
isn't done by default has been answered (the general solution risks
consuming too much memory, while the memory efficient solution constrains
the domain to only sortable sequences).

Cheers,
Nick.

>
>
>
>
> On Fri, Oct 11, 2013 at 3:23 PM, Neil Girdhar <mistersheik at gmail.com>
wrote:
>>
>> 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
>>>
>>> --
>>>
>>> --- 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.
>>> To unsubscribe from this group and all its topics, send an email to
python-ideas+unsubscribe at googlegroups.com.
>>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>>
>>
>> _______________________________________________
>> Python-ideas mailing list
>> Python-ideas at python.org
>> https://mail.python.org/mailman/listinfo/python-ideas
>>
>
>
>
> --
> Keeping medicines from the bloodstreams of the sick; food
> from the bellies of the hungry; books from the hands of the
> uneducated; technology from the underdeveloped; and putting
> advocates of freedom in prisons.  Intellectual property is
> to the 21st century what the slave trade was to the 16th.
>
> _______________________________________________
> Python-ideas mailing list
> Python-ideas at python.org
> https://mail.python.org/mailman/listinfo/python-ideas
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20131012/82e23284/attachment-0001.html>