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

Postby portia » Sat Aug 24, 2013 3:31 pm

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/python3

from itertools import permutations as perm
print(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

Postby Mekire » Sat Aug 24, 2013 3:53 pm

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 permutations

results = []
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
User avatar
Mekire
 
Posts: 988
Joined: Thu Feb 07, 2013 11:33 pm
Location: Amakusa, Japan

Re: restrict permutations right at the start

Postby portia » Sat Aug 24, 2013 4:03 pm

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

Postby portia » Sat Aug 24, 2013 4:44 pm

Hmm, actually it still includes even numbers

Code: Select all
#!/usr/bin/python3
 
from itertools import permutations

results = []

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

Postby hansn » Sat Aug 24, 2013 5:14 pm

Code: Select all
>>> not 4 % 2
True
>>> not 5 % 2
False

>>> 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

Postby portia » Sat Aug 24, 2013 5:29 pm

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

Postby stranac » Sat Aug 24, 2013 5:48 pm

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.
User avatar
stranac
 
Posts: 1144
Joined: Thu Feb 07, 2013 3:42 pm

Re: restrict permutations right at the start

Postby portia » Sat Aug 24, 2013 7:01 pm

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

Postby stranac » Sat Aug 24, 2013 7:51 pm

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.
That's where a sieve can help you.
Translating the pseudocode from the wikipedia page should be quite straight-forward.
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.
User avatar
stranac
 
Posts: 1144
Joined: Thu Feb 07, 2013 3:42 pm

Re: restrict permutations right at the start

Postby micseydel » Sat Aug 24, 2013 8:34 pm

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!

Please do not PM members regarding questions which are meant to be discussed publicly. The point of the forum is so that others can benefit from it. We don't want to help you over PMs or emails.
User avatar
micseydel
 
Posts: 1368
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

Re: restrict permutations right at the start

Postby portia » Sun Aug 25, 2013 5:15 pm

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

Postby micseydel » Sun Aug 25, 2013 5:31 pm

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!

Please do not PM members regarding questions which are meant to be discussed publicly. The point of the forum is so that others can benefit from it. We don't want to help you over PMs or emails.
User avatar
micseydel
 
Posts: 1368
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

Re: restrict permutations right at the start

Postby portia » Sun Aug 25, 2013 5:44 pm

Thanks, that's probably why it returns an empty set!!!!
Code: Select all
#!/usr/bin/python3
import math
from itertools import permutations

def isprime(n):
    for x in range(2, int(math.sqrt(n))):
        if n % x == 0:
            return False
    return True

def 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 results

print(get_perm())
portia
 
Posts: 17
Joined: Sun Apr 14, 2013 10:03 pm

Re: restrict permutations right at the start

Postby stranac » Sun Aug 25, 2013 6:52 pm

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.
See what I'm talking about?

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.
User avatar
stranac
 
Posts: 1144
Joined: Thu Feb 07, 2013 3:42 pm

Re: restrict permutations right at the start

Postby portia » Sun Aug 25, 2013 7:49 pm

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


Return to General Coding Help

Who is online

Users browsing this forum: Google [Bot] and 6 guests