[algogeeks] Re: All possible permutations of a given string
In the link you have specified they are talking about using the C++ STL . I would like to know how is that STL implemented -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: All possible permutations of a given string
What are the parameters it is taking i and j? What are those? We only have to permute(s)-where s is the string. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: All possible permutations of a given string
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 kartmu...@gmail.com 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: All possible permutations of a given string
@ravu
I have mentioned how next permutation works.. Also i have given an
example in another post. Please go thru the link..
On Dec 28, 10:47 pm, Gene gene.ress...@gmail.com wrote:
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 kartmu...@gmail.com 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: All possible permutations of a given string
Have a look at this algo :- Steinhaus–Johnson–Trotter algorithm . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: All possible permutations of a given string
This might help.. http://groups.google.com/group/algogeeks/browse_thread/thread/d3dafdcd53f101a9# On Dec 28, 11:53 am, SAMMM somnath.nit...@gmail.com wrote: Have a look at this algo :- Steinhaus–Johnson–Trotter algorithm . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: All possible permutations of a given string
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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
