I came across a problem which needed me to check if a number is a palindrome which I can do by reversing the number and comparing it with the original.
But what if I wanted all the possible palindromic numbers of a given width.
If I wanted all the 5 palindromic numbers, I can solve them by considering the number as abcba where a, b, c are digits and a!=0. The number would be a(10000) + b(1000) + c(100) + b(10) + a.
Then the problem becomes trivial.
for a in range(9, 0, -1):
for b in range(9, -1, -1):
for c in range(9, -1, -1):
num = 10001 * a + 1010 * b + 100 * c
But as we can see, it is not generic and making it generic this way, would require me to use iterators.
On a sunday morning, travelling from Krishnagiri to Dharmapuri in a local bus, at 04:14, this sweet and simple approach occured to me.
It is a recursive approach that considers the fact that all n digit palindromes can be generated by adding a digit at the front and back of the (n - 2) digit palindromes and (n - 4) digit palindromes and so on.
Ex: 5 digit palindromes are of the form
a***a where a != 0 and *** is a 3d palindrome
a0*0a where * is a 1d palindrome.
def nDigitPalins(n):
if n == 1:
return range(9, 0, -1)
elif n == 2:
return [11 * x for x in range(9, 0, -1)]
else:
p_zeros = [i * (10 ** (n -1) + 1) for i in range(9, 0, -1)]
p = []
for base in p_zeros:
for y in range(1, (n + 1) / 2):
for subPalin in nDigitPalins(n - 2 * y):
p_num = base + subPalin * (10 ** y)
p.append(p_num)
p.append(base)
return p
print nDigitPalins(8)
You can run the code at http://ideone.com/szO5q
