拼字游戏字谜生成器

Question

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

到目前为止，我的代码可以工作，但速度非常慢，并且存在错误。其中之一是它会多次使用字母。例如：输入字母：“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  );

                          }




    }
}

字典文件只是按单词大小排序。

Answer 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)

您可以使用查找表来快速检查输入中还剩下多少特定字符（恒定时间检查）。

Answer 2

我会通过首先将所有词典统一到一个巨大的词典中来解决此问题，然后对您构建的词典中的字母以及您正在搜索的单词进行排序，以查找名为 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 

Answer 3

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

• 生成给定集合的所有可能的子集
  • 使用位字段计数器最容易完成
• 完成集合的排列
  • 伪代码说明和图表
  • .NET 字符串的更具体实现

我还应该注意到一个问题您当前的代码是所有内部循环都从 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;
    }
}

Answer 4

在Python中：

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

如果你想查看算法，只需查看source/文档：

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

Answer 5

Jon Bentley 的书 Programming Pearls 提供了一个很好的示例这是字谜词，我相信你可以适应它。请参阅第 2 列的代码（或更好地抓住这本书！）。

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

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

3) 现在，当您想要查找单词时，请按上述方式对机架中的字母序列进行排序，然后查询地图（例如，在您制作的地图中查找关键字）。这将为您提供由该系列字母组成的所有可能单词的列表。

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

Answer 6

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

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;
 } 
}