Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**gAr****Member**- Registered: 2011-01-09
- Posts: 3,478

From the discussion here: http://www.mathisfunforum.com/viewtopic … 19518&p=13

Posting my program in Sage to get the expected number of keystrokes, for my later reference!

```
st="abracadabra" # The string pattern
nn=len(st) # The string length
mx=[[0]*(nn+1) for i in range(nn+1)] # The initialized markov chain
nchars=26 # Number of possible characters
for i in range(1,nn): # Set the probabilities row by row
seen=st[:i] # The substring seen till index 'i'
seenst=set(seen) # Unique chars seen
# Get the proper transition state, by watching the repeated substrings
# E.g. in 123121,
# consider the states to be "others", "1", "12", "123", "1231", "12312" and "123121"
# If we see 123123, we must go to the state "123" from "12312"
for ele in seenst:
nlongest=0
tmpst=seen+ele
for k in range(1,len(tmpst)):
if st.find(tmpst[-k:]) == 0: # The last k chars in the state
nlongest=k
mx[i][i+1]=1/nchars
if st[i] != ele and nlong != 0:
mx[i][nlong]=1/nchars
mx[i][0]=1-sum(mx[i])
mx[0][0]=(nchars-1)/nchars
mx[0][1]=(1)/nchars
mx[nn][nn]=1
print sum((identity_matrix(nn)-matrix(mx)[0:nn,0:nn]).inverse()[0].list())
```

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense" - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

Offline

Pages: **1**