Оптимальный алгоритм для генерации всех комбинаций (порядок букв) слова

Question

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

Например:

Учитывая слово любви, следующий будет выводиться:

Сформированных слова: 24 Эл Elvo eolv eovl evlo эвол leov levo Лоев любовь lveo lvoe oelv oevl Olev Olve OvEL ovle Вело VEOL vleo vloe voel полевка

Учитывая слово колокол (обратите внимание, о повторяющихся l), выдается следующее:

Сформированные слова: 12 колокол blel blle ebll elbl ellb lbel lble Лебл lelb llbe lleb

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

Answer 1

После того, как долго! время, наконец, я получил ответ на свой вопрос. Я использовал PHP как свой язык программирования (потому что это мой выбор, а не что-то еще), и я использовал Pear Package: Math Combinatorics.

Answer 2

Можно создать перестановки (исключая дублирующее ограничение) для каждого символа, заменяя этот символ первым символом и рекурсивным путем исключения первого символа.

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

код Java: (полученный из a basic permutation generator)

import java.util.Arrays; 
import java.util.Scanner; 

public class NewMain 
{ 
    public static void main(String[] args) 
    { 
     Scanner sc = new Scanner(System.in); 
     System.out.println("Enter the string:"); 
     String s = sc.nextLine(); 
     char[] c = s.toCharArray(); 
     Arrays.sort(c); 

     System.out.println("Here are all the permutations:"); 
     NewMain.c = c; 
     count = 0; 
     permutation(0); 
     System.out.println("Number of permutations = " + count); 
    } 

    static char[] c; 
    static int count; 

    static void swap(int pos1, int pos2) 
    { 
     char temp = c[pos1]; 
     c[pos1] = c[pos2]; 
     c[pos2] = temp; 
    } 

    public static void permutation(int start) 
    { 
     if (start == c.length) 
     { 
     System.out.println(c); 
     count++; 
     } 

     for (int i = start; i < c.length; i++) 
     { 
     if (i == start || (c[i] != c[i-1] && c[i] != c[start])) 
     { 
      swap(start, i); 
      permutation(start + 1); 
      swap(start, i); 
     } 
     } 
    } 
} 

Test.

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

Answer 3

1. Возьмите общее количество букв в слове, n и найдите n !.
2. Подсчитайте количество вхождений каждой буквы. Для каждой буквы, повторяющейся более одного раза, разделите на (число повторений)!

Пример: 'банан'

2 п-х, 3 А-х, 6 всего письма

ответа = 6/(2 * 3!) = 60