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

[Neil Girdhar]

> 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.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20131011/a15a6378/attachment-0001.html>