Exercise 39: Alternative transformation algorithm

Summary

Implement an alternative transformation algorithm that doesn't start by permuting each of the entity type sets, but rather works by permuting the entity type sets of each adjacent words.

This alternative approach will be known as the Adjacent Pair Permutation algorithm, or APP algorithm. As part (b), add a hash that will track what fragments have already been considered so that they aren't re-considered. This in effect prunes the tree. The resulting algorithm will be called Unique Adjacent Pair Permutation.

The original approach will be known as the Exhaustive Permutation algorithm, or EP algorithm.

Motivation

It is impractical to permute each of the entity type sets of a sentence, since a 15 word sentence with 10 entity types per word results in 10^15 permutations. That's one thousand trillion, and the initial permutations are only the first level of a tree!