# Copyright (C) 1999 Lucent Technologies
# Excerpted from 'The Practice of Programming'
# by Brian W. Kernighan and Rob Pike
 
# markov.pl: markov chain algorithm for 2-word prefixes
 
  $MAXGEN = 10000;
  $NONWORD = "\n";
  $w1 = $w2 = $NONWORD;                    # initial state
  while (<>)
  {                                        # read each line of input
    foreach (split)
    {
      push(@{$statetab{$w1}{$w2}}, $_);
      ($w1, $w2) = ($w2, $_);	           # multiple assignment
    }
  }
 
  push(@{$statetab{$w1}{$w2}}, $NONWORD);  # add tail
  $w1 = $w2 = $NONWORD;
 
  for ($i = 0; $i < $MAXGEN; $i++) 
  {
    $suf = $statetab{$w1}{$w2};	           # array reference
    $r = int(rand @$suf);		   # @$suf is number of elems
    exit if (($t = $suf->[$r]) eq $NONWORD);
    print "$t\n";
    ($w1, $w2) = ($w2, $t);		   # advance chain
  }