Euler help function

[luke77]

Hi guys,

I'm working my way through the Project Euler problems to help teach myself programming, so I'm looking to write a function that will return all possible permutations of a n digit number so that I can test for a condition on each permutation. So, for example, if the number was 87321 I would want the function to return 12378, 12387, 12738, 12783, ..., 87312, 87321 . They don't necessarily have to be in order. I'm having trouble figuring out how to do this. I'm thinking perhaps there is a way to create a list out of the individual digits and then use some kind of recursive iteration on the list, but it's a bit over my head. Can anyone help out?

Thanks,
Luke

[Stefano Mtangoo]

I was about to try when I found myself that I have forgotten permutation formula. I'll be back after some Xtra time perruzing

[Gribouillis]

Here is a possible code to generate the permutations of a number

def permutations(L):
    "generates all the permutations of a list"
    if len(L) == 1:
        yield L
    for i in xrange(len(L)-1, -1, -1):
        x, LL = L[i], L[:i] + L[i+1:]
        for p in permutations(LL):
            p = list(p)
            p.append(x)
            yield p

def rev_digits(n):
    "generates the digits of a postitive integer in reverse order"
    while n > 0:
        n, r = divmod(n, 10)
        yield r

def digits(n):
    "returns the list of the digits of a positive integer"
    if n <= 0:
        raise ValueError
    return list(rev_digits(n))[::-1]

def numpermutations(n):
    "generates all numbers obtained by permuting the digits of n > 0"
    L = digits(n)
    for LL in permutations(L):
        s = 0
        for x in LL:
            s = 10*s + x
        yield s
        
for n in numpermutations(3105):
    print n

Note that the above code is not so good when there are repeated digits, for example if n == 222, this will generate 6 times the same number by permuting the 2's.

[Gribouillis]

This code avoids the above problem

from collections import defaultdict

def perm(D):
    if not D:
        yield 0
        return
    for k, v in D.items():
        if v == 1:
            del D[k]
        else:
            D[k] = v-1
        for s in perm(D):
            yield 10*s+k
        D[k] = v

def digit_frequencies(n):
    "returns a dictionary digit -> number of occurrences in n"
    D = defaultdict(int)
    while n:
        n, r = divmod(n, 10)
        D[r] += 1
    return D

def numpermutations(n):
    return perm(digit_frequencies(n))

n = 31044

for p in numpermutations(n):
    print p

[luke77]

Thanks guys. These work but I am still having trouble with the problem. I'll post it here along with my code, and I'd greatly appreciate any help. Be gentle; I'm new to programming and haven't taken math since calculus in high school :)

The problem:

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

My code so far (I included the permutation code verbatim):

#Generate list of numbers that can be expressed as sum of two abundant numbers
from collections import defaultdict

def perm(D):
    if not D:
        yield 0
        return
    for k, v in D.items():
        if v == 1:
            del D[k]
        else:
            D[k] = v-1
        for s in perm(D):
            yield 10*s+k
        D[k] = v

def digit_frequencies(n):
    "returns a dictionary digit -> number of occurrences in n"
    D = defaultdict(int)
    while n:
        n, r = divmod(n, 10)
        D[r] += 1
    return D

def numpermutations(n):
    return perm(digit_frequencies(n))

n = 31044


theanswers=[]


def getPossiblePrimes (n1):
    #Get a list of "possible" circular primes. Any number with an even digit
    #is excluded because one of the permutations will be even (ie not prime).
    #If the number has only odd digits, returns true.
    b=list(str(n1))
    for i in b:
        i=int(i)
        if i%2==0:
            return False
    return True

for i in xrange(1,100000):
    if getPossiblePrimes(i)==True:
        theanswers.append(i)

        
falseanswers=[]
#Sort the list of possible primes, testing each permutation of each number
#to see if it prime. If any permutation is not prime (and the same length as the original
#number), append the number to "falseanswers"
for i in theanswers:
    for p in numpermutations(i):
        if len(str(p))==len(str(i)) and isPrime(p)==False:
            falseanswers.append(i)
#Finally, generate a list of numbers from possible primes that are not in falseanswers.
            
finalanswers=[]
for i in theanswers:
    if i not in falseanswers:
        finalanswers.append(i)
print finalanswers

After working for about 10 minutes, the output was:

[1, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 199, 311, 337, 373, 733, 919, 991]

which is incorrect...I'm guessing there is a much more efficient way to go about solving this problem, and I'm not sure why I'm getting an incorrect answer even with my bulky, inefficient code. Can anyone help out?

Thanks very much,
Luke

[bvdet]

You should not look at the permutations for this problem, you should look at the rotations.

def rotations(s):
    return [s[i:]+s[:-len(s)+i] for i in range(len(s))]

Example:
>>> rotations('87321')

>>>

[luke77]

You should not look at the permutations for this problem, you should look at the rotations.

def rotations(s):
    return [s[i:]+s[:-len(s)+i] for i in range(len(s))]

Example:
>>> rotations('87321')

>>>

Ah...thanks, I feel stupid. I read the problem wrong.