Here’s a quick one. The problem is to find out what is the mean length of the largest palindromic substring from a x-character string. (I saw the problem at this Google+ post, where it’s stated with numbers, not exactly strings.)

Solving the problem analytically is definitely complicated. So I wanted to make a program to actually calculate the statistics of the length of the largest palindromic substrings, to check out the theories.

The difficult part of the program is finding out the length of the largest palindromic substring of the given strings. Here is how it works: I start with a list of all the 1-digit and 2-digit palindromic substrings from the input. The 1-digit ones are each character. The 2-digit ones are the simply the characters whose following one is equal to it. The list has maximum size of 2*x-1 entries. Each entry is a tuple, with the length of the substring, and the index of the first digit.

After this list is initialized, we grow each of these substrings in both directions if the previous and following characters are equal. If the substring reaches the limits of the string, or if the next characters are different from each other, the substring stops growing.

At each iteration with build a new list from the previous, so the smaller palindromic substring get dropped. At each iteration we record the length of the current largest substring, and that is the output of the routine.

I pasted the code at http://pastebin.com/ZyfmtYt9 too.

from pylab import *
def largest_palindrome(x,num):
## Initialize palindrome candidates list with the unit palindromes
seeds = [(1,k) for k in range(x)]
## Initial "even" palindrome middles
seeds += [(2,k) for k in range(x-1) if num[k]==num[k+1]]
while seeds != []:
output = seeds[-1][0]
newseeds = []
for l,k in seeds:
if k>0 and k+l<x-1:
if num[k-1]==num[k+l]:
newseeds.append((l+2,k-1))
seeds = newseeds
return output
def iteration(x):
num = randint(0,10,x)
return largest_palindrome(x,num)
if __name__ == '__main__':
ion()
Nsmp = 10000
Lx = [3,4,5,6,7,8,9,10,32,100,316,1000]
suptitle('Cumulative probabilities of largest palindromes', size=16, fontweight='bold')
axes([.1,.2,.8,.7])
kk=0
Lll=[]
meanz = []
for x in Lx:
kk+=0.04
cdf = sort([iteration(x) for k in range(Nsmp)])
p=mgrid[1:Nsmp+1]/(Nsmp+1.)
ll=plot(cdf+kk,p,'-')[0]
Lll.append(ll)
meanz.append(mean(cdf))
figlegend(Lll,Lx, 'lower center', ncol=6, title='Values of x (number of digits)')
grid()
plot([0,10],[.5,.5],'k--')
xlim(0,10)

### Like this:

Like Loading...

*Related*