One can generate permutations (excluding the duplicate constraint) by, for each character, swapping that character with the first character and recursing by excluding the first character.
Now if we want to exclude duplicates, we simply need to make sure we don't put the same character in the first position twice. Doing this can be done by sorting the characters (so the duplicate characters are next to one another) and skipping over any character that's the same as the one before it or the same as the character at the target position.
Java code: (derived from 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.
Now this is still not particularly efficient if there are too many duplicate characters. One way I can think of to improve on this is by having a count for each character (maybe in the form of a linked-list (a linked-list of counts) so we can quickly remove counts that have reached 0, and insert them back afterwards) and, similar to above, we generate characters from left to right, skipping over duplicates by only processing each count once at each recursive step.
