Можно генерировать перестановки (исключая ограничение дублирования), для каждого символа заменяя этот символ первым символом и рекурсивно исключая первый символ.
Теперь, если мы хотим исключить дубликаты, нам просто нужно убедиться, что мы не помещаем один и тот же символ в первую позицию дважды. Это можно сделать, отсортировав символы (чтобы повторяющиеся символы находились рядом друг с другом) и пропустив любой символ, который совпадает с предыдущим или совпадает с символом в целевой позиции.
Код Java: (полученный из базового генератора перестановок)
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);
}
}
}
}
Тест.
Теперь это все еще не особенно эффективно, если есть слишком много повторяющихся символов. Один из способов, который я могу придумать, чтобы улучшить это, - это иметь счетчик для каждого символа (возможно, в форме связанного списка (связанный список счетчиков), чтобы мы могли быстро удалить счетчики, которые достигли 0, и вставить их обратно после этого) и, как и выше, мы генерируем символы слева направо, пропуская дубликаты, обрабатывая каждый счет только один раз на каждом рекурсивном шаге.
person
Bernhard Barker
schedule
17.07.2013
