Как мне создать рекурсивный инструмент анаграммы, который печатает каждую возможную комбинацию строки букв, включая префиксы? - PullRequest
Новая
       6

Как мне создать рекурсивный инструмент анаграммы, который печатает каждую возможную комбинацию строки букв, включая префиксы?

0 голосов
/ 02 марта 2012

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

Например: восточная будет производить другие варианты, такие какСерьезно, но я также хотел бы, чтобы он производил такие вариации, как восток, есть и есть.

У меня уже есть рабочий словарь, проверяющий, есть ли комбинации в словаре. 

public void printAnagrams(String prefix, String word)
{
    if(word.length() == 1) {
        if (words.contains(prefix+word))
            System.out.println(prefix + word);
    }
    else    
    {
        for(int i = 0; i < word.length(); i++)
        {
            String current = word.substring(i, i + 1);
            String before = word.substring(0, i);
            String after = word.substring(i+1);
            printAnagrams(prefix + current, before + after);
        }
    }
}

1 Ответ

1 голос
/ 02 марта 2012

Имеет набор chars [может быть char[]] и «угадайте», которая является следующей буквой, и добавьте ее к промежуточному sol StringBuilder, который содержит текущую подстроку. Вызовите алгоритм рекурсивно, чтобы найти следующие символы решения.

Иметь индекс i, чтобы указать, какие символы можно использовать [все символы "вправо" до i].

На каждой итерации - выводить полученную строку, даже если вы не указали максимальную длину.

Псевдокод: 

findPermutations(chars,i,sol):
   print sol
   if (chars.length == i):
       return
   for each j in range(j,chars.length):
       sol.append(chars[i+1])
       swap(chars,i,j) //we cannot use chars[j] anymore.
       findPermutations(chars,j+1,sol)
       swap(chars,i,j) //clean up environment
       sol.removeLast()

Примечания:

  1. В этом решении предполагается, что chars является набором, поэтому, если определенный символ появляется более одного раза - у вас будут дубликаты, но он все равно будет работать [генерировать все возможности]
  2. Несколько слов о сложности: существует экспоненциальное количество возможностей, и вам нужны все из них. Итак, если вы попытаетесь вызвать этот метод [и фактически любой алгоритм для его выполнения] с более чем 20 символами, вы должны закончить генерировать все возможности через ~ 200 лет
...