| 5 | """ |
| 6 | |
| 7 | class Markov: |
| 8 | def __init__(self, histsize, choice): |
| 9 | self.histsize = histsize |
| 10 | self.choice = choice |
| 11 | self.trans = {} |
| 12 | |
| 13 | def add(self, state, next): |
| 14 | self.trans.setdefault(state, []).append(next) |
| 15 | |
| 16 | def put(self, seq): |
| 17 | n = self.histsize |
| 18 | add = self.add |
| 19 | add(None, seq[:0]) |
| 20 | for i in range(len(seq)): |
| 21 | add(seq[max(0, i-n):i], seq[i:i+1]) |
| 22 | add(seq[len(seq)-n:], None) |
| 23 | |
| 24 | def get(self): |
| 25 | choice = self.choice |
| 26 | trans = self.trans |
| 27 | n = self.histsize |
| 28 | seq = choice(trans[None]) |
| 29 | while True: |
| 30 | subseq = seq[max(0, len(seq)-n):] |
| 31 | options = trans[subseq] |
| 32 | next = choice(options) |
| 33 | if not next: |
| 34 | break |
| 35 | seq += next |
| 36 | return seq |
| 37 | |
| 38 | |
| 39 | def test(): |