Abstract: A reduced word of a permutation w is a minimal length expression of w as a product of simple transpositions. The concept is ubiquitous within algebraic combinatorics. I will summarize what is known about enumeration of this set. In joint work (in progress) with Cara Monical and Benjamin Pankow, we prove that a well-known algorithm ("transition") for this problem has, on average, exponential time complexity. Given this context, we devise two simple, but competitive, randomized approximation algorithms. One of these extends to Hecke word enumeration, where significantly fewer results are available.