restrict permutations right at the start

This is the place for queries that don't fit in any of the other categories.

restrict permutations right at the start

I'm using Python 3.3.2.

I'm trying to generate permutations of digits 1-9 to filter it further. At the moment, I have got:

Code: Select all
`#!/usr/bin/python3from itertools import permutations as permprint(list(perm(range(1, 10))))`

This works fine. It generates a long list of tuples containing permutations of the digits. I've got a few ideas that I can't implement:
a) Is it possible to output it straight into a list of integers (not tuples)?
b) Is it possible to filter out even numbers straight away. I don't need even numbers (I don't mean digits, just numbers, eg. I don't need 987654312)

I know I can do it afterwards (ie. store all of it in a variable and then play with it) but I'd like to shorten the generation time.

Thank you.
portia

Posts: 17
Joined: Sun Apr 14, 2013 10:03 pm

Re: restrict permutations right at the start

The thing that is taking the time would be the printing not the generation here. Also if possible don't try and turn the permutations into a list; leave it as a generator.

Anyway... I think this is what you are trying to do (use range instead of xrange if using python 3):
Code: Select all
`from itertools import permutationsresults = []for perm in permutations(xrange(1,10)):    if not perm[-1]%2:        results.append(int("".join(str(num) for num in perm)))`

You could also do it in a somewhat pushing-the-limits-of-sensibility one-liner:
Code: Select all
`results = (int("".join(str(i) for i in ele)) for ele in permutations(xrange(1,10)) if not ele[-1]%2)`

-Mek
• Use code tags when posting code.
• Include any errors with your post (in code tags).
• Make examples the minimum length to demonstrate your issue.

Mekire

Posts: 1600
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

Re: restrict permutations right at the start

Thank you. It is working fine. No, I don't need a one-line but thank you, anyway!!
portia

Posts: 17
Joined: Sun Apr 14, 2013 10:03 pm

Re: restrict permutations right at the start

Hmm, actually it still includes even numbers

Code: Select all
`#!/usr/bin/python3 from itertools import permutationsresults = []for perm in permutations(range(1, 10)):    if not perm[-1] % 2:         results.append(int("".join(str(num) for num in perm)))print(results)`

Outputs:
.....
....
...
..., 987645312, 987651234, 987651324, 987651342, 987651432, 987652134, 987652314, 987653124, 987653142, 987653214, 987653412, 987654132, 987654312]

What am I doing wrong, I though it wasn't including even numbers (not perm[-1] % 2:)
portia

Posts: 17
Joined: Sun Apr 14, 2013 10:03 pm

Re: restrict permutations right at the start

Code: Select all
`>>> not 4 % 2True>>> not 5 % 2False>>> bool(4 % 2)False>>> bool(5 % 2)True`

4 % 2 evaluates to 0.
not 0 is a double negative (since 0 evaluates to false), and evaluates to true.
not 1 evalutes to false.
And so only even numbers pass your if condition.
hansn

Posts: 87
Joined: Thu Feb 21, 2013 8:46 pm

Re: restrict permutations right at the start

That's true. I swear I saw both even and odd numbers. I must be seeing things. Thank you.
portia

Posts: 17
Joined: Sun Apr 14, 2013 10:03 pm

Re: restrict permutations right at the start

I would start from strings instead of ints.
It allows you to write simpler code, and it runs much faster, at least with my setup:
Code: Select all
`>>> def perm_orig():...     results = []...     for perm in permutations(range(1, 10)):...         if perm[-1] % 2:...             results.append(int("".join(str(num) for num in perm)))...     return results...>>> def perm_stranac():...     results = []...     for perm in permutations('123456789'):...         if perm[-1] in '13579':...             results.append(int(''.join(perm)))...     return results...>>> timeit(perm_orig, number=1)1.8012697535498319>>> timeit(perm_stranac, number=1)0.3152886501488865`

Also, I would write this function as a generator.
Then, if you really need a list, you can just call list() on it.
Friendship is magic!

R.I.P. Tracy M. You will be missed.

stranac

Posts: 1592
Joined: Thu Feb 07, 2013 3:42 pm

Re: restrict permutations right at the start

Thanking you. It is faster. On a separate note, what's the simplest way of checking a single number whether it's a prime? Each site/forum I visit provides a slightly different solution. I'm just looking at the Sieve of Eratosthenes article on wikipedia but am struggling with it. I don't need to generate a whole list of primes, just check for primes the the numbers I've generated.
portia

Posts: 17
Joined: Sun Apr 14, 2013 10:03 pm

Re: restrict permutations right at the start

It depends on your needs, really.

If you don't care about speed much, i can be as simple as:
• loop through all the numbers from 2 to the square root of the number
• if it's divisible by any of those numbers, it's not prime
• if it's divisible by none of them, it's a prime

If you do need speed(which you will if you're solving Project Euler problems), then pre-generating a list of primes and doing a simple lookup is the best solution.
If you want help with it, just post your attempt here(I would recommend starting a new thread).
Friendship is magic!

R.I.P. Tracy M. You will be missed.

stranac

Posts: 1592
Joined: Thu Feb 07, 2013 3:42 pm

Re: restrict permutations right at the start

Putting the primes in a set provides much better lookup time than a list, by the way. And if you seriously need the extra space for a list instead of a set, you can do a binary search instead of a linear search.
Join the #python-forum IRC channel on irc.freenode.net for off-topic chat!

Please prefer not to PM members. The point of the forum is so that anyone can benefit. We don't want to help you over PMs/emails/Skype chats that others can't benefit from

micseydel

Posts: 2250
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

Re: restrict permutations right at the start

Thank you all. How about the below? Is that ok as a prime number checker?

Code: Select all
`  1 #!/usr/bin/python3  2 import math  3   4 num = 73  5   6   7 def isprime(n):  8     for x in range(2, int(math.sqrt(n))):  9         if n % x == 0: 10             return False 11     return True 12          13 if isprime(num): 14     print("YES, it's a prime number") 15 else: 16     print("NO, it's not a prime number")`

By the way, as suggested above, I've replaced a list with a set. Thanks
portia

Posts: 17
Joined: Sun Apr 14, 2013 10:03 pm

Re: restrict permutations right at the start

Don't put your own line numbers in code tags. It makes it difficult for us to copy+paste and test your code.
Your code requires a small change, because it fails for the square of prime numbers, like 49.
Also, I'm curious how you're using sets, because it works well with a seive but isn't necessarily a good idea with the O(n**0.5) prime finding solution you're using.
Join the #python-forum IRC channel on irc.freenode.net for off-topic chat!

Please prefer not to PM members. The point of the forum is so that anyone can benefit. We don't want to help you over PMs/emails/Skype chats that others can't benefit from

micseydel

Posts: 2250
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

Re: restrict permutations right at the start

Thanks, that's probably why it returns an empty set!!!!
Code: Select all
`#!/usr/bin/python3import mathfrom itertools import permutationsdef isprime(n):    for x in range(2, int(math.sqrt(n))):        if n % x == 0:            return False    return Truedef get_perm():    results = set()    #results = []    for perm in permutations('123456789'):        if perm[-1] in '13579':            num = int(''.join(perm))            if isprime(num):                results.add(num)    return resultsprint(get_perm())`
portia

Posts: 17
Joined: Sun Apr 14, 2013 10:03 pm

Re: restrict permutations right at the start

No, that's not the reason.
Do you know how to determine if a number is divisible by 3?
http://en.wikipedia.org/wiki/Divisibility_rule#Divisibility_by_3

Try doing that for any number containing all digits from 1 to 9.

Anyway, you'll want to include the square root of the number in your checking, so you need to add 1 to the second number in your range().
Also, a set isn't going to get you any kind of a speed-up here.
Friendship is magic!

R.I.P. Tracy M. You will be missed.

stranac

Posts: 1592
Joined: Thu Feb 07, 2013 3:42 pm

Re: restrict permutations right at the start

Thanks!!!! I see. That has helped a lot. Maths knowledge does make things easier:)

As suggested by one of the members, I think I'm going to pregenerate prime numbers for future use.

Thanks a lot good people.
portia

Posts: 17
Joined: Sun Apr 14, 2013 10:03 pm