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

[Neil Girdhar]

Unfortunately, that doesn't quite work…

list("".join(x) for x in it.permutations('aaabb', 3))
['aaa', 'aab', 'aab', 'aaa', 'aab', 'aab', 'aba', 'aba', 'abb', 'aba',
'aba', 'abb', 'aaa', 'aab', 'aab', 'aaa', 'aab', 'aab', 'aba', 'aba',
'abb', 'aba', 'aba', 'abb', 'aaa', 'aab', 'aab', 'aaa', 'aab', 'aab',
'aba', 'aba', 'abb', 'aba', 'aba', 'abb', 'baa', 'baa', 'bab', 'baa',
'baa', 'bab', 'baa', 'baa', 'bab', 'bba', 'bba', 'bba', 'baa', 'baa',
'bab', 'baa', 'baa', 'bab', 'baa', 'baa', 'bab', 'bba', 'bba', 'bba']


On Fri, Oct 11, 2013 at 5:48 PM, David Mertz <mertz at gnosis.cx> wrote:

> 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/27f95407/attachment-0001.html>