Re: [algogeeks] DISTINCT Permutations ( Not Easy)
Hi Nishanth Pandey,
I got it. If str[end] char is present in
any index between [start, end) we would have already generated
permutations with str[end] character in index start. So no need to
generate those permutations again.
Again, Thank you very much for your programn :).
-Thanks,
Bujji
On Thu, Jan 9, 2014 at 3:56 AM, bujji jajala jajalabu...@gmail.com wrote:
Hi Nishanth Pandey,
Excellent solution! It meets all
requirements in problem!
One thing I am finding hard to understand is your duplicate functions
logic.
code is simple. But reason behind it I am finding hard.
I would write it like
bool duplicate(char str[], int start, int end)
{ if(start == end)
return false;
// Without loop
if (str[start] == str[end]) /* I would end up generating same
permutations for example abcacd here swapping a and a would repeat
same permutations. unfortunately this logic is not working well */
return true;
return false;
}
Why are you skipping if you find element you want to swap in between
start and end indexes in duplicate function?
Please let me know you intuition.
-Thanks,
Bujji
On Tue, Jan 7, 2014 at 6:08 AM, Nishant Pandey
nishant.bits.me...@gmail.com wrote:
This will help u i guess :
#include iostream
#include string.h
using namespace std;
void swap(char str[],int m,int n ) {
char temp=str[m];
str[m]=str[n];
str[n]=temp;
}
bool duplicate(char str[], int start, int end)
{ if(start == end)
return false;
else
for(; startend; start++)
if (str[start] == str[end])
return true;
return false;
}
void Permute(char str[], int start, int end)
{
if(start = end){
coutstrendl;
return;
}
for(int i=start;i=end;i++)
{ if(!duplicate(str,start,i))
{
swap(str,start,i);
Permute(str,start+1,end);
swap(str,start,i);
}
}
}
int main()
{
char Str[]=aba;
Permute(Str,0,strlen(Str)-1);
return 0;
}
NIshant Pandey
Cell : 9911258345
Voice Mail : +91 124 451 2130
On Tue, Jan 7, 2014 at 4:44 PM, kumar raja rajkumar.cs...@gmail.comwrote:
This u can do it using the backtracking method. To know how to use
backtracking refer algorithm design manual by steve skiena.
On 7 January 2014 03:35, bujji jajala jajalabu...@gmail.com 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 algogeeks+unsubscr...@googlegroups.com.
--
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 algogeeks+unsubscr...@googlegroups.com.
--
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 algogeeks+unsubscr...@googlegroups.com.
--
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 algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] DISTINCT Permutations ( Not Easy)
Hi Nishanth Pandey,
Excellent solution! It meets all
requirements in problem!
One thing I am finding hard to understand is your duplicate functions logic.
code is simple. But reason behind it I am finding hard.
I would write it like
bool duplicate(char str[], int start, int end)
{ if(start == end)
return false;
// Without loop
if (str[start] == str[end]) /* I would end up generating same
permutations for example abcacd here swapping a and a would repeat
same permutations. unfortunately this logic is not working well */
return true;
return false;
}
Why are you skipping if you find element you want to swap in between start
and end indexes in duplicate function?
Please let me know you intuition.
-Thanks,
Bujji
On Tue, Jan 7, 2014 at 6:08 AM, Nishant Pandey nishant.bits.me...@gmail.com
wrote:
This will help u i guess :
#include iostream
#include string.h
using namespace std;
void swap(char str[],int m,int n ) {
char temp=str[m];
str[m]=str[n];
str[n]=temp;
}
bool duplicate(char str[], int start, int end)
{ if(start == end)
return false;
else
for(; startend; start++)
if (str[start] == str[end])
return true;
return false;
}
void Permute(char str[], int start, int end)
{
if(start = end){
coutstrendl;
return;
}
for(int i=start;i=end;i++)
{ if(!duplicate(str,start,i))
{
swap(str,start,i);
Permute(str,start+1,end);
swap(str,start,i);
}
}
}
int main()
{
char Str[]=aba;
Permute(Str,0,strlen(Str)-1);
return 0;
}
NIshant Pandey
Cell : 9911258345
Voice Mail : +91 124 451 2130
On Tue, Jan 7, 2014 at 4:44 PM, kumar raja rajkumar.cs...@gmail.comwrote:
This u can do it using the backtracking method. To know how to use
backtracking refer algorithm design manual by steve skiena.
On 7 January 2014 03:35, bujji jajala jajalabu...@gmail.com 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 algogeeks+unsubscr...@googlegroups.com.
--
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 algogeeks+unsubscr...@googlegroups.com.
--
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 algogeeks+unsubscr...@googlegroups.com.
--
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 algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] DISTINCT Permutations ( Not Easy)
This u can do it using the backtracking method. To know how to use backtracking refer algorithm design manual by steve skiena. On 7 January 2014 03:35, bujji jajala jajalabu...@gmail.com 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 algogeeks+unsubscr...@googlegroups.com. -- 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 algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] DISTINCT Permutations ( Not Easy)
This will help u i guess :
#include iostream
#include string.h
using namespace std;
void swap(char str[],int m,int n ) {
char temp=str[m];
str[m]=str[n];
str[n]=temp;
}
bool duplicate(char str[], int start, int end)
{ if(start == end)
return false;
else
for(; startend; start++)
if (str[start] == str[end])
return true;
return false;
}
void Permute(char str[], int start, int end)
{
if(start = end){
coutstrendl;
return;
}
for(int i=start;i=end;i++)
{ if(!duplicate(str,start,i))
{
swap(str,start,i);
Permute(str,start+1,end);
swap(str,start,i);
}
}
}
int main()
{
char Str[]=aba;
Permute(Str,0,strlen(Str)-1);
return 0;
}
NIshant Pandey
Cell : 9911258345
Voice Mail : +91 124 451 2130
On Tue, Jan 7, 2014 at 4:44 PM, kumar raja rajkumar.cs...@gmail.com wrote:
This u can do it using the backtracking method. To know how to use
backtracking refer algorithm design manual by steve skiena.
On 7 January 2014 03:35, bujji jajala jajalabu...@gmail.com 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 algogeeks+unsubscr...@googlegroups.com.
--
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 algogeeks+unsubscr...@googlegroups.com.
--
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 algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] DISTINCT Permutations ( Not Easy)
use C++, next_permutation, in algorithm
2014/1/7 Nishant Pandey nishant.bits.me...@gmail.com
This will help u i guess :
#include iostream
#include string.h
using namespace std;
void swap(char str[],int m,int n ) {
char temp=str[m];
str[m]=str[n];
str[n]=temp;
}
bool duplicate(char str[], int start, int end)
{ if(start == end)
return false;
else
for(; startend; start++)
if (str[start] == str[end])
return true;
return false;
}
void Permute(char str[], int start, int end)
{
if(start = end){
coutstrendl;
return;
}
for(int i=start;i=end;i++)
{ if(!duplicate(str,start,i))
{
swap(str,start,i);
Permute(str,start+1,end);
swap(str,start,i);
}
}
}
int main()
{
char Str[]=aba;
Permute(Str,0,strlen(Str)-1);
return 0;
}
NIshant Pandey
Cell : 9911258345
Voice Mail : +91 124 451 2130
On Tue, Jan 7, 2014 at 4:44 PM, kumar raja rajkumar.cs...@gmail.comwrote:
This u can do it using the backtracking method. To know how to use
backtracking refer algorithm design manual by steve skiena.
On 7 January 2014 03:35, bujji jajala jajalabu...@gmail.com 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 algogeeks+unsubscr...@googlegroups.com.
--
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 algogeeks+unsubscr...@googlegroups.com.
--
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 algogeeks+unsubscr...@googlegroups.com.
--
Victor Manuel Grijalva Altamirano
Universidad Tecnologica de La Mixteca
--
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 algogeeks+unsubscr...@googlegroups.com.
