Nanagram the Anagram Maker

Your Word Jumbling Desktop Friend

Author:	Michael Foord
Version:	Nanagram 1.4.0
Date:	2006/02/28
Homepage:	Nanagram Homepage
License:	Voidspace License
Mailing List:	Voidspace Shareware Mailing List

Note

Nanagram 1.4 includes lots of changes and improvements on the previous versions. It's now faster, with several new features.

Nanagram the Word Jumbler

Introduction

An anagram is A word or phrase formed by reordering the letters of another word or phrase. For example, did you know that :

George W Bush is an anagram of 'whose bugger' [1]...
Tony Blair : 'bony trail'...
Ronald Reagan : 'adrenal groan' or 'loan aranged'...
Osama Bin Laden : 'bald nose mania' or 'bad neon salami'...
Mother Theresa : 'hot rare themes' or 'earth theorems'...
Michael Foord : 'cool firm head'... remember, the anagram never lies

Nanagram is a program for making anagrams. Astound and annoy your friends by discovering what silly anagrams can be made from their names. There is also an online version to play with [2].

Nanagram is shareware. There is a free demo version with a small dictionary and a restricted set of features. You can obtain the full version by visiting the Voidspace Shop.

Versions

You can try Nanagram in several different ways. All of these, as well as various other fun and interesting programs, can be found at Voidspace Shareware.

Demo Version

There is a freeware demo version of Nanagram available for download from the Voidspace Shop. Feel free to try it, and give it to all your friends.

This is a slightly restricted version, with the following limitations :

It displays a nag screen on opening and closing.
It is restricted to a much smaller dictionary.
You can't load new dictionaries.
You can't use the advanced options.

Other than that it is fully working, and still worth playing with.

There is also a Windows Executable Demo that doesn't need to be installed.

The Full Version

You can download the full version for the very low price of only £4.99.

Don't forget to join the Voidspace Shareware Mailing List, so that you hear as soon as new versions come out.

There is also a Windows Executable that doesn't need to be installed.

The Online Version

There is a free Online Version. It doesn't have all the features of the desktop gooey version, but is still a silly way to while away a few moments.

The Source Code

If you want to look at the Python source code, or use Nanagram on a non-windows platform, you can get the source to Version 1.3.

Nanagram 1.3 Source Distribution

This is released under the Voidspace Shareware License.

You will need Python and Tkinter installed to run it.

Using Nanagram

Using Nanagram is very easy. Type the words you want an anagram of and hit enter ! (or 'Go Nanagram'.)

You can include spaces, apostrophes or dashes etc, but they won't appear in the results.

Once you've produced a list of anagrams you can save it to a text file, for posterity and the greater benefit of mankind.

The Basic Options

Nanagram has a few simple options to control it's behaviour. These are all the options on the main GUI.

Some of these are useful for reducing the number of anagrams that Nanagram finds. When it finds hundreds, it can be difficult to pick out the really funny ones .

Nanagram will automatically show you anagrams using less words first (because these tend to be the best); but see the Hints for Searching section on how to use the Advanced options to further refine your search.

About

The About button launches this documentation page.

Quit

Can you guess what this does ?

Anagram Must Contain

This text entry box allows you to restrict the anagrams to ones containing a certain word or phrase.

For example, you might only want to find anagrams of Michael Foord that contain the word cool. Disturbingly enough, the results include :

Cool Firm Head

Cool if Harmed

I know which I prefer.

Using this feature can be especially useful for finding long anagrams. It effectively reduces the number of letters that Nanagram has to search through, making it quicker.

See Hints for Searching for how you can use this to speed up your searches for really long anagrams.

Min Word Length

This radio button lets you choose the minimum length of words that will be included in your anagram. The higher the setting here, the less anagrams it will return, but the faster it will work.

Output Whilst Thinking

It can be pretty boring waiting for Nanagram to finish its search. This option gets it to display the results as it finds them.

Be warned though, this means it can take much longer to find all the possible anagrams.

The output window has a Stop button on it, so you can halt Nanagram if it is taking too long. If you hit Stop, Nanagram will show you all the anagrams it has found so far.

Progress Bar

This option (on by default), shows you a progress bar while Nanagram is calculating the anagram. Having this on does slow down the process a bit, but nothing like so much as having Nanagram display the results as it finds them.

The progress bar also has a Stop button on it, in case you want to stop Nanagram before it has found all possible combinations.

Include Common Small Words

To search for anagrams at a reasonable speed it is normal to search with Min Word Length set to four or five letters. Unfortunately, this means that you might miss some interesting anagrams that could be found if you included such common words as a or if.

The Include Common Small Words (on by default) allows you to include 176 common small words (all three letters or less) in all your searches.

This does slow down the search, but not as much as choosing a lower value for Min Word Length.

In the full version you can add to this list (only words of three letters or less), but you will need to delete common.dat (in the dictionaries directory) and restart Nanagram for this to take effect.

Load New Dict

Nanagram uses a dictionary of words to search from. By default Nanagram uses 'dictionary.txt' which has (only) 57 000 words in it. You can increase the speed by using a smaller dictionary, or increase the number of anagrams found by using a bigger one - you can also add words to any of them if you want.

Whenever you load a dictionary it saves it out in its own format - this makes it quicker to load and also means Nanagram will automatically use the new dictionary next time.

To use a dictionary after adding new words, you need to either delete dictionary.dat or reload the dictionary using the Load New Dict button.

Note

Nanagram works with dictionaries that include accented characters (anything from the latin-1 character set). It actually maps them to their nearest ASCII equivalent - so e-acute matches for e etc - but they appear correctly when displayed. This means you should be able to use nanagram with non-English dictionaries.

The GUI

By the way, the name 'Nanagram - Gooey' comes from the computer term GUI which means Graphical User Interface. Unlike old fashioned computers where you had to type every command out , modern computers have given us fancy window based interfaces - with a lovely acronym... the GUI.

The Dictionaries

Nanagram comes with the following dictionary files. They are all located in the dictionaries directory. They are simple wordlists, with one word per line.

Note

You will only be able to use new dictionaries if you have bought the full version.

dictionary.txt (The default dictionary). This contains 57047 words.
smalldict (The dictionary used by the free trial version and also the online one). This contains 17890 word.
largedict.txt. This contains 117971 words.
french_dictionary.txt. A dictionary of 22740 French words.
verysmalldict.txt. A dictionary of the 3029 most common words.

If you want to experiment with some alternative dictionaries you can download the following zip file. It contains 3 extra English dictionary files, two very large and one very small.

Extra Dictionaries (1.3mb)

Hints For Searching

I've not set a maximum number of letters that Nanagram will let you enter. In practise I've found that any more than about 15 and Nanagram slows to a crawl (although it always returns the answers in the end... even if it takes a long time). Increasing the minimum number of letter setting helps, because it reduces the number of words that Nanagram has to check. Setting a 'containing' word has the same effect - it reduces the number of letters that Nanagram has to work with.

If you select the checkbox saying 'output whilst thinking' then Nanagram will open a temporary window and display anagrams as it finds them. This is less boring to watch but slows Nanagram down a lot.

Using Output Whilst Thinking, or the Progress Bar also gives you the option of stopping the search if it's taking too long. Hunting for anagrams is a 'processor-intensive' task, so the window can be unresponsive. It will do what you tell it in the end.

If you hit 'Go Nanagram' and nothing appears to happen - except maybe everything else on your computer slows down - then Nanagram is desperately searching its database for matches.

Sometimes it can take a minute or more to find matches. In fact I've waited ten minutes for some. 'Stephen Uncompromising' on my machine took 591 seconds even when set to 5 letters or more. Sometimes it can take so long that to all intents and purposes it's dead - and you have to close it down and start again.

Here are a couple of hints to avoid that happening :

Always do your first search with minimum word length set to five. It's less frustrating to try again with less letters than it is to have to restart Nanagram.
If you wonder if a set of words is too much, try just entering part of it and see how long Nanagram takes.
Using Contains greatly speeds a search. So - do a Partial Search First.

Sometimes you want to search for anagrams of someone's full name - Samuel Alexander Burling for example - but you know Nanagram ain't gonna cope.

If you do a partial search first - e.g. Samuel Burling - you will get several results. These include :
- umbrella suing
- numb guerrillas
- musing rubella
We can now do a search against the full name, but ask for only anagrams containing the word 'Guerrillas', or only anagrams containing the word 'umbrellas'. Because using the 'containing' section effectively reduces the number of letters that Nanagram has to match against - we can enter more words to start with.

We now get results like :
- urban guerrillas mend axle
- guerrillas axeman blunder
We could try a different search for anagrams containing rubella, or axeman to get a varied set of results - these in turn will throw up new words we can use as well.
To increase the variety of answers returned when searching with 4 or 5 letter minimum set - you can search for answers containing 'a' or 'an' or other smaller words. They wouldn't normally be returned when searching with the higher minimum size - but you sometimes find some interesting ones like this.

For example, my friend 'Daniel Lantsbery' has the anagram 'a tyrannised bell'. - if you just search with minimum letters set to 4 then you don't find it. If you try with 'containing' set to 'a', then it appears.
As a last resort, using one of the smaller dictionaries drastically improves search times.

The Advanced Options

There is also an Advanced button, which brings up a couple more interesting ways to refine the way Nanagram does it's searches. Here you get a choice of limiting the number of words that Nanagram will allow and also the maximum number of 'combinations' that it will find before quitting.

The maximum number of words is useful, simply because the most interesting anagrams usually only have two or three words. This also helps to speed up the search - once it's reached the maximum number of words it can give up with that combination.

Setting the maximum number of combinations that Nanagram will find before giving up is nearly the same as setting the maximum number of answers that it will find - but not quite ! If you look in the How it Works section you'll see that once it's found anagrams involving the word 'rare' it's also found ones involving the word 'rear', without doing any extra work !

This means if you set it to find 100 combinations - you might actually have 160 answers or so ! Again this can speed up the search - but it also means you might miss some of the most interesting anagrams. Even with this value set really low, it can still take Nanagram a long time to find answers if you give it a lot of letters. Even if their only are a few answers it might take a long time to find them....

Anyway - experiment with different combinations, the very worst thing that can happen is that you'll waste time when you're meant to be working.

How It Works

Ok, so I admit it... I didn't think up the idea for Nanagram entirely by myself. A craze amongst a few of my friends for using internet based anagram finders inspired me.

First off I wrote a short script that would find every possible combination of letters for a word. This was a nice exercise in remembering how recursion [3] works. Unfortunately, for every letter you add it increases the complexity of this algorithm by an order of magnitude, and it's long lists of jumbled letters aren't very useful anyway. You can have a look at this code (if you want) at word-jumble.py.

I knew that a dictionary based one, that checked for real words, was the only way forward.

Simple Explanation

We go through the full word list and compare it against the words we're matching. If a word is longer than the ones we're matching, or it contains letters not in the one we're matching, we discard it. This drastically reduces the number of words we have to check. If we set the minimum size of the words we are looking for we can also discard any words that are shorter than this.

Next we take each word, one by one. We remove it's letters from our words. We can then check the next word and see if it will fit what is left. If a word fits, we remove it's letters and start again with what is left...

We finally either get to the position where there are no letters left - a match, we have an anagram - or none of the words fit and we have to throw away that combination.

We do this in a loop to test against every word. Because once we have chopped some of the letters out we are effectively looking for any words that are an anagram (or partial anagram) of what is left - the function can just call itself. This is the recursion and means that the main loop is actually very short... only a few lines of code.

The whole program including the GUI and my comments is only 21k - but when I bundle it as a windoze executable the python core and graphics libraries make the whole program 7 MB... ouch.

There's one more neat trick to reduce the number of words we have to search against. This trick comes from the coder forum above.

A Neat Trick

You'll notice that some words are actually anagrams of each other - like rare and rear for example. If we find an anagram that involves the word rare, then if we swap rare for rear it will still be an anagram.

To make use of this the code forms a hash table of all words that are anagrams of each other. To do this we sort the letters of each word into alphabetical order (the 'hash'). For words that are anagrams of each other this will be the same. For both rare and rear the 'hash' will be 'aerr'.

We store a table of which words match which hash, and just search against the hashes (which is obviously a smaller list). When we have found our matches we just convert these hashes back into all the possible combinations. This saves us up to a third of the words we need to search for.

There's another neat trick as well. With what we've said so far, if there was an anagram found when we'd got to the word fish for example - say 'fish home rag' was an anagram - then when it got to the word home, it would also find 'home fish rag', in fact it would find 'home rag fish' and so on as well. With Nanagram, every time the loop finishes with a word it knocks it off the list. Having completely searched for anagrams using that word it knows it never has to check for that word again. This makes each loop progressively quicker and removes duplicates [4].

If you want to see the raw algorithm then check out Nana.py. This is the bare bones of the code from before I added the GUI. It is only 6k and is what became Nanagram-CGI.

TODO

The next version of Nanagram will include several great changes. It may take a few months to do though, so don't hold your breath.

The proposed improvements include :

Add a crossword 'word solver', for finding words when you know the length and a few of the words.
A better dictionary choosing dialog.
Better support for foreign languages.
Improve the save format.
Add a spellchecker. This could include a personal word list that is shared with the anagram dictionary.
A GUI option to add words to the dictionary.
Disable "include common short words" button, when minimum length is one.
Make output "whilst thinking" and "progress bar" mutually a radio bar along with a third ("neither") option.
Add an 'exclude words' option.
Save a config file with the last used settings.
If dictionary.txt isn't found raise an error dialog (plus a dialog to choose one).
Progress bar should be logarithmic, not linear.

If you have any more feature requests or suggestions, feel free to make them on the Mailing List.

CHANGELOG

28th Feb 2006 Version 1.4.0

Lots of changes :

Improved the GUI.
Sped up the anagram finding by around 20%.
Now built with Python 2.4 and psyco 1.5 for even more speed.
Added the progress bar.
Added the option to include common short words.
Optimised sorting the results.
We can now find anagrams where a word fits more than once into the original phrase.

Plus various other minor changes and improvements.

23rd Feb 2004 Version 1.3.1

Added support for non-English dictionaries (accented characters allowed now).

Also added the French dictionary to the dictionaries available for download.

21st Feb 2004 Version 1.3.0

Added another feature.... There is now a checkbox asking if you want it to output the results as it finds them. This slows down the search for anagrams, but is less boring. It also allows you to stop the search whilst it's in progress.

17th Feb 2004 Version 1.2.0

Added sorting to the results, so that anagrams using less words (and likely to be more interesting) are shown first.

Added the advanced options to set the maximum number of answers it finds and the maximum number of words to accept in the answers.

06th Feb 2004 Version 1.1.0

Added support for the psyco compiler. The executable is faster as a result. In the source code version it is only faster if psyco is installed.

Added support for loading alternative dictionaries. It also saves out the loaded dictionary in an internal format - both to avoid having to save a config pointing to the dictionary and to speed up the loading time.

Footnotes

[1]	And disturbingly enough, also he grew bogus.

[2]	You can also download the online version and include it on your own website (or just play around with the source code). See the Nanagram-CGI homepage.

[3]	Recursion is a neat trick when programming. You create chunks of code that call themselves. Of course using this technique it's very easy write code that never ends .

[4]	With the slight disadvantage that if a word is contained more than once in our phrase we won't discover this. The speed advantage makes it worth it though.

Nanagram (not Nangram as it is often misspelt) is a great anagram creator, anagram finder, anagram generator, anagram creator and word jumbler. It is written by Michael Foord, in the Python programming language.