Licking the Spoonerism Problem

The Spoonerism Problem was first outlined by K. Tsichlas, M. Bender, and the Algorithmic Design Group (ADG) of King’s College, UK, at London Stringology Day 2005. (LSD 2005) (see note below §)
It was named in honour of William Archibald Spooner (22 July 1844 – 29 August 1930) and can be defined thus :

“Whether [within a given sentence] there exists a transposition of two [different] letters such that the resulting string is a valid word according to a given dictionary or can be decomposed into valid words.”

At the time of the presentation, no-one had yet constructed an efficient computer algorithm to solve the problem. The position has now changed, for an international group of algorithmic developers, Hans-Joachim Böckenhauer, Juraj Hromkovič, Richard Královič, Tobias Mömke and Kathleen Steinhöfel, have decently revised Efficient Algorithms for the Spoonerism Problem* (Lecture Notes in Computer Science, 2007, Volume 4475/2007, 78-92).
“In this paper, we give some efficient algorithms for deciding whether a given sentence, made up from words of a given dictionary, is a spoonerism or not.” say the authors.
As a BONUS, the international team give example spoonerisms not only in English:

• “You have deliberately tasted two worms and you can leave Oxford by the town drain.”

but also in German:

• ”Ein Schornsteinfeger gegen Ruß / am besten steht im Regenguß.”

and Czech:

• “úÎ bez nálady – Îúbezná lady”

The full paper can be accessed here.


[*] The research was partially supported by VEGA 1/3106/06 (Slovak Grant Agency for Science), and EPSRC EP/D062012/1, Stochastic Local Search Algorithms for Structural Proteomics, (Engineering and Physical Sciences Research Council).

[§] It is said – for it does not appear to appear in the programme.

The picture depicting The Reverend Spooner is provided courtesy of Wikipedia, from Vanity Fair, April 1898.