Генератор анаграмм скрэббл

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

Я бы подошел к этому, сначала объединив все ваши словари в один гигантский словарь, а затем отсортировав буквы в создаваемом словаре и слово, которое вы ищете, для подмножеств с именем 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 2

Вы можете построить три из словаря и пройти его. Для каждого символа во входной строке перейдите к соответствующему узлу в дереве, удалите символ из ввода и повторите рекурсивно.

Псевдо-код:

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

Я ценю всю помощь, которую вы оказали. Я выбрал более простой подход, вот он: он кажется довольно эффективным, но я все же планирую изучить все предложенные вами альтернативы.

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

Answer 5

Книга Джона Бентли, Programming Pearls , имеет отличный пример того, как это делается для анаграмм, и я уверен, что вы могли бы адаптировать его. См. Код для столбца 2 (или даже лучше захватите книгу!).

Я нарисую здесь реализацию:

1) Пройдите по словарю, для каждого слова сортируйте буквы по порядку (например, рыба стала бы "fihs", "осел" стал бы "dekony". Этот ключ позволит вам найти все слова, которые могут быть сделано из этой серии букв. Сохраните эту информацию в структуре данных Map >. Например, для слова «собака» у вас будет две записи «собака» -> (бог, собака).

3) Теперь, когда вы хотите найти слово, отсортируйте последовательность букв в стойке, как описано выше, и запросите карту (например, найдите ключ на карте, которую вы создали). Это даст вам список всех возможных слов, составленных из этой серии букв.

Вам придется немного адаптировать это для Scrabble, потому что оригинальный алгоритм был для анаграмм, но это должно быть так же просто, как просто запрашивать карту больше раз (например, если у вас есть буквы dayvgea, то вам нужно будет запрашивать не только для aadgeyv, но также для каждой комбинации из 6 букв и ниже. Количество различных комбинаций из 7 элементов составляет всего 128, поэтому для поиска лучшего слова вам понадобится только фиксированное количество поисков в структура данных.

Answer 6

В 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