如何生成給定範圍內的迴文數字列表？

假設的範圍是：≤X≤如何生成給定範圍內的迴文數字列表？

這是我曾嘗試：

>>> 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]

然而，這是O(n)。

如何改進此算法以使其更快？

PS。這是Python 2.7版

來源

2013-05-02 Thanakron Tandavas

你的方法可能是：

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

，你可以做到這一點，有一個非線性算法的唯一方法是不是測試生成迴文自己。

迴文可以通過採取以前的迴文生成，並將相同的數字添加到左側和右側，這是一個起點。

比方說，你開始在1：9左右：

而且也，你必須生成多個條目

可能的迴文是通過從1將每個數字獲得每個數字在範圍內相等...

來源

2013-05-02 17:43:53 pcalcao

這是一個有趣的練習！這裏是我的大上回文數發生器，爲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)

因爲它的數字，生成具有單獨處理0：它應該包括0，但不是010

來源

2013-05-02 17:57:02

我覺得這是一個有趣的任務，所以我給了我生鏽的蟒蛇技能一些練習。

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是這裏的關鍵部分。該函數生成迴文，並給定小數位數。它對奇數和偶數小數位使用不同的策略。示例：如果請求長度爲5，則會生成模式爲abxba的迴文，其中a,b和x是從1到9的任何數字（加上x可能爲0）。如果4是請求的長度，則模式是abba。

generate_palindrome只需要收集所有需要長度的迴文「，並照顧邊界。

該算法在O（2 * p）中，其中p是迴文數。

該算法確實有效。但是，由於我的python技能很生疏，所以對於更優雅的解決方案的任何建議都是值得讚賞的。

來源

2013-05-02 18:54:37 tessi

如果你想給你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

但是，如果你想要一臺發電機，可以使用：

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

這些將幫助你加快速度這取決於你使用的是什麼。例如，如果你想遍歷迴文，那麼一個發電機就能很好地爲你服務。但是，如果您需要整個列表，則返回的常規列表會更好。但值得注意的是，在這種情況下，xrange比範圍更好，因爲它處理大列表更好，如記錄here。

來源

2013-05-02 19:24:50

正如@它忍者寫的只是改變的步驟和停止

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

這會給所有的迴文給定範圍內

來源

2016-06-01 17:01:10

如何生成給定範圍內的迴文數字列表？

回答

相關問題