Scrabble algorithm

If you are playing scrabble and you have n letters, what are all the possible words that you can make from these n letters?

It looks as if it would involve permutations and combinations both of the letters or a union of permutations and combinations for n letters. Surprisingly, it is much simpler.

Below are the possible words for letters 'abc'. I have highlighted the patterns in them.

a
ab
abc
ac
acb
b
ba
bac
bc
bca
c
ca
cab
cb
cba

For n letters, it looks like we have to get permutations of n letters plus permutations of n-1 letters and so on till permutations of each letter which is O(nPn) + O(n-1Pn-1) + ... O(1P1). The time complexity is O(n!) + O(n-1!) + ... + O(1!) = O(n!).

All possible words for n letters can be obtained by using the permutations algorithm of n letters with a very simple mod in O(n!) time itself. The changes are in blue.

permutation(char[] in):
    //initially, used[] set to false and depth is 0
    permuteWords(in, out, used, 0)

permuteWords(char[] in, buffer out, bool[] used, int depth):
    if depth > 0:
        print(out)  
    if depth == in.length:
        print(out)
        return
    for (int i = 0; i < in.length; i++):
        if used[i] == true:
            continue
        used[i] = true
        out.append(in[i])
      
        permuteWords(in, used, out, depth +1)
        
        out.length = out.length -1 
        used[i] = false

Time complexity is the same as that of permutation algorithm O(n!).

A better way is to have each word added to a list (the list would be created in permutation method and passed as parameter to permuteWords method) for extensions of the problem. 

Possible extensions to this scrabble problem are:

• Find the longest word. 
• Find the word with maximum points given a map of points to each letter.
• You have a dictionary, how would you use it to get the valid words? For this, I would assume that the dictionary has a function like boolean isValidWord(String s) which would indicate if a particular word is valid or not. Here is another interesting thought with the dictionary extension which requires a trie structure. I could use a dictionary, to see if I can bust out of permuting further as mostly not all permutations are going to be valid words. For example, if you have a dictionary implemented as a trie with a function boolean hasPrefix(String s) or hasPrefix(char c) and letters 'aabc' and suppose that the dictionary does not have a trieNode structure a-a, you do not have to permute further for the unused characters 'bc'. Below is the changed code that I came up with (not tested).  

Set getValidWordsPermutation(char[] in): 
    Set validWords = new HashSet();
    //initially, used[] set to false and depth is 0
    permuteWords(in, out, used, 0, validWords);
    return validWords;

permuteWords(char[] in, buffer out, bool[] used, int depth, Set validWords): 
    // if the current prefix is not present in the dictionary, then do not permute further with the rest of the unused letters
    if !dict.hasPrefix(out): //or dict.hasPrefix(out[out.length()]) 
        return

    if depth == in.length:
        return

    for (int i = 0; i < in.length; i++):
        if used[i] == true:
            continue
        used[i] = true
        out.append(in[i])

        //if current prefix is a word, add to the set
        if dict.isValidWord(out):
            validWords.add(out)
        
        permuteWords(in, used, out, depth +1, validWords)
        
        out.length = out.length -1 
        used[i] = false

Using the dictionary, only those trieNodes forming valid words possible from the n letters are traversed in the dictionary trie [O(|V|+|E|) time] and not all permutations [O(n!) time]. If all permutations are valid words OR if there is no such hasPrefix(String s) function for trie, then it takes O(n!) time - which is better than O(nCn * n!) + O(nCn-1 * n-1!) + ... O(nC1 * 1!). 


[Hat tip to OJ]