Author Options:

Calling All Programmers (Yes, ALL) Answered

Every now and then in typing class, our teacher will give us a handful of letters, and we're given about 5 minutes to come up with as many words as we can from these letters. So today I thought... what if there was a program where you could input a string of letters, and it would spit out as many words as possible that can be made out of those letters. A quick Google search was less than fruitful. So, to the more techier of my fellow Iblians, how would you go about writing a program that could do this? I'm thinking something where you input a string of letters, and then it scans, say, an online dictionary, to find as many words as possible from the inputted letters. Sound doable?


it must exist! it was in national treasure!

(He's the guy who is running all that equipment in the movie)

... i thought Nicholas Cage movies were jessyratfink's thing..

A program that would do that would have immense outputs. To be precise, the number of letters factorial. For example, 10 letters would have 3,628,800 different combinations. As for adding a filter to only output actual words, then you would have to use some sort of dictionary function... Which I don't recall being in any programming language I have learned. Making a commandline program wouldn't be hard, as long as you found a dictionary checking program to call. Or, possible some PHP to interface dictionary.com and use the resulting page to determine whether or not it is a word. It all depends on the lengths of the word though... loading a webpage 3,628,800 times would take a long time, not to mention processing the results.

there is a CLASS in javascript called Dictionary.js which may be useful in this case.

browser based languages are kinda limited in interaction with files, so it would have to be completely self contained, I'm guessing. But hey, I don't know. I don't have much experience with JavaScript.

JavaScript can be Client run, or Server run and, as far as I know, it is not browser dependent (not dependent on one browser that is). Still, a language more like Perl or C# may be better for writing the "sort"

I would not reccommend JScript for this sort of thing... It has some real issues with datatypes and complicated operations... I'd do it in ANSI C, because although memory management and garbage collection are easy to mess up, the control to quickly create complicated custom data indexing methods is awesome... at the same time, for a recursive program like this, a FUNCTIONAL programming language would be a perfect fit... I've changed my opinion in mid thought... USE SML. IT WILL BLOW YOUR MIND for this sort of program.

Hmm, I had not heard about Standard ML before your mention of it.....but I see where it has great strengths in this area: SML Link

Remember that to a computer, 3 million does not equal "immense". The computer could generate all 3,628,800 possible combinations in seconds, and check them against a 100,000 word dictionary easily. The most efficient way of making words and checking them is an interesting programming puzzle. I'd be tempted to generate the shorter combinations first (so make words like "as" and "in", then "ask" and "ink", etc.) and check those against the dictionary (looking up a word in a dictionary is a very time-efficient task if the dictionary is stored on the computer in the right way) before writing the existing words out to a list. In fact, the description I've given above is half the program already. Labot: Do you actually want to write this program? If so, what languages do you know?

I made a program that generated all of the 3,628,800 10 letter words-- just a quick command line program-- and it took 31.28 seconds. This is just the 10 letter words- All of them would be 10! + (2)9! + (3)8! + (4)7! + (5)6! + (6)5! + (7)4! + (8)3! + (9)2! + (10)1!. The total of ALL possible combinations would be 4500244. This would take almost twice as long, and that's without even looking them up. Not to mention, I doubt there is just this 100,000 word outsourcing dictionary... It would have to be built directly into a programming language.... Like javascript (So goodhart says. Idk, I don't have any expierience in web-programming except for a little of the basic HTML)

"unabr.dict" at this site is a 2.2MB file that is simply a text file containing a list of every word from an unabridged dictionary separated by newline characters. Just the words, not the definitions- exactly what you need for this task. From a programming perspective it would be trivial to read that into your program into a large array and check the words you generated against the list- many higher-level languages have a single function, called Split or similar, to do exactly that.

If you do download that file, be careful with it- I loaded the file into Word 2007 and tried to do a word count. The word count crashed Word, and that's on my work machine with a Core2 Quad and 4GB of RAM O_O


Reply 9 years ago

With a bit of cajoling I found out it's about 345,000 words- don't try dealing with that using javascript or a command line program...

I used "type" from the command line and it took a good 8 minutes for it to print the entire list. If this was used, it would HAVE to be split into different files based on length, first letter, or both, etc.

If you were going to do it with a batch file program or Windows command line stuff, yes it would be. The alternative is to use a lower-level language like C and/or a more efficient method to generate the words, and I guarantee you a well-written C program could deal with that entire dictionary as one file and generate all the possible words from ten letters in seconds, not minutes. Think about the files that Photoshop or a modern game deal with- they make a 2MB text file seem inconsequential. I'm actually tempted to write this program having spent so long discussing it. brb, coding :)

Maybe separate it into several different text files, maybe by first letter. I tried to open it... It crashed notepad.

Perhaps you need an anagram solver?

Note that bumpus has posted something similar, and from the look of it possibly better.


simple trick that cuts processing time... sort your letters alphabetically and sort your dictionary alphabetically... store your dictionary in a tree arranged such that each node has up to 26 children, identified by letter, and a value containing all words that alphabetized path from root to node contains.... then you can perform a depth first search that atempts each possible alphabetized path you can get from a subset of the letters... the cool part is that because it's depth first, and recursive, the number of operations per scan is tiny.... You could also make a strong case for hash tables... In any event, I reccomend memoising the operations, if space is not an issue... that way, once you get a subset's response once, its a single operation for every future recall. YAY... SHOUT OUT TO PROF RUDICH

How many letters? If they really are only a handful, the simplest way would be to use a simple bubble sort and make as many combinations as possible and then spell check them with a good spell checker.

If there are more then say, 8-10 letters, you get into both a time bind, and an overwhelmingly large number of words to look through.

just google anagram programs.