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: 980
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: 1093
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: 1093
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!
User avatar
micseydel
 
Posts: 1116
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!
User avatar
micseydel
 
Posts: 1116
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: 1093
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: freddyhard and 2 guests