Sort the input string and remove duplicates, keeping a count of the number
of occurrences of each character.
They you can build the permutations easily.
For your example, you would start with
char *str = "aba";
int len = strlen(str);
Which would be converted to
char *str "ab";
int rep[N] = {2,1,0}; // The string contained 2 'a's and 1 'b'
char result[N];
Then call permute(str,rep,len)
void permute(char *str, int *rep, int len, int p=0)
{
if (p<len)
{
for(int i = 0; str[i]; ++i)
if (rep[i])
{
result[p] = str[i];
--rep[i];
permute(str, rep, len,p+1);
++rep[i];
}
}
else printf("%s\n", result);
}
On Monday, January 6, 2014 5:05:08 PM UTC-5, bujji wrote:
>
> generate all possible DISTINCT permutations of a given string with some
> possible repeated characters. Use as minimal memory as possible.
>
> if given string contains n characters in total with m < n distinct
> characters each occuring n_1, n_2, ....n_m times where n_1 + n_2 + ...+ n_m
> = n
>
> program should generate n! / ( n_1! * n_2! * ....* n_m! ) strings.
>
> Ex:
> aba is given string
>
> Output:
>
> aab
> aba
> baa
>
>
> -Thanks,
> Bujji
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
