Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News Sign UpSign In
| Download
Views: 39
def remove_squares(s): """" Removes squares from a string s under the assumption that the prefix s[:-1] is square free. Each suffix of length i, s[:-i], is compared to the second to last suffix of length i, s[-2*i:i], for i from 1 to len(s)/2. """" n = len(s) for i in range(1,n/2+1): if s[-i:] == s[-2*i:-i]: s = s[:-2*i] break return s def meta_remove_squaresk(k): """ This function returns a function that removes squares from the last 2k characters of s. The returned function works just as remove_squares (above) except it just checks suffixes of length i from 1 to k. """ def remove_squaresk( s ): n = len(s) for i in range(1,k+1): if s[-i:] == s[-2*i:-i]: s = s[:-2*i] break return s return remove_squaresk def process(n=50, alphabet='abc', cleaner = remove_squares): """ Simulates the random process of growing an initially empty string s over a given alphabet by adding n characters. At each of the n steps of the process a random character from the alphabet is chosen and it is appended. After appending the character we call a cleaner function on s. INPUT: - n - number of characters to append to the empty string. Default value is 50. - alphabet - Source of characters for the string. {a,b,c} is the default alphabet - cleaner - Function used to clean s. By default we remove squares from s by using remove_squares. OUTPUT: - s - string that results from running the simulation. - max_length - maximum length of s during simulation. """ s = '' max_length=0 for i in xrange(n): c = alphabet[randint(0,len(alphabet)-1)] s+=c s = cleaner( s ) if len(s)>max_length: max_length=len(s) return s,max_length def expected_length( repeat, steps=100, alphabet='abc', cleaner=remove_squares ): """ Runs process (defined above) for repeat many times. All other arguments are passed to the process function. Reports the average length of the string after running process for repeat times and also the length of the longest string found by process during the simulations. """ lengths =[] max_length = 0 for i in range(repeat): s,maxl = process(steps,alphabet, cleaner) lengths.append(len(s)) if max_length < maxl: max_length=maxl return sum(lengths)/float(repeat), max_length
expected_length(1000,10000,cleaner=meta_remove_squaresk(2))
(8.51, 97)
expected_length(1000,10000,cleaner=meta_remove_squaresk(2))
(8.822, 94)
expected_length(1000,10000,cleaner=meta_remove_squaresk(2))
(8.472, 90)
expected_length(1000,10000,cleaner=meta_remove_squaresk(2))
(8.376, 99)
expected_length(1000,1000,cleaner=meta_remove_squaresk(1))
(333.686, 442)
expected_length(1000,10000)
(3.074, 27)
expected_length(1000,10000)
(3.244, 29)
len(process(100000,'abcd'))
7008
x[-4:]
'fghi'
i=3 print x[-i:] print x[-2*i:-i]
ghi def
print x[:-2*i]
abc