[Python-ideas] Fwd: Extremely weird itertools.permutations
Neil Girdhar
mistersheik at gmail.com
Fri Oct 11 23:38:27 CEST 2013
My code, which was the motivation for this suggestion:
import itertools as it
import math
def is_prime(n):
for i in range(2, int(math.floor(math.sqrt(n))) + 1):
if n % i == 0:
return False
return n >= 2
def unique(iterable): # Should not be necessary in my opinion
seen = set()
for x in iterable:
if x not in seen:
seen.add(x)
yield x
n = int(input())
for _ in range(n):
x = input()
print(sum(is_prime(int("".join(y)))
for len_ in range(1, len(x) + 1)
for y in unique(it.permutations(x, len_))
if y[0] != '0'))
On Fri, Oct 11, 2013 at 5: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.
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20131011/dba34ab5/attachment.html>
More information about the Python-ideas
mailing list