## luke77 Newbie Poster

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 455

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 1,391

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 1,391

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

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:

#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 p in numpermutations(i):
if len(str(p))==len(str(i)) and isPrime(p)==False:
#Finally, generate a list of numbers from possible primes that are not in falseanswers.

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 75

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.