I've only recently started trying to learn Python; I'm using Project Euler for some practice, and I'm currently doing Problem 24
I'm sure my code is not the most efficient out there, and it looks quite silly, but it gives me the correct answer and doesn't take too long, so I'm happy with it for now.
I have it printing out the correct answer, but then the program is still running, working out the next numbers in the sequence. I'd appreciate any help in getting my program to stop running once it's output the correct answer. Here is my code:
for b in range(0,10):
if b != a:
for c in range(0,10):
if c not in (a,b):
for d in range(0,10):
if d not in (a,b,c):
for e in range (0,10):
if e not in (a,b,c,d):
for f in range(0,10):
if f not in (a,b,c,d,e):
for g in range(0,10):
if g not in (a,b,c,d,e,f):
for h in range(0,10):
if h not in (a,b,c,d,e,f,g):
for i in range(0,10):
if i not in (a,b,c,d,e,f,g,h):
for j in range(0,10):
if j not in (a,b,c,d,e,f,g,h,i):
z = 1000000000*a + 100000000*b + 10000000*c + 1000000*d + 100000*e + 10000*f + 1000*g + 100*h + 10*i + j
m = m + 1
if m == 1000000:
print z
>>1
I would kick you in the balls if you checked in this O(n^9) algorithm.
You can do permutations using recursion for a better solution, or for an optimal solution, look up Lehmer coding, and the factorial numbering system (described in the Permutation article on wackypedia).
>>3
It's not like a tip jar, where I can just grab some coins when I think no-one's looking.
Name:
Anonymous2011-08-14 9:23
The cleanest way to solve this is to fork to the background when you have found the correct answer, so that the remaining work will be completed without interfering with the user.
It should look like this: for b in range(0,10):
if b != a:
for c in range(0,10):
if c not in (a,b):
for d in range(0,10):
if d not in (a,b,c):
for e in range (0,10):
if e not in (a,b,c,d):
for f in range(0,10):
if f not in (a,b,c,d,e):
for g in range(0,10):
if g not in (a,b,c,d,e,f):
for h in range(0,10):
if h not in (a,b,c,d,e,f,g):
for i in range(0,10):
if i not in (a,b,c,d,e,f,g,h):
for j in range(0,10):
if j not in (a,b,c,d,e,f,g,h,i):
z = 1000000000*a + 100000000*b + 10000000*c + 1000000*d + 100000*e + 10000*f + 1000*g + 100*h + 10*i + j
m = m + 1
if m == 1000000:
print z
if m == 1000000:
os.fork()
iS THIS SOME SORT OF JOKE? cONSIDER THE TOTALLY ORDERED SET S WITH LEXICOGRAPHICAL ORDER CONSISTING OF ALL PERMUTATIONS OF "0123456789". aNY F:N10!->S THAT IS 1-1 AND STRICTLY INCREASING WILL DO. tHE ANSWER IS F(1000000) wHY ARE YOU ROLLING OVER ALL SPOILERS DUMBFUCK?! tHE GAME
Name:
Anonymous2011-08-14 14:57
Christ OP.
Here's my solution:
def permutations(ls):
for i in xrange(len(ls)):
ls[0], ls[i] = ls[i], ls[0]
if len(ls) == 2:
yield ls
else:
for p in permutations(ls[1:]):
yield ls[:1] + p
i = 1
for perm in permutations(range(10)):
if i == 1000000:
print ''.join(str(n) for n in perm)
break
i += 1
it seems to me like you'd need to break at the bottom of every for loop after you've found the answer. So create a variable called done, set equal to False, and check for that everytime at end of for loop. if done (== True) then break. Do it for every for loop at end of for loop. So.... I'd do something like:
done = False
m = 9876543*2 for a in range (1,10):
for b in range(0,10):
if b != a:
for c in range(0,10):
if c not in (a,b):
for d in range(0,10):
if d not in (a,b,c):
for e in range (0,10):
if e not in (a,b,c,d):
for f in range(0,10):
if f not in (a,b,c,d,e):
for g in range(0,10):
if g not in (a,b,c,d,e,f):
for h in range(0,10):
if h not in (a,b,c,d,e,f,g):
for i in range(0,10):
if i not in (a,b,c,d,e,f,g,h):
for j in range(0,10):
if j not in (a,b,c,d,e,f,g,h,i):
z = 1000000000*a + 100000000*b + 10000000*c + 1000000*d + 100000*e + 10000*f + 1000*g + 100*h + 10*i + j
m = m + 1
if m == 1000000:
print z
done = True
if done:
break
if done:
break
if done:
break
if done:
break
if done:
break
if done:
break
if done:
break
if done:
break
if done:
break
def forward(perm):
head = perm[0]
newhead = min ([i for i in perm if i > head])
perm.sort()
return [newhead]+[i for i in perm if i != newhead]
print (nth_perm(range(10), 1000000))
Name:
Anonymous2011-08-14 23:50
Not everything has to be solved with a billion nested loops or deep recursion.
For ten digits, there are 9! = 362880 permutations beginning with a given digit. Therefore the 1000000th permutation will start with 2 since 2*362880 < 1000000 < 3*362880. Thus we're looking for the 1000000-2*362880 = 274240th permutation starting with 2.
The remaining digits are 0,1,3,4,5,6,7,8,9.
For 9 digits, there are 8! = 40320 permutations starting with a given digit (note that it doesn't matter that the 9 digits in this case aren't 0,1,2,3,4,5,6,7,8). Since 6*40320 < 274240 < 7*40320, the next digit is the 7th lowest remaining digit, i.e. 7, and we want the 274240 - 6*40320 = 32320th permutation starting with 27.
same thing, blah blah, 6*7! < 32320 < 7*7!, so the next digit is the 7th lowest digit of 0,1,3,4,5,6,8,9, which is 8.
Keep going to get the final answer, I can't be bothered.