[Python-ideas] Fwd: Extremely weird itertools.permutations
David Mertz
mertz at gnosis.cx
Sat Oct 12 00:03:48 CEST 2013
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.
On Fri, Oct 11, 2013 at 2:51 PM, Neil Girdhar <mistersheik at gmail.com> wrote:
> 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.
>>
>
>
--
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/f37c4732/attachment.html>
More information about the Python-ideas
mailing list