CareerCup

here is the solution using backtracking
1: fix the 1st character and swap the others
and so on

/* Function to swap values at two pointers */
void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
            
                 if (a[i] == a[j] && i != j)// take care of duplicate characters
                continue;

          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
}

at least you can use the probability formula to know how many strings you should get. If number of letters are 'n', number of letters (in that string) of type 1 are 'x', number of letters (in that string) of type 2 are 'y' then the number of possible permutations are : n! / (x! * y!)

worst case you can do n! work and use a HashSet to screen out duplicates. The size of your HashSet should match the count you get from the formula.

I am thinking if there is a better way to do it.

at least you can use the probability formula to know how many strings you should get. If number of letters are 'n', number of letters (in that string) of type 1 are 'x', number of letters (in that string) of type 2 are 'y' then the number of possible permutations are : n! / (x! * y!)

worst case you can do n! work and use a HashSet to screen out duplicates. The size of your HashSet should match the count you get from the formula.

I am thinking if there is a better way to do it.

Here is something i did using sets: Not the most efficient in terms of space, but very easy to understand.

private void permute(char[] slots, ArrayList<Character> charSet, int k) {
if(charSet.size() == 0)
System.out.println(new String(slots));
else {
Set<Character> set = new HashSet<Character>(charSet);
for(Character c : set) {
slots[k] = c;
ArrayList<Character> newSet = new ArrayList<Character>(charSet);
newSet.remove(c);
permute(slots, newSet, k + 1);
}
}
}

void RecursivePermute(string sofar, string rest, map<string,string> hashmap)
{
	if( rest.empty() )
	{
		printf("%s\n", sofar.c_str());
		return;
	}
	string savenext;
	string saveleftover;
	for( int i= 0;i<=rest.length()-1;i++)
	{
		string next = sofar + rest[i];
		string leftover = rest.substr(0,i) + rest.substr(i+1);
		if( next == savenext && saveleftover == leftover)
			continue;
		RecursivePermute(next,leftover, hashmap);
		savenext = next;
		saveleftover = leftover; 
	}
}

How it works : We add one char at a time to sofar from rest. To avoid duplicate permutation we must first ensure that the string is sorted lexographically. When the sofar and rest computed is same as the ones that were computed previously then we do not make the recursive call since it will generate the same permutation.