12,951,548 members (51,018 online)
alternative version

#### Stats

153.9K views
29 bookmarked
Posted 24 Nov 2003

# Jumble Solving Utility

, 9 Nov 2005
 Rate this:
This program finds all the words in the dictionary that can be created from a jumbled word.

## Introduction

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

## Background

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 jumble.com. 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;
}
else
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.

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

## History

• 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*>*`

A list of licenses authors might use can be found here

## Share

No Biography provided

## You may also be interested in...

 First Prev Next
 a simpler algorithm peatrick29-Aug-07 11:13 peatrick 29-Aug-07 11:13
 Thanks greba :) rzs4-Mar-07 4:45 rzs 4-Mar-07 4:45
 Re: Anagrams generation greba3-Jan-07 3:04 greba 3-Jan-07 3:04
 Port to CSharp? Doncp22-Dec-06 8:08 Doncp 22-Dec-06 8:08
 Re: Port to CSharp? Doncp24-Dec-06 12:32 Doncp 24-Dec-06 12:32
 Simple Addition for BIG Improvement Humble Programmer9-Nov-05 21:27 Humble Programmer 9-Nov-05 21:27
 file version wrax29-Oct-05 1:49 wrax 29-Oct-05 1:49
 Re: file version greba9-Nov-05 7:32 greba 9-Nov-05 7:32
 nice wrax28-Oct-05 5:02 wrax 28-Oct-05 5:02
 I once had a similar program... Fredrik6-Nov-04 12:11 Fredrik 6-Nov-04 12:11
 Thats Wonder!!! Balkrishna Talele16-Feb-04 23:41 Balkrishna Talele 16-Feb-04 23:41
 Can't compile in VC7 Art Friesz2-Dec-03 6:00 Art Friesz 2-Dec-03 6:00
 Re: Can't compile in VC7 greba2-Dec-03 20:36 greba 2-Dec-03 20:36
 Anagram Solver Bruce Duncan26-Nov-03 18:40 Bruce Duncan 26-Nov-03 18:40
 Notes from a pedant. Iain Clarke26-Nov-03 0:16 Iain Clarke 26-Nov-03 0:16
 Anagram vs. Jumble greba26-Nov-03 15:53 greba 26-Nov-03 15:53
 Re: Anagram vs. Jumble Joe Nellis29-Nov-03 6:25 Joe Nellis 29-Nov-03 6:25
 A very similar problem Joe Nellis25-Nov-03 15:55 Joe Nellis 25-Nov-03 15:55
 Re: A very similar problem greba26-Nov-03 15:59 greba 26-Nov-03 15:59
 Re: A very similar problem treenef8-Jan-05 3:20 treenef 8-Jan-05 3:20
 Re: A very similar problem treenef8-Jan-05 3:24 treenef 8-Jan-05 3:24
 Re: A very similar problem greba10-Jan-05 3:42 greba 10-Jan-05 3:42
 Last Visit: 31-Dec-99 18:00     Last Update: 26-May-17 5:02 Refresh 1