ansaurus

Question

Answer 1

+1 A:

Your question boils down to the following basic algorithms:

Generate all possible subsets of a given set
- Most easily done with a bitfield counter
Generate all permutations of a set
- Pseudocode description and diagram
- A more specific implementation for .NET strings

I should also note that one problem with your current code is that all your inner loops start from 0, which is not correct. This is why "AA" is generated (because you end up returning the character for index 0 twice).

A bitfield counter in Java

package com.stackoverflow.samples;

import java.lang.String;

public class Main {
    public static void main(String[] args) {            
        String input = "ABCDE";        
        printAllSubsets(input);
    }

    private static void printAllSubsets(String input) {
        int n = input.length();
        int last = 2 << n;
        char[] subset = new char[n];

        for (int bits = 0; bits < last; ++bits) {
            int j = 0;
            for (int i = 0; i < n; ++i) {
                if (bitIsSet(bits, i)) {
                    subset[j] = input.charAt(i);
                    ++j;
                }
            }

            printSubset(subset, j);
        }
    }

    private static void printSubset(char[] subset, int n) {
        System.out.print('{');

        for (int i = 0; i < n; ++i) {
            System.out.print(subset[i]);
        }

        System.out.println('}');
    }

    private static boolean bitIsSet(int bits, int position) {
        return ((bits >> position) & 1) == 1;
    }
}

bobbymcr 2009-12-06 17:43:51

I'm sorry. I'm not exactly sure what you mean. Presently, my Java knowledge is rather... limited.

Jake Brooks 2009-12-06 17:49:09

Which part(s) of my answer are you having trouble with?

bobbymcr 2009-12-06 17:51:45

The bitfield counter, not exactly sure how it works or what it does.

Jake Brooks 2009-12-06 17:54:56

Okay, imagine you have an input string {ABC}. The possible substrings (including empty and the string itself) are {}, {A}, {B}, {C}, {AB}, {AC}, {BC}, {ABC}. Note that there 2^3 = 8 subsets in the 3 element set. If you think carefully, you can see that you can generate these subsets by just counting from 0 to 7 in binary: 000, 001, 010, 011, 100, 101, 110, 111. The 1 represents a letter, and the 0 means no letter, so 110 would be 'AB' and 101 would be 'AC'.

bobbymcr 2009-12-06 18:02:43

Can you demonstrate an example of how this can be implemented in Java? I am pretty sure I understand the logic behind it.

Jake Brooks 2009-12-06 18:11:22

Added a Java sample.

bobbymcr 2009-12-06 18:55:20

Thanks! I will post my new algorithm when finished.

Jake Brooks 2009-12-06 19:05:00

I tried to compile your example, and bitIsSet cannot be found?

Jake Brooks 2009-12-06 19:07:54

`bitIsSet` is the bottom static method in the Main class (last ~3 lines of my sample code).

bobbymcr 2009-12-06 19:11:26

Yes. But when compiled this error is generated."Cannot find symbol - method bitIsSet(int,int)

Jake Brooks 2009-12-06 19:14:55

Well, it works for me in Eclipse 3.4 with JDK 1.6. Maybe try calling it using `Main.bitIsSet` instead of just `bitIsSet`?

bobbymcr 2009-12-06 19:18:38

Nope. Is there something I need to import that I am missing?

Jake Brooks 2009-12-06 19:23:36

Odd. I tried Netbeans instead of BlueJ and it worked perfectly.

Jake Brooks 2009-12-06 19:51:37

One thing missing from the solution is that these are not just sets, they are ordered. ABC is not in the dictionary, CAB is.

MattMcKnight 2009-12-07 03:38:50

@MattMcKnight: Right, above I said there are 2 algorithms needed -- one for the subsets and one for the permutations.

bobbymcr 2009-12-07 04:32:34

Answer 2

+1 A:

You could build a trie out of the dictionary and traverse it. For each character in the input string, go to the corresponding node in the trie, remove the character from the input and repeat recursively.

Pseudo-code:

function check(trie_node)
    if trie_node is terminal
        output trie_node
    else
        for each child of trie_node
            let c be the character of the child
            if input contains at least one c
                remove one c from input
                check(child)
                put c back into input
            end
        end
    end
end

check(trie_root)

You could use a lookup table to quickly check how many of a certain character there are left in the input (constant time check).

Josef Grahn 2009-12-06 17:45:07

Can you show me an example?

Jake Brooks 2009-12-06 17:49:44

Here is a Java Trie implementation: http://trie.googlecode.com/svn/trunk/trie/src/net/bcharris/trie/(Code licensed under the Apache License 2.0: http://www.apache.org/licenses/LICENSE-2.0 .)

bobbymcr 2009-12-06 17:54:42

Answer 3

A:

In Python:

import itertools
mystring = "ABCDEFG"
for perm in itertools.permutations(mystring):
    print "".join(perm)

And if you want to see the algorithm, just look at the source/docs:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

Tim Pietzcker 2009-12-06 17:49:35

Answer 4

+1 A:

I would approach this by first unifying all of your dictionaries into one giant dictionary, and then sorting the letters in the dictionary you build and the word you're searching for subsets of called searchWord.

I would do something like this

String findAllScrabbleWords (String searchWord)
  searchWord = searchWord.sortLetters();

  Dictionary<String,List<String>> wordlist = new Dictionary <String, List<String>>()

  foreach file in fileList
    foreach word in file
    sortedword = word.sortLetters();
    // Add a new key if it isn't there then add the new word
    if (!wordlist.containsKey(sortedword))
      wordlist[sortedword] = new List<String>();
    wordlist[sortedword].add(word);
  end

  // Now search for the words.
  return findScrabbleWords ("", sortedword, wordList);

end

// We do this recursively so we don't have to worry about how long the search
// string is. 
String function findScrabbleWords (String headString, String tailString, Dictionary<String,List<String>> wordList)
  if (tailString == "")
    return "";
  end

  String returnValue = "";

  for (pos = 0; pos < tailString.length; pos++)

    // Add an element of the tail to the current string and remove
    // that letter from the tail.
    String currString = headString + tailString[pos];
    String remainderString = tailString.removeAt(pos,1);

    if (wordList.containsKey(currString))
      foreach word in wordList[currString]
        returnValue += word + " ";
      end
    end

    // Now check the strings that contain the new currString
    returnValue += findScrabbleWords(currString,remainderString,wordList);

  end

  return returnValue;
end

John 2009-12-06 18:11:55

Answer 5

A:

Jon Bentley's book, Programming Pearls, has a great example of doing this for anagrams and I'm sure you could adapt it. See the code for column 2 (or even better grab the book!).

I'll sketch out an implementation here:

1) Go through a dictionary, for each word sort the letters into order (e.g. fish would become "fihs", "donkey" would become "dekony". This key will allow you to look up all the words that can be made with this series of letters. Store this information in a data structure Map<String,Set<String>>. For example, for the word dog you'd end up with two entries dog -> (god,dog).

3) Now when you want to find a word, sort the sequence of letters in the rack as described above and query the map (e.g. look up the key in the Map you've made). This'll give you the list of all possible words made from that series of letters.

You'll have adapt this a little for Scrabble because the original algorithm was for anagrams, but it should be as simple as just querying the map more times (e.g. if you have the letters dayvgea then you'd need to query not only for aadgeyv, but also for each combination of 6 letters and below. The number of distinct combinations of 7 items is only 128, so to find the best word you'll only need a fixed number of lookups in the data structure.

Jeff Foster 2009-12-06 18:24:44

Note that this is the same idea that John has used in another answer!

Jeff Foster 2009-12-06 18:25:15

Answer 6

A:

I appreciate all the help you have all provided. I took a simpler approach, here it is: It seems to be quite efficient, but I still plan to investigate all the alternatives you posed.

public class Unscramble 
{
 public final static String letters = JOptionPane.showInputDialog("Please input your tiles").toLowerCase();
 public static LinkedList<String> words = new LinkedList();

 public static void main(String[] args) throws FileNotFoundException, IOException 
 {
  checkWords(new FileReader("ospd3.txt"));
  for(int i = 0; i < words.size(); i++)
  {
   System.out.println(words.get(i));
  }
 }
 private static void checkWords(FileReader dict) throws IOException
 {
  BufferedReader bf = new BufferedReader(dict);
  String line = "";
  while((line = bf.readLine()) != null)
  {
   if(hasWord(line))
   {
    words.add(line);
   }
  }
  bf.close();
  dict.close();
 }
 public static boolean hasWord(String word)
 {
    String copy = letters;
    for(int u = 0; u < word.length(); u++)
    {
        if(copy.contains(String.valueOf(word.charAt(u))))
     {
        copy = copy.replaceFirst(String.valueOf(word.charAt(u)), "");
     }
     else
     {
        return false;
     }
    }
    return true;
 } 
}

Jake Brooks 2009-12-07 20:50:48

ansaurus

tags:

views:

answers:

Scrabble Anagram Generator

A bitfield counter in Java

related questions