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

## No comments:

## Post a Comment