"""
A simple, generic implementation of Markov chains in Python, with some
helpers for generating chains of words.

With inspiration from:
http://code.activestate.com/recipes/194364-the-markov-chain-algorithm/
"""

import os
import pickle
import random
import sys
from collections import defaultdict


def markov(model, length, start_key=None):
    """Generates a Markov chain based on the given model with the given word
    count."""
    chain = []
    key = start_key or random.choice(model.keys())
    for _ in xrange(length):
        x = random.choice(model[key])
        chain.append(x)
        key = key[1:] + (x,)
    return chain

def build_model(xs, n=2, nil=None):
    """Builds a model of the given sequence using n-grams of size n. The model
    is a dict mapping n-gram keys to lists of items appearing immediately
    after those n-grams. Missing values will be filled in with the given nil
    value."""
    model = defaultdict(list)
    # Start with a dummy key for the first word. After n iterations, the key
    # will contain all valid words from the corpus.
    key = tuple(nil for _ in xrange(n))
    for x in xs:
        model[key].append(x)
        key = key[1:] + (x,)
    # Make sure the last key has an entry
    model[key].append(nil)
    # Return normal dict, instead of a defaultdict object
    return dict(model)

def build_word_model(corpus, n=2):
    """A special-case of build_model that knows how to build a model based on
    words from a corpus given as a string or a file-like object."""
    return build_model(gen_words(corpus), n=n, nil='')

def gen_words(corpus):
    """Yields each word from the given corpus, which can be either a string or
    a file-like object containing the words."""
    if isinstance(corpus, basestring):
        corpus = (line for line in corpus.splitlines())
    for line in corpus:
        for word in line.strip().split():
            yield word

if __name__ == '__main__':
    try:
        length = int(sys.argv[-1])
    except ValueError:
        length = 30
    model = build_word_model(sys.stdin)
    chain = markov(model, length)
    for item in chain:
        print item,

@@ -660,18 +660,8 @@
  n=2
-, nil=None
 ):%0A 
@@ -840,475 +840,153 @@
 ams.
- Missing values will be filled in with the given nil%0A    value.%22%22%22%0A    model = defaultdict(list)%0A    # Start with a dummy key for the first word. After n iterations, the key%0A    # will contain all valid words from the corpus.%0A    key = tuple(nil for _ in xrange(n))%0A    for x in xs:%0A        model%5Bkey%5D.append(x)%0A        key = key%5B1:%5D + (x,)%0A    # Make sure the last key has an entry%0A    model%5Bkey%5D.append(nil)%0A    # Return normal dict, instead of a defaultdict object
+%22%22%22%0A    model = defaultdict(list)%0A    for ngram in gen_ngrams(xs, n+1):%0A        key, item = ngram%5B:-1%5D, ngram%5B-1%5D%0A        model%5Bkey%5D.append(item)
 %0A   
@@ -1236,17 +1236,254 @@
  n=n
-, nil='')
+)%0A%0Adef gen_ngrams(xs, n=2):%0A    %22%22%22Yields n-grams from the given sequence. Assumes len(xs) %3E= n.%22%22%22%0A    it = iter(xs)%0A    gram = tuple(it.next() for _ in xrange(n))%0A    yield gram%0A    for x in xs:%0A        gram = gram%5B1:%5D + (x,)%0A        yield gram
 %0A%0Ade

Simplify model-building by just using n-grams and not worrying about empty values.