# Improve pandigital algorithm

First of all, I am a beginner in Python trying to learn optimizations and proper coding standards.

Here is a snippet of code that checks if a number follows the rule: first AND last N digits contain all unique numbers from 1 to N, but in any order. This also means that in either first N or last N digits, each number appears exactly once.

import time

start_time = time.time()

def is_pandigital(nr, n):
digits = ''.join(map(str, range(1, n + 1)))
nr = str(nr)
for i in digits:
if str(i) not in nr[0:9]:
return False
if str(i) not in nr[-9:]:
return False

return True

assert is_pandigital(1423, 4) is True
assert is_pandigital(1423, 5) is False
assert is_pandigital(14235554123, 4) is True
assert is_pandigital(14235552222, 4) is False # !important
assert is_pandigital(1444, 4) is False
assert is_pandigital(123564987, 9) is True

pandigitals = []
# this loop is strictly for benchmarking is_pandigital
for i in range(100000, 999999):
if is_pandigital(i, 6):
pandigitals.append(i)

print pandigitals

print time.time() - start_time, "seconds"


When running this, the result is:

[123456, .......]
2.968 seconds

Process finished with exit code 0


The code seems to work fine, but it doesn't appear to be very efficient. Would you have any tips to improve it? Any piece of code and/or idea would be highly appreciated.

PS: I chose this loop so that any improvements to the is_pandigital function would be immediately obvious.

Example of numbers I am looking for:

321XXXXXXXXXXXXXXX132 - good

321XXXXXXXXXXXXXXX133 - not good, because the last 3 digits dont contain 1, 2 and 3

231 - good

• Pandigital numbers have a somewhat different definition. Sep 21, 2013 at 10:13
• That is true, I worded the issue a bit weird, sorry about that. Re-wrote it slightly so it doesn't conflict with the definition of pandigital numbers. This is part of a problem on projecteuler.net Sep 21, 2013 at 12:00
• Out of curiosity, which problem is this ? Sep 21, 2013 at 23:48
• It was problem 104, which requested the first Fibonacci number for which the first 9 + last 9 digits were 1-9 pandigital. The script still ran for 10h before finding the result :) Sep 22, 2013 at 9:22
• 10 hours for a PE problem: you're probably doing it wrong. You can have a look at the thread now that you have a solution. An easy improvement you could/should do is to remove the n parameter as it will always be 9 and pre compute the set of numbers from 1 to 9. Sep 22, 2013 at 11:10

You can rewrite your asserts without comparing to True and False:

assert is_pandigital(1423, 4)
assert not is_pandigital(1423, 5)
assert is_pandigital(14235554123, 4)
assert not is_pandigital(14235552222, 4) # !important
assert not is_pandigital(1444, 4)
assert is_pandigital(123564987, 9)


You can rewrite your benchmark with list comprehension:

# this loop is strictly for benchmarking is_pandigital
pandigitals = [i for i in range(100000, 999999) if is_pandigital(i, 6)]


Now for the algorithm itself, I must confess that I have troubles understanding what you want to do as you seem to be calling "pandigital" two different things. In any case, I have the feeling that something is wrong in your code, it seems like :

   if str(i) not in nr[0:9]:
return False
if str(i) not in nr[-9:]:
return False


should be

    if str(i) not in nr[0:n]:
return False
if str(i) not in nr[-n:]:
return False


and

assert not is_pandigital(9999912399999, 3)


should provide you some hints.

I'll go deeper in the code once you confirm that my understanding is correct.

Edit : I have to go, no time to run benchmarks but here are the improvements. I kept different versions to that you can take ideas out of it.

def is_pandigital(nr, n):
nr = str(nr)
beg=nr[0:n]
end=nr[-n:]
for i in map(str, range(1, n + 1)):
if i not in beg or i not in end:
return False
return True

def is_pandigital(nr, n):
nr = str(nr)
beg=set(nr[0:n])
end=set(nr[-n:])
return beg==end and beg==set(map(str, range(1, n + 1)))

• Awesome! Especially the list comprehension, which I didn't know about. The n instead of 9 fix (code initially was used to check only pandigital numbers with length 9) also fixed the assert you mentioned. Sep 21, 2013 at 11:30
• I edited the post to be a bit more clear on the numbers I am looking for Sep 21, 2013 at 11:58
• First solution - an average of 2.4 seconds (pretty big improvement), and second version has 4.2 seconds. I'll see if I can improve on your code, thank you Sep 21, 2013 at 12:29
• I managed to solve the projecteuler.net problem using your improvement. The rest of the script probably was pretty bad, since it found the result after running 10 hours, but I got it! Thank you Sep 22, 2013 at 9:19

I'd try by sorting digits:

def adapt_nr(nr):
nr = [ int(i) for i in list(nr) ]
nr.sort()
return nr

def is_pandigital(nr, n):
nr = str(nr);
if len(nr) < n: return False
chk = list(range(1, n+1))
if adapt_nr(nr[0:n]) != chk: return False
if adapt_nr(nr[-n:]) != chk: return False
return True


A built-in sort is quick, and all that is left to compare is that the obtained lists of digits are equal to [1,..,n].

The check itself might be faster if done with strings instead of lists:

def adapt_nr(nr):
nr = [ int(i) for i in list(nr) ]
nr.sort()
return ''.join([str(i) for i in nr])

def is_pandigital(nr, n):
nr = str(nr);
if len(nr) < n: return False
chk = ''.join(str(i) for i in list(range(1, n+1)))
if adapt_nr(nr[0:n]) != chk: return False
if adapt_nr(nr[-n:]) != chk: return False
return True


You'll have to benchmark for yourself.

I'm a beginner in Python, so some of this can probably be written in a more pythonic way. I'll edit if I get such suggestions in the comments.

• Quite interesting solutions. The first has an average of 6 seconds run time, while the second has an average of 10 seconds, so in this situations lists are better than strings :) Sep 21, 2013 at 12:24