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

[David Mertz]

OK, you're right.  Just using set() has bad worst case memory costs.  I was
thinking of the case where there actually WERE lots of equalities, and
hence the resulting list would be much smaller than N!.  But of course
that's not general.  It takes more than one line, but here's an incremental
version:

def nonredundant_permutations(seq):
    seq = sorted(seq)
    last = None
    for perm in permutations(seq):
        if perm != last:
            yield perm
            last = perm


On Fri, Oct 11, 2013 at 2:35 PM, Neil Girdhar <mistersheik at gmail.com> wrote:

> > Moreover, I don't think the runtime behavior of my one-liner is
> particularly costly…
>
> It is *extremely* costly.  There can be n! permutations, so for even, say,
> 12 elements, you are looking at many gigabytes of memory needlessly used.
>  One big motivator for itertools is not to have to do this.  I'm curious
> how you would solve this problem:
> https://www.kattis.com/problems/industrialspy  efficiently in Python.  I
> did it by using a unique-ifying generator, but ideally this would not be
> necessary.  Ideally, Python would do exactly what C++ does with
> next_permutation.
>
> Best,
>
> Neil
>
>
> On Fri, Oct 11, 2013 at 4:27 PM, David Mertz <mertz at gnosis.cx> wrote:
>
>> Andrew & Neil (or whoever):
>>
>> Is this *really* what you want:
>>
>>  >>> from itertools import permutations
>> >>> def nonredundant_permutations(seq):
>> ...     return list(set(permutations(seq)))
>> ...
>> >>> pprint(list(permutations([F(3,1), D(3.0), 3.0])))
>> [(Fraction(3, 1), Decimal('3'), 3.0),
>>  (Fraction(3, 1), 3.0, Decimal('3')),
>>  (Decimal('3'), Fraction(3, 1), 3.0),
>>  (Decimal('3'), 3.0, Fraction(3, 1)),
>>  (3.0, Fraction(3, 1), Decimal('3')),
>>  (3.0, Decimal('3'), Fraction(3, 1))]
>>
>> >>> pprint(list(nonredundant_permutations([F(3,1), D(3.0), 3.0])))
>> [(Fraction(3, 1), Decimal('3'), 3.0)]
>>
>> It seems odd to me to want that.  On the other hand, I provide a one-line
>> implementation of the desired behavior if anyone wants it.  Moreover, I
>> don't think the runtime behavior of my one-liner is particularly costly...
>> maybe not the best possible, but the best big-O possible.
>>
>>
>>
>> On Fri, Oct 11, 2013 at 1:19 PM, Andrew Barnert <abarnert at yahoo.com>wrote:
>>
>>> I think equality is perfectly reasonable here. The fact that {3.0, 3}
>>> only has one member seems like the obvious precedent to follow here.
>>>
>>> Sent from a random iPhone
>>>
>>> On Oct 11, 2013, at 13:02, David Mertz <mertz at gnosis.cx> wrote:
>>>
>>> What would you like this hypothetical function to output here:
>>>
>>> >>> from itertools import permutations
>>> >>> from decimal import Decimal as D
>>> >>> from fractions import Fraction as F
>>> >>> items = (3, 3.0, D(3), F(3,1), "aa", "AA".lower(), "a"+"a")
>>> >>> list(permutations(items))
>>>
>>> It's neither QUITE equality nor identity you are looking for, I think,
>>> in nonredundant_permutation():
>>>
>>> >> "aa" == "AA".lower(), "aa" is "AA".lower()
>>> (True, False)
>>> >>> "aa" == "a"+"a", "aa" is "a"+"a"
>>> (True, True)
>>> >>> D(3) == 3.0, D(3) is 3.0
>>> (True, False)
>>>
>>> On Fri, Oct 11, 2013 at 11:38 AM, Neil Girdhar <mistersheik at gmail.com>wrote:
>>>
>>>> "It is universally agreed that a list of n distinct symbols has n!
>>>> permutations. However, when the symbols are not distinct, the most common
>>>> convention, in mathematics and elsewhere, seems to be to count only
>>>> distinct permutations." —
>>>> http://stackoverflow.com/questions/6534430/why-does-pythons-itertools-permutations-contain-duplicates-when-the-original
>>>> .
>>>>
>>>>
>>>> Should we consider fixing itertools.permutations and to output only
>>>> unique permutations (if possible, although I realize that would break
>>>> code). It is completely non-obvious to have permutations returning
>>>> duplicates. For a non-breaking compromise what about adding a flag?
>>>>
>>>> Best,
>>>> Neil
>>>>
>>>> _______________________________________________
>>>> 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.
>>>
>>>
>>>
>>> --
>>> 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
>>>
>>>
>>
>>
>> --
>> 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
>>
>> --
>>
>> ---
>> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20131011/574b1eaf/attachment.html>