Don't forget repeats. The string "aaa" has only one permutation.
A related interesting question is how to write a permutation
iterator. Here is the interface:
typedef struct {
// your code here
} PERMUTATION_ITERATOR;
/* Initialize the given permutation iterator with the string of n
characters
to be permuted. */
void init_permutation_iterator(PERMUTATION_ITERATOR *iterator, char
*str, int n)
{
// your code here
}
/* Get the next unique permutation of the initialization string into
the
given buffer. The first string returned is always the string
provided
to the initializer. Return true unless the permutation being
returned
is the last one. I.e. next time this function is called, it will
"wrap" back
to the initialization string. */
int get_next_permutation(PERMUTATION_ITERATOR *iterator, char *buf)
{
// your code here
}
Use like this:
{
PERMUTATION_ITERATOR iterator[1];
char s = "Cool or what?";
char buf[100];
init_permutation_iterator(iterator, s, strlen(s));
while (get_next_permutation(iterator, buf))
printf("%.*s\n", buf);
}
On Dec 28, 8:15 am, "Karthikeyan V.B" <[email protected]> wrote:
> Hi,
>
> Using Backtracking,
>
> 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++)
> {
> swap((a+i),(a+j));
> permute(a,i+1,n);
> swap((a+i),(a+j));
>
> }
> }
> }
>
> But this takes O(n*n!) time
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
