1

我正在尝试编写一个拼字游戏字谜生成器。

到目前为止，我的代码可以正常工作，但是速度非常慢，并且有错误。一个是它会不止一次地使用字母。例如：输入的字母：“ABCDEFG”。它会产生AB，但也会产生AA，这是不对的。

请帮忙。

public class Scrabble1
{
    private String[] dictionary2 = new String[97];
    private String[] dictionary3 = new String[978];
    private String[] dictionary4 = new String[3904];
    private String[] dictionary5 = new String[8635];
    private String[] dictionary6 = new String[15225];
    private String[] dictionary7 = new String[23097];
    public void sampleMethod(String s) throws FileNotFoundException
    {
        File in2 = new File( "dictionary2.txt" );
        File in3 = new File( "dictionary3.txt" );
        File in4 = new File( "dictionary4.txt" );
        File in5 = new File( "dictionary5.txt" );
        File in6 = new File( "dictionary6.txt" );
        File in7 = new File( "dictionary7.txt" );        
        Scanner dict2 = null,dict3 = null,dict4 = null,dict5 = null,dict6 = null,dict7 = null;

        try
        {
            dict2 = new Scanner(in2);
            dict3 = new Scanner(in3);   
            dict4 = new Scanner(in4);
            dict5 = new Scanner(in5);
            dict6 = new Scanner(in6);  
            dict7 = new Scanner(in7); 
            int c = 0;
            while(dict2.hasNext()&&dict3.hasNext()&&dict4.hasNext()&&dict5.hasNext()&&dict6.hasNext()&&dict7.hasNext())
            {
                dictionary2[c] = dict2.next();
                dictionary3[c] = dict3.next();
                dictionary4[c] = dict4.next();
                dictionary5[c] = dict5.next();
                dictionary6[c] = dict6.next();
                dictionary7[c] = dict7.next();
                c++;
            }
        }
        catch( FileNotFoundException e )
        {
            System.err.println( e.getMessage () );
            System.exit(1);
        }
        finally
        {
            dict2.close();
            dict3.close();
            dict4.close();
            dict5.close();
            dict6.close();
            dict7.close();
        }

       // for(int i= 0; i<80612; i++)
            //System.out.println(dicArray[i]);


        String temp = "";
        //All 2 letter anagrams  
        for(int k=0; k<=6; k++)
            for(int i=0; i<=6; i++)
                for(int d= 0; d<97; d++)
                {
                    temp = "" + s.charAt(k) + s.charAt(i);
                    if(temp.equals(dictionary2[d]))
                        System.out.println(temp  );
                }

        //All 3 letter anagrams  
        for(int j = 0; j<=6; j++)
            for(int k=0; k<=6; k++)
                for(int i=0; i<=6; i++)
                     for(int d= 0; d<978; d++)
                          {
                                temp = "" + s.charAt(j) + s.charAt(k)+ s.charAt(i);
                                if(temp.equals(dictionary3[d]))
                                    System.out.println(temp  );
                          }
        //All 4 letter anagrams  
        for(int j = 0; j<=6; j++)
            for(int k = 0; k<=6; k++)
                for(int i=0; i<=6; i++)
                    for(int l=0; l<=6; l++)
                          for(int d= 0; d<-3904; d++)
                          {
                                temp = "" + s.charAt(j) + s.charAt(k)+ s.charAt(i)+ s.charAt(l);
                                if(temp.equals(dictionary4[d]))
                                    System.out.println(temp );
                          }
         //All 5 letter anagrams
         for(int j = 0; j<=6; j++)
            for(int k = 0; k<=6; k++)
                for(int i=0; i<=6; i++)
                    for(int l=0; l<=6; l++)
                        for(int f=0; f<=6; f++)
                          for(int d= 0; d<8635; d++)
                          {
                                temp = "" + s.charAt(j) + s.charAt(k)+ s.charAt(i)+ s.charAt(l)+s.charAt(f);
                                if(temp.equals(dictionary5[d]))
                                    System.out.println(temp  );
                          }
          //All 6 letter anagrams
          for(int j = 0; j<=6; j++)
            for(int k = 0; k<=6; k++)
                for(int i=0; i<=6; i++)
                    for(int l=0; l<=6; l++)
                        for(int f=0; f<=6; f++)
                            for(int g=0; g<=6; g++)
                          for(int d= 0; d<15225; d++)
                          {
                                temp = "" + s.charAt(j) + s.charAt(k)+ s.charAt(i)+ s.charAt(l)+ s.charAt(f)+ s.charAt(g);
                                if(temp.equals(dictionary6[d]))
                                    System.out.println(temp  );
                          }
          //All 7 letter anagrams.
          for(int j = 0; j<=6; j++)
            for(int k = 0; k<=6; k++)
                for(int i=0; i<=6; i++)
                    for(int l=0; l<=6; l++)
                        for(int f=0; f<=6; f++)
                            for(int g=0; g<=6; g++)
                                for(int p=0; p<=6; p++)
                          for(int d= 0; d<23097; d++)
                          {
                                temp = "" + s.charAt(j) + s.charAt(k)+ s.charAt(i)+ s.charAt(l)+ s.charAt(f)+ s.charAt(g)+ s.charAt(p);
                                if(temp.equals(dictionary7[d]))
                                    System.out.println(temp  );

                          }




    }
}

字典文件只是按字长排序。

4

6 回答 6

1

您的问题归结为以下基本算法：

我还应该注意，您当前代码的一个问题是您的所有内部循环都从 0 开始，这是不正确的。这就是生成“AA”的原因（因为您最终会返回索引 0 的字符两次）。

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;
    }
}
于 2009-12-06T17:43:51.273 回答
1

您可以从字典中构建一个trie并遍历它。对于输入字符串中的每个字符，转到 trie 中的相应节点，从输入中删除该字符并递归重复。

伪代码：

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)

您可以使用查找表快速检查输入中剩余的某个字符的数量（恒定时间检查）。

于 2009-12-06T17:45:07.060 回答
1

我会通过首先将你所有的字典统一到一个巨大的字典中来解决这个问题，然后对你构建的字典中的字母和你正在搜索的名为 searchWord 的子集的单词进行排序。

我会做这样的事情

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
于 2009-12-06T18:11:55.253 回答
0

我感谢你们提供的所有帮助。我采取了一种更简单的方法，如下所示：它似乎非常有效，但我仍计划研究您提出的所有替代方案。

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;
 } 
}
于 2009-12-07T20:50:48.713 回答
0

Jon Bentley 的书Programming Pearls有一个很好的例子来说明字谜，我相信你可以适应它。请参阅第2 列的代码（或者更好地抓住这本书！）。

我将在这里勾勒出一个实现：

1）通过字典，为每个单词排序字母顺序（例如fish会变成“fihs”，“donkey”会变成“dekony”。这个键可以让你查找所有可以用这个组成的词一系列字母。将此信息存储在数据结构 Map<String,Set<String>> 中。例如，对于单词 dog，您最终会得到两个条目 dog -> (god,dog)。

3) 现在，当你想找一个词时，按照上面的描述对机架中的字母序列进行排序并查询地图（例如在你制作的地图中查找键）。这将为您提供由该系列字母组成的所有可能单词的列表。

您将对 Scrabble 进行一些调整，因为原始算法是针对字谜的，但它应该像多次查询地图一样简单（例如，如果您有字母 dayvgea，那么您不仅需要查询 aadgeyv , 但也适用于 6 个及以下字母的每个组合。7 个项目的不同组合的数量仅为 128，因此要找到最佳单词，您只需要在数据结构中进行固定数量的查找。

于 2009-12-06T18:24:44.000 回答
0

在 Python 中：

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

如果您想查看算法，只需查看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
于 2009-12-06T17:49:35.820 回答