Don't like ads? PRO users don't see any ads ;-)

# Largest palindrome mean length problem

By: nlw on Jan 14th, 2012  |  syntax: Python  |  size: 1.27 KB  |  hits: 51  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. ## Mean size of the largest palindrome problem.
2. ## by Nicolau Werneck, 2012-01-15
3. from pylab import *
4.
5. def largest_palindrome(x,num):
6.     ## Initialize  palindrome candidates list with the unit palindromes
7.     seeds = [(1,k) for k in range(x)]
8.     ## Initial "even" palindrome middles
9.     seeds += [(2,k) for k in range(x-1) if num[k]==num[k+1]]
10.
11.     while seeds != []:
12.         output = seeds[-1][0]
13.         newseeds = []
14.         for l,k in seeds:
15.             if k>0 and k+l<x-1:
16.                 if num[k-1]==num[k+l]:
17.                     newseeds.append((l+2,k-1))
18.         seeds = newseeds
19.
20.     return output
21.
22.
23. def iteration(x):
24.     num = randint(0,10,x)
25.     return largest_palindrome(x,num)
26.
27.
28. if __name__ == '__main__':
29.     ion()
30.
31.     Nsmp = 10000
32.     Lx = [3,4,5,6,7,8,9,10,32,100,316,1000]
33.
34.     suptitle('Cumulative probabilities of largest palindromes', size=16, fontweight='bold')
35.     axes([.1,.2,.8,.7])
36.     kk=0
37.     Lll=[]
38.     for x in Lx:
39.         kk+=0.04
40.         cdf = sort([iteration(x) for k in range(Nsmp)])
41.         p=mgrid[1:Nsmp+1]/(Nsmp+1.)
42.         ll=plot(cdf+kk,p,'-')[0]
43.         Lll.append(ll)
44.
45.     figlegend(Lll,Lx, 'lower center', ncol=6, title='Values of x (number of digits)')
46.     grid()
47.     plot([0,10],[.5,.5],'k--')
48.     xlim(0,10)