How to generate a list of palindrome numbers within a given range?

Question

Let's say the range is : 1 ≤ X ≤ 120

This is what I have tried:

>>> def isPalindrome(s):
    ''' check if a number is a Palindrome '''
    s = str(s)
    return s == s[::-1]

>>> def generate_palindrome(minx,maxx):
    ''' return a list of Palindrome number in a given range '''
    tmpList = []
    for i in range(minx,maxx+1):
        if isPalindrome(i):
            tmpList.append(i)

    return tmpList

>>> generate_palindrome(1,120)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111]

However, this is O(n).

How do I improve this algorithm to make it faster ?

PS. This is Python 2.7

Answer 1

Inspired by the Quant Metropolis answer, here is my take on generating palindromes in different bases (from 2 to 10).

First we define a helper generator that gives us all the numbers in the desired base of some length:

def nums_in_base(ndigits=3, b=10, _toplevel=True):
    """
    generate all nubmers in the given base of the given length
    `_toplevel` controls whether to add 0 at the beginning in the process of recursive calls
    """
    if ndigits == 0:
        yield ''
    else:
        for num in nums_in_base(ndigits-1, b, False):
            for i in range(int(_toplevel), b):
                yield str(i) + num

Note that it returns strings.

Now we write the palindrome generator itself:

def any_base_digit_palindromes(n_max_half_digits, b=10):
    """
    generate all palindromes in the given base and
    less than the given length
    palindromes consist of two parts, `n_max_half_digits` controls
    the maximum length of those halves 
    i.e., real max length of a palindrome is double the `n_max_half_digits`
    """
    if n_max_half_digits > 1:
        yield from digit_palindromes(n_max_half_digits - 1, b)

    for num in nums_in_base(n_max_half_digits, b):
        yield num + num[-2::-1]
        yield num + num[::-1]

Not sure about big-O, but plain empirical comparison with the OP's version for all palindromes in base 10 that are smaller than 1,000,000 I got ~400ms with OP's version and ~0.7ms with mine.

P.S. This can be extended to bases higher than 10 but that would require the usage of explicit predefined digits array instead of range in both generators.

Answer 2

Just as @it-ninja wrote just change step and stop

def palindrome_range(start,stop,step=1):
    ret=[x for x in xrange(start,stop,step) if str(x)==str(x)[::-1]]
    return ret

this will give all the palindromes in the given range

Answer 3

It's a fun exercise! Here's my take on a palindrome number generator, O(n^(1/2)):

def palindrome_number_generator():
    yield 0    
    lower = 1
    while True:
        higher = lower*10
        for i in xrange(lower, higher):    
            s = str(i)
            yield int(s+s[-2::-1])
        for i in xrange(lower, higher):    
            s = str(i)
            yield int(s+s[::-1])
        lower = higher


def palindromes(lower, upper):
    all_palindrome_numbers = palindrome_number_generator()
    for p in all_palindrome_numbers:
        if p >= lower:
            break
    palindrome_list = [p]
    for p in all_palindrome_numbers:
        # Because we use the same generator object,
        # p continues where the previous loop halted.
        if p >= upper:
            break
        palindrome_list.append(p)
    return palindrome_list


print palindromes(1, 120)

Because it's numbers, the generator has to handle 0 separately: it should include 0 but not 010.

Answer 4

This will work if you want it to give you a list immidiately:

def palindrome_range(start,stop,step=1):
    ret=[x for x in xrange(start,step,stop) if str(x)==str(x)[::-1]]
    return ret

However, if you want a generator, you could use:

def palindrome_range(start,stop,step=1):
    for x in xrange(start,stop,step):
        if str(x)==str(x)[::-1]:
            yield x

These will help you speed things up quite a bit depending on what you are using it in. For example, if you want to iterate through the palindromes, then a generator would serve you well. However, if you need the entire list, a regular list being returned would be better. It is also notable however, that xrange is much better in this case than range would be, as it deals with large list's better, as documented here.

Answer 5

I find this is a fun task, so I gave my rusty python skills some practise.

def generate_palindromes_with_length(l):
''' generate a list of palindrome numbers with len(str(palindrome)) == l '''
    if l < 1:
        return []
    if l == 1:
        return [x for x in range(10)]
    p = []
    if (l % 2):
        half_length = (l - 1) / 2
        for x in xrange(0, 10):
            for y in xrange(10 ** (half_length - 1), 10 ** half_length):
                p.append(int(str(y) + str(x) + str(y)[::-1]))
    else:
        half_length = l / 2
        for x in xrange(10 ** (half_length - 1), 10 ** half_length):
            p.append(int(str(x) + str(x)[::-1]))
    p.sort()
    return p


def generate_palindrome(minx, maxx):
''' return a list of palindrome numbers in a given range '''
    min_len = len(str(minx))
    max_len = len(str(maxx))
    p = []
    for l in xrange(min_len, max_len + 1):
        for x in generate_palindromes_with_length(l):
            if x <= maxx and x >= minx:
                p.append(x)
    p.sort
    return p

generate_palindromes_with_length is the key part here. The function generates palindromes, with a given number of decimal places. It uses different strategies for odd and even numbers of decimal places. Example: If length 5 is requested, it generates palindromes with the pattern abxba, where a, b, and x is any number from 1 to 9 (plus x may be 0). If 4 is the requested length, the pattern is abba.

generate_palindrome only needs to collect the palindromes for all needed length', and take care of the boundary.

The algorithm is in O(2*p), with p being the number of palindromes.

The algorithm does work. However, as my python skills are rusty, any advice for a more elegant solution is appreciated.

Answer 6

Your method could be:

palindromes = [x for x in xrange(min, max) if isPalindrome(x)]

The only way you can do this and have a non-linear algorithm is to generate the palindromes yourself, instead of testing.

A palindrome can be generated by taking a previous palindrome, and adding the same number to the left and right side, so that is a starting point.

Let's say you start at 1:

Possible palindromes are obtained by adding each digit from 1:9 to the left and right:

111
212
313
...

And also, you have to generate the several entries where every digit is equal in the range...