Click here to Skip to main content
13,051,447 members (47,301 online)
Click here to Skip to main content
Add your own
alternative version


29 bookmarked
Posted 24 Nov 2003

Jumble Solving Utility

, 9 Nov 2005
Rate this:
Please Sign up or sign in to vote.
This program finds all the words in the dictionary that can be created from a jumbled word.


This program finds all the words in the dictionary that can be created from a jumbled word.


I've never been excellent at solving Jumbles, mainly because my vocabulary doesn't include some of the odd-ball words they like to use. A Jumble is a word problem that can be found in newspapers and on some websites like A basic Jumble problem is a bunch of letters that form a word when re-arranged. The solution to the problem is an anagram of the original jumbled word, Ex. lbujme -> jumble. This program will take the bunch of letters and give a list of any words (found in the dictionary) that can be formed from those letters.

Using the code

To use the code in your own application just include trie.cpp and trie.h to your project source, and #include "trie.h" when you want to use the class.

A very simple use of the class CTrie:

//Create the List
CTrie* List = new CTrie();

//Add a word to the List

//Get a vector of words from the List
vector<CHAR*>* all = List->GiveWords("lbujme");

//Output the results
if (all && !all->empty())
    vector<CHAR*>::const_iterator vai;
    int cnt = 0;
    for (vai = all->begin(); vai != all->end(); vai++, cnt++)
        cout << cnt + 1 << " " << *vai << endl;
    cout << "none" << endl;

Algorithm Outline

My algorithm uses the basis that the same number of any letter must occur in a word as the given jumbled word for the word to be formed from the jumbled word. In other words lbujme has: 1 B, 1 E, 1 J, 1 M, 1 L, 1 U, and jumble has: 1 B, 1 E, 1 J, 1 M, 1 L, 1 U. These are the same therefore you can make jumble out of lbujme. The data structure of my algorithm uses a binary tree. The tree starts off with the root node which contains a list of all the words with zero occurrences of the letter 'a'. The root node then can have left and right pointers. The left pointer points to the node with zero occurrences of the letter 'a' and zero occurrences of the letter 'b'. The right pointer points to the node with one occurrence of the letter 'a'. This can be expanded generally to say that going left in the tree means you move to the next letter. To go right means you add an occurrence of the current letter.

History prior to CodeProject

The first time I wrote my Jumble solving program was about five years ago. It took about five minutes to find all the possible words for a bunch of six letters. Eight letters I estimated would take half a day. I never did find out how long it took. Also the original program was written in Turbo Pascal; I could say that was the reason for the slow algorithm but must blame the programmer.

The original algorithm was to arrange the bunch of letters in all there possible combinations (including repeats of letters) and check if it was a word. For a six letter word this gives us 6^6 = 46656 words to check. Not too bad but I was also scanning the dictionary file every single time to check if the word existed or not. This was the major bottleneck, so I read all the words into memory once, and scanned the list. This improved the search time considerable but was still incredibly slow for eight bunches of letters. Also the basis of my algorithm was a whole lot of if statements, making expanding to anything beyond eight letters tedious at best.

I eventually improved the algorithm to remove repeats of letters. This meant that instead of 6^6 = 46656 words to check I had to check 6! = 720 words. A vast improvement. Years passed...and I decided to code the Jumble program again, this time in C++ :). I did exactly the same algorithm and still came across a huge barrier when using words greater then size of eight. The problem sat in the back of my mind and a new algorithm popped into my head. I could count the number of times a letter occurred in the jumbled set of letters and count the number of times a letter occurred in a word and compare the two. This worked wonders and improved the algorithm drastically. But, I had no nice data structure for finding if a word belonged to a certain jumbled set.

University courses gave me trees, from which my jumble tree was born. Now the program takes a few seconds to load up and a few to shut down but searching is 26 pointers away (in the worst case). I've cleaned up the code, separated it into classes and posted it here. Obviously this program is pointless with this web site but has been an adventure thus far. I'm sure improvements can still be made, and look forward to feedback.

Possible Future Updates

Implement a Directed Acyclic Word Graph [DAWG] structure to save memory, and time stepping through structure.
Test other algorithms.


  • 8 November 2003 - v1.0
    First public release
  • 2 December 2003 - v1.1
    Changed class and file names
    Changed return type of GiveWords() to vector<CHAR*>*
    Added .NET Demo Project


This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


About the Author

Web Developer
Canada Canada
No Biography provided

You may also be interested in...

Comments and Discussions

Generala simpler algorithm Pin
peatrick29-Aug-07 11:13
memberpeatrick29-Aug-07 11:13 
GeneralThanks greba :) Pin
rzs4-Mar-07 4:45
memberrzs4-Mar-07 4:45 
GeneralAnagrams generation Pin
Girish Mahadevan2-Jan-07 19:12
memberGirish Mahadevan2-Jan-07 19:12 
GeneralRe: Anagrams generation Pin
greba3-Jan-07 3:04
membergreba3-Jan-07 3:04 
GeneralRe: Anagrams generation(greb) Pin
Girish Mahadevan3-Jan-07 18:16
memberGirish Mahadevan3-Jan-07 18:16 
QuestionPort to CSharp? Pin
Doncp22-Dec-06 8:08
memberDoncp22-Dec-06 8:08 
AnswerRe: Port to CSharp? Pin
Doncp24-Dec-06 12:32
memberDoncp24-Dec-06 12:32 
GeneralSimple Addition for BIG Improvement Pin
Humble Programmer9-Nov-05 21:27
memberHumble Programmer9-Nov-05 21:27 
Generalfile version Pin
wrax29-Oct-05 1:49
memberwrax29-Oct-05 1:49 
GeneralRe: file version Pin
greba9-Nov-05 7:32
membergreba9-Nov-05 7:32 
Generalnice Pin
wrax28-Oct-05 5:02
memberwrax28-Oct-05 5:02 
GeneralI once had a similar program... Pin
Fredrik6-Nov-04 12:11
sussFredrik6-Nov-04 12:11 
GeneralThats Wonder!!! Pin
Balkrishna Talele16-Feb-04 23:41
memberBalkrishna Talele16-Feb-04 23:41 
GeneralCan't compile in VC7 Pin
Art Friesz2-Dec-03 6:00
memberArt Friesz2-Dec-03 6:00 
GeneralRe: Can't compile in VC7 Pin
greba2-Dec-03 20:36
membergreba2-Dec-03 20:36 
GeneralAnagram Solver Pin
Bruce Duncan26-Nov-03 18:40
memberBruce Duncan26-Nov-03 18:40 
GeneralNotes from a pedant. Pin
Iain Clarke26-Nov-03 0:16
memberIain Clarke26-Nov-03 0:16 
GeneralAnagram vs. Jumble Pin
greba26-Nov-03 15:53
membergreba26-Nov-03 15:53 
GeneralRe: Anagram vs. Jumble Pin
Joe Nellis29-Nov-03 6:25
memberJoe Nellis29-Nov-03 6:25 
GeneralA very similar problem Pin
Joe Nellis25-Nov-03 15:55
memberJoe Nellis25-Nov-03 15:55 
GeneralRe: A very similar problem Pin
greba26-Nov-03 15:59
membergreba26-Nov-03 15:59 
GeneralRe: A very similar problem Pin
treenef8-Jan-05 3:20
membertreenef8-Jan-05 3:20 
GeneralRe: A very similar problem Pin
treenef8-Jan-05 3:24
membertreenef8-Jan-05 3:24 
GeneralRe: A very similar problem Pin
greba10-Jan-05 3:42
membergreba10-Jan-05 3:42 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.170713.1 | Last Updated 9 Nov 2005
Article Copyright 2003 by greba
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid