Need find words in a given set of letters

[coroll]

Hi,

I want to find all the words(scabble words) that can be made out of given set of letters.
ex: abnana

results: a aa ab an baa ban banana na nab

How could i achieve this? Do i need a binary tree?
Plz some one help me...

[deceptikon]

This seems more like a job for a frequency list. You can use a dictionary of characters and counts like so:

for each word in the dictionary
    build a frequency list of each character initialized to 0

    for each character in the letter collection
        if the character exists in the frequency list
            increment the count for that character

    if all counts in the frequency list are greater than 0
        mark the word as a match

[gusano79]

I think the question is actually "how do I generate permutations?"

[deceptikon]

I think the question is actually "how do I generate permutations?"

"nab" isn't a permutation of "abnana". Permutations can get you closer to a complete solution, but that's not all there is to it.

[coroll]

Im a student so Im not expert in java.But not even too much low.
I dont understand the frequency list.
If u could please explain the psuedo code a bit?

[deceptikon]

I dont understand the frequency list.

http://en.wikipedia.org/wiki/Letter_frequencies.

If u could please explain the psuedo code a bit?

You're basically just matching at least one of every letter in a given word using the available tiles that the player currently has. All of the words that meet this requirement are words that the player can make with his or her tiles.

[JamesCherrill]

Probably the easiest way is to put all the words in a TreeMap (for fast searching) then check every permutation of every subset of your letters to see if it's in the TreeSet. However that will generate a lot of searches if you have a lot of letters, which may or may not make it too slow.

You can speed up the search, at the cost of more work at startup time, by building a TreeMap. For each word sort its letters into order and use that as the key; the word (or words)corresponding to that form the value. Now you just need to test each subsets of your letters once - keep them sorted and see if the subset is a valid key. There's no need to test all the permutations.

Decepticon's solution may be faster or easier than either of these, but I'm ashamed to admit that I don't understand it.

[deceptikon]

Decepticon's solution may be faster or easier than either of these, but I'm ashamed to admit that I don't understand it.

Here's a quickie example to show what I mean. Please excuse the crappy Java, I'm terribly rusty:

import java.util.*;

class Foo {
    public static void main(String args[])
    {
        String[] dictionary = {
            "za",  "zoo", "a",      "aa", "ab",  "an", 
            "baa", "ban", "banana", "na", "nab", "test"
        };
        String word = "abnana";

        for (int i = 0; i < dictionary.length; i++) {
            TreeMap<Character, Integer> freq = new TreeMap<Character, Integer>();

            for (int j = 0; j < dictionary[i].length(); j++)
                freq.put(dictionary[i].charAt(j), 0);

            for (int j = 0; j < word.length(); j++) {
                if (freq.containsKey(word.charAt(j)))
                    freq.put(word.charAt(j), freq.get(word.charAt(j)) + 1);
            }

            boolean match = true;

            for (int count : freq.values()) {
                if (count <= 0) {
                    match = false;
                    break;
                }
            }

            if (match)
                System.out.println("'" + dictionary[i] + "' was found");
        }
    }
}

[JamesCherrill]

OK, thank you. That seems functionally equivalent to creating a key that contains the letters in the word but sorted - ie its a way of identifying words that is independent of the order in which its letters appear. (Correct me if I'm wrong, please.)

[deceptikon]

ie its a way of identifying words that is independent of the order in which its letters appear.

Yes, pretty much.

[gusano79]

"nab" isn't a permutation of "abnana". Permutations can get you closer to a complete solution, but that's not all there is to it.

True, you'd also need to look at subsets of the original set of letters.

For completeness, you'd also want to consider a nonempty game board, which would involve finding words with specific letters in fixed positions.

[coroll]

Here's a quickie example to show what I mean. Please excuse the crappy Java, I'm terribly rusty:

Thank you very much.
I get it now and you just saved me :-)

[Todor]

Hello, i tried implementing your solution @Deceptikon. I am doing similar project like the author posted, but the thing with your code is it doesn't count for repeated letters, so word ban, will give banana from dictionary, which is not valid. Does anyone know how to sort this problem out.
Thanks for your response in advance.

[JamesCherrill]

After that discussion I implemented a general version that works correctly. It takes each word in the dictionary and sorts its letters into ascending order then adds that to a Map (sorted letters as key, list of matching original words as value).
To make searching faster I actually created an array of maps, one for each word length, but that's maybe over-thinking it.

[Todor]

Thats pretty cool idea, thanks :)

[JamesCherrill]

Yes.
I was amazed by the performance. Loading the map with over a quarter of a million words from an official scrabble list takes under a second. Searching for anagrams goes as fast as you can type (which you would expect with a tree map), but searching the original strings for words with some specified letters in particular places is also seemingly instant. I didn't implement searching for anagrams with specified letters in specific places, but that woud be very easy and also instant.