[algogeeks] Re: Permutation Problem with repeating characters
Here is the algorithm for printing all permutations ignoring repeats:
char buf[MAX_LEN];
void swap(int i, int j)
{ char t = buf[i]; buf[i] = buf[j]; buf[j] = t; }
void recur(int start, int len)
{
if (len == 0) printf(%s, buf);
else {
for (int i = 0; i len; ++i) {
swap(start, i);
recur(start + 1, len - 1);
swap(start, i);
}
}
}
void permute(char *s)
{
strcpy(buf, s);
recur(0, strlen(buf));
}
Now the problem arises when swap(start, i); is exchanging two
different copies of the same character. So how can you modify this
algorithm to prevent that?
On Dec 7, 8:01 am, Aniket aniket...@gmail.com wrote:
Write a programme to produce all permutations of a given string where
characters are not unique. That means you are not allowed to print the
duplicate strings.
Ex:
If input is aaa
The output should be only aaa
--
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: Permutation Problem with repeating characters
http://groups.google.com/group/algogeeks/browse_thread/thread/d3dafdcd53f101a9#
On Dec 7, 8:07 pm, Gene gene.ress...@gmail.com wrote:
Here is the algorithm for printing all permutations ignoring repeats:
char buf[MAX_LEN];
void swap(int i, int j)
{ char t = buf[i]; buf[i] = buf[j]; buf[j] = t; }
void recur(int start, int len)
{
if (len == 0) printf(%s, buf);
else {
for (int i = 0; i len; ++i) {
swap(start, i);
recur(start + 1, len - 1);
swap(start, i);
}
}
}
void permute(char *s)
{
strcpy(buf, s);
recur(0, strlen(buf));
}
Now the problem arises when swap(start, i); is exchanging two
different copies of the same character. So how can you modify this
algorithm to prevent that?
On Dec 7, 8:01 am, Aniket aniket...@gmail.com wrote:
Write a programme to produce all permutations of a given string where
characters are not unique. That means you are not allowed to print the
duplicate strings.
Ex:
If input is aaa
The output should be only aaa
--
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: permutation of string with repeated characters...
i did a dry run on this code and didnt find the significance of mk array ... so i did remove it from the code .. and the code works fine .. i more thing ... the code repeats same palindromes as in incase of ABA baa is coming twice.. correct me if i am wrong ... On Fri, Jul 29, 2011 at 10:47 AM, Arun Vishwanathan aaron.nar...@gmail.comwrote: @amit:i am not clear about the code.Maybe could you take your example string aabc and explain a few steps that happen from your code??.The array mk is locally created for each function call and so I do not get how it keeps track of elements tried cos each time it is a new array. On Fri, Jul 29, 2011 at 3:54 AM, amit karmakar amit.codenam...@gmail.comwrote: What my recursive solution does is that, For all elements that can be used at position *k*, fix that element at position *k* and then permute the rest of the elements. So if are two same elements which can be used at position *k* we must choose only one of it to avoid repeated permutations. Array mk[256] keeps a track of the elements that have already been tried. Does there exist any better solution also, or this backtracking solution is the best? You should have a look at this: http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations On Jul 29, 12:34 am, Nitish Garg nitishgarg1...@gmail.com wrote: Can you please explain what is the use of the array mk[256], how this array solves the problem of repeated characters. Does there exist any better solution also, or this backtracking solution is the best? -- 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. -- 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. -- 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: permutation of string with repeated characters...
void printPerm(char *s,int i ,int len){
if( i == len){
printf(%s\n,s);
return ;
}
int j ;
char t ;
char h[26] ;
memset(h,'0',26);
for(j = i ; j len ; j++ ){
if(h[s[j]-'a'] == '0'){
h[s[j]-'a'] = '1' ;
t = s[i] ; s[i] = s[j] ; s[j] = t ;
printPerm(s,i+1,len);
t = s[i] ; s[i] = s[j] ; s[j] = t ;
}
}
}
On Fri, Jul 29, 2011 at 11:37 AM, snehi jain snehijai...@gmail.com wrote:
i did a dry run on this code and didnt find the significance of mk array
... so i did remove it from the code ..
and the code works fine ..
i more thing ... the code repeats same palindromes as in incase of ABA baa
is coming twice..
correct me if i am wrong ...
On Fri, Jul 29, 2011 at 10:47 AM, Arun Vishwanathan
aaron.nar...@gmail.com wrote:
@amit:i am not clear about the code.Maybe could you take your example
string aabc and explain a few steps that happen from your code??.The array
mk is locally created for each function call and so I do not get how it
keeps track of elements tried cos each time it is a new array.
On Fri, Jul 29, 2011 at 3:54 AM, amit karmakar amit.codenam...@gmail.com
wrote:
What my recursive solution does is that,
For all elements that can be used at position *k*, fix that element at
position *k* and then permute the rest of the elements.
So if are two same elements which can be used at position *k* we must
choose only one of it to avoid repeated permutations.
Array mk[256] keeps a track of the elements that have already been
tried.
Does there exist any better solution also, or this backtracking
solution is the best?
You should have a look at this:
http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
On Jul 29, 12:34 am, Nitish Garg nitishgarg1...@gmail.com wrote:
Can you please explain what is the use of the array mk[256], how this
array
solves the problem of repeated characters.
Does there exist any better solution also, or this backtracking
solution is
the best?
--
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.
--
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.
--
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.
--
*With Regards :*
Ravinder Kumar
B.Tech Final Year
Computer Science and Engineering
MNNIT Allahabad
--
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: permutation of string with repeated characters...
i more thing ... the code repeats same palindromes as in incase of ABA baa is coming twice.. Put back mk array in place and baa won't be repeated. The idea is that out of all available options for filling a particular position in our partial solution at each round of backtracking we choose for each group of repeated characters, only one of them. In this way, we get only distinct permutations as output. On Jul 29, 3:37 pm, snehi jain snehijai...@gmail.com wrote: i did a dry run on this code and didnt find the significance of mk array ... so i did remove it from the code .. and the code works fine .. i more thing ... the code repeats same palindromes as in incase of ABA baa is coming twice.. correct me if i am wrong ... On Fri, Jul 29, 2011 at 10:47 AM, Arun Vishwanathan aaron.nar...@gmail.comwrote: @amit:i am not clear about the code.Maybe could you take your example string aabc and explain a few steps that happen from your code??.The array mk is locally created for each function call and so I do not get how it keeps track of elements tried cos each time it is a new array. On Fri, Jul 29, 2011 at 3:54 AM, amit karmakar amit.codenam...@gmail.comwrote: What my recursive solution does is that, For all elements that can be used at position *k*, fix that element at position *k* and then permute the rest of the elements. So if are two same elements which can be used at position *k* we must choose only one of it to avoid repeated permutations. Array mk[256] keeps a track of the elements that have already been tried. Does there exist any better solution also, or this backtracking solution is the best? You should have a look at this: http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permu... On Jul 29, 12:34 am, Nitish Garg nitishgarg1...@gmail.com wrote: Can you please explain what is the use of the array mk[256], how this array solves the problem of repeated characters. Does there exist any better solution also, or this backtracking solution is the best? -- 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. -- 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. -- 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: permutation of string with repeated characters...
The seen array filters out the characters which are available for filling a particular position. The mk array makes sure that we choose only one of the repeated characters. for example, if the array is aba if mk array is there backtracking will try like String : a _ _ or b _ _ or a _ _ character position : 0 _ _ 1 _ _ 2 _ _ with mk array , String : a _ _ character position : 2 _ _ will not happen. I hope you can get my notations. On Jul 29, 10:17 am, Arun Vishwanathan aaron.nar...@gmail.com wrote: @amit:i am not clear about the code.Maybe could you take your example string aabc and explain a few steps that happen from your code??.The array mk is locally created for each function call and so I do not get how it keeps track of elements tried cos each time it is a new array. On Fri, Jul 29, 2011 at 3:54 AM, amit karmakar amit.codenam...@gmail.comwrote: What my recursive solution does is that, For all elements that can be used at position *k*, fix that element at position *k* and then permute the rest of the elements. So if are two same elements which can be used at position *k* we must choose only one of it to avoid repeated permutations. Array mk[256] keeps a track of the elements that have already been tried. Does there exist any better solution also, or this backtracking solution is the best? You should have a look at this: http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permu... On Jul 29, 12:34 am, Nitish Garg nitishgarg1...@gmail.com wrote: Can you please explain what is the use of the array mk[256], how this array solves the problem of repeated characters. Does there exist any better solution also, or this backtracking solution is the best? -- 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. -- 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: permutation of string with repeated characters...
there was an typo, if mk array is *not* there backtracking will try like On Jul 29, 7:13 pm, amit karmakar amit.codenam...@gmail.com wrote: The seen array filters out the characters which are available for filling a particular position. The mk array makes sure that we choose only one of the repeated characters. for example, if the array is aba if mk array is there backtracking will try like String : a _ _ or b _ _ or a _ _ character position : 0 _ _ 1 _ _ 2 _ _ with mk array , String : a _ _ character position : 2 _ _ will not happen. I hope you can get my notations. On Jul 29, 10:17 am, Arun Vishwanathan aaron.nar...@gmail.com wrote: @amit:i am not clear about the code.Maybe could you take your example string aabc and explain a few steps that happen from your code??.The array mk is locally created for each function call and so I do not get how it keeps track of elements tried cos each time it is a new array. On Fri, Jul 29, 2011 at 3:54 AM, amit karmakar amit.codenam...@gmail.comwrote: What my recursive solution does is that, For all elements that can be used at position *k*, fix that element at position *k* and then permute the rest of the elements. So if are two same elements which can be used at position *k* we must choose only one of it to avoid repeated permutations. Array mk[256] keeps a track of the elements that have already been tried. Does there exist any better solution also, or this backtracking solution is the best? You should have a look at this: http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permu... On Jul 29, 12:34 am, Nitish Garg nitishgarg1...@gmail.com wrote: Can you please explain what is the use of the array mk[256], how this array solves the problem of repeated characters. Does there exist any better solution also, or this backtracking solution is the best? -- 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. -- 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: permutation of string with repeated characters...
What my recursive solution does is that, For all elements that can be used at position *k*, fix that element at position *k* and then permute the rest of the elements. So if are two same elements which can be used at position *k* we must choose only one of it to avoid repeated permutations. Array mk[256] keeps a track of the elements that have already been tried. Does there exist any better solution also, or this backtracking solution is the best? You should have a look at this: http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations On Jul 29, 12:34 am, Nitish Garg nitishgarg1...@gmail.com wrote: Can you please explain what is the use of the array mk[256], how this array solves the problem of repeated characters. Does there exist any better solution also, or this backtracking solution is the best? -- 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: permutation of string with repeated characters...
@amit:i am not clear about the code.Maybe could you take your example string aabc and explain a few steps that happen from your code??.The array mk is locally created for each function call and so I do not get how it keeps track of elements tried cos each time it is a new array. On Fri, Jul 29, 2011 at 3:54 AM, amit karmakar amit.codenam...@gmail.comwrote: What my recursive solution does is that, For all elements that can be used at position *k*, fix that element at position *k* and then permute the rest of the elements. So if are two same elements which can be used at position *k* we must choose only one of it to avoid repeated permutations. Array mk[256] keeps a track of the elements that have already been tried. Does there exist any better solution also, or this backtracking solution is the best? You should have a look at this: http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations On Jul 29, 12:34 am, Nitish Garg nitishgarg1...@gmail.com wrote: Can you please explain what is the use of the array mk[256], how this array solves the problem of repeated characters. Does there exist any better solution also, or this backtracking solution is the best? -- 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. -- 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: Permutation of a string
@baghel: The method returns the desire output.
But looking for some algo which can do the same.
*Subhransu Panigrahi
*
*Mobile:* *+91-9840931538*
*Email:* subhransu.panigr...@gmail.com
On Tue, Apr 12, 2011 at 12:08 AM, baghel anant.bag...@gmail.com wrote:
This solution is incorrect.you are only considering ordered
permutations of all the rotations of the list ignoring random
permutations.
for eg in abcd you are missing random permutation like acbd.
here we need implementation of next_permutation() function of c++.
this http://wordaligned.org/articles/next-permutation might be
helpful.
Happy coding
On Apr 9, 12:13 am, Manish Pathak pathak@gmail.com wrote:
#include stdio.h
#include string.h
#include stdlib.h
int fact(int n);
void main()
{
char a[20],st_char;
static int i,j,k,n,ctr,main_ctr;
printf(Enter the string : );
//gets(a);
scanf(%s,a);
n=strlen(a);
if(n=1)
{
printf(please enter a valid string );
exit(0);
}
//label :
while(main_ctrn) //loop till length
{
for(i=0;i=n-2;++i)//loop to print first character of string ex
abc,acb
{
ctr=0;
printf(\n);
printf(%c,a[0]);
for(j=i+1;j=n-1;j++)//take
{
printf(%c,a[j]);
ctr++;
}
if(ctr!=n-1)
{
for(k=1;k=i;k++)// print characters that left in above loop ex
from above i=2 print a[0], then j=3 print a[3], means to print a[1] and
a[2]
{
printf(%c,a[k]);
ctr++;
}
}
}
st_char=a[0];//ex for abc string this change as a[0]=b;
for(i=0;i=n-2;i++)//a[1]=c;
a[i]=a[i+1];//a[2]=a;
a[n-1]=st_char;
main_ctr++;}
printf(\nDesigned by Manish Pathak );
}
--
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.
--
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: Permutation of a string
I don't there is any algorithm for this..
The recursive seems to the best approach for this.
does anyone know if there is any better approach available?
On Apr 12, 4:45 pm, Subhransu subhransu.panigr...@gmail.com wrote:
@baghel: The method returns the desire output.
But looking for some algo which can do the same.
*Subhransu Panigrahi
*
*Mobile:* *+91-9840931538*
*Email:* subhransu.panigr...@gmail.com
On Tue, Apr 12, 2011 at 12:08 AM, baghel anant.bag...@gmail.com wrote:
This solution is incorrect.you are only considering ordered
permutations of all the rotations of the list ignoring random
permutations.
for eg in abcd you are missing random permutation like acbd.
here we need implementation of next_permutation() function of c++.
this http://wordaligned.org/articles/next-permutation might be
helpful.
Happy coding
On Apr 9, 12:13 am, Manish Pathak pathak@gmail.com wrote:
#include stdio.h
#include string.h
#include stdlib.h
int fact(int n);
void main()
{
char a[20],st_char;
static int i,j,k,n,ctr,main_ctr;
printf(Enter the string : );
//gets(a);
scanf(%s,a);
n=strlen(a);
if(n=1)
{
printf(please enter a valid string );
exit(0);
}
//label :
while(main_ctrn) //loop till length
{
for(i=0;i=n-2;++i) //loop to print first character of string ex
abc,acb
{
ctr=0;
printf(\n);
printf(%c,a[0]);
for(j=i+1;j=n-1;j++) //take
{
printf(%c,a[j]);
ctr++;
}
if(ctr!=n-1)
{
for(k=1;k=i;k++)// print characters that left in above loop ex
from above i=2 print a[0], then j=3 print a[3], means to print a[1] and
a[2]
{
printf(%c,a[k]);
ctr++;
}
}
}
st_char=a[0]; //ex for abc string this change as a[0]=b;
for(i=0;i=n-2;i++) //a[1]=c;
a[i]=a[i+1]; //a[2]=a;
a[n-1]=st_char;
main_ctr++;}
printf(\nDesigned by Manish Pathak );
}
--
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.- Hide quoted text -
- Show quoted text -
--
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: Permutation of a string
@subhransu u sure that this code will return the desired output? chk
again dude. he is just considering ordered permutation not the random
permutation.
@sravanreddy yeah i tried for looking implementation of
next_permutation but seems like recursive approach is the best one as
far as producing code in front of interviewer is concern :P
On Apr 12, 5:20 pm, sravanreddy001 sravanreddy...@gmail.com wrote:
I don't there is any algorithm for this..
The recursive seems to the best approach for this.
does anyone know if there is any better approach available?
On Apr 12, 4:45 pm, Subhransu subhransu.panigr...@gmail.com wrote:
@baghel: The method returns the desire output.
But looking for some algo which can do the same.
*Subhransu Panigrahi
*
*Mobile:* *+91-9840931538*
*Email:* subhransu.panigr...@gmail.com
On Tue, Apr 12, 2011 at 12:08 AM, baghel anant.bag...@gmail.com wrote:
This solution is incorrect.you are only considering ordered
permutations of all the rotations of the list ignoring random
permutations.
for eg in abcd you are missing random permutation like acbd.
here we need implementation of next_permutation() function of c++.
this http://wordaligned.org/articles/next-permutation might be
helpful.
Happy coding
On Apr 9, 12:13 am, Manish Pathak pathak@gmail.com wrote:
#include stdio.h
#include string.h
#include stdlib.h
int fact(int n);
void main()
{
char a[20],st_char;
static int i,j,k,n,ctr,main_ctr;
printf(Enter the string : );
//gets(a);
scanf(%s,a);
n=strlen(a);
if(n=1)
{
printf(please enter a valid string );
exit(0);
}
//label :
while(main_ctrn) //loop till length
{
for(i=0;i=n-2;++i) //loop to print first character of string ex
abc,acb
{
ctr=0;
printf(\n);
printf(%c,a[0]);
for(j=i+1;j=n-1;j++) //take
{
printf(%c,a[j]);
ctr++;
}
if(ctr!=n-1)
{
for(k=1;k=i;k++)// print characters that left in above loop ex
from above i=2 print a[0], then j=3 print a[3], means to print a[1] and
a[2]
{
printf(%c,a[k]);
ctr++;
}
}
}
st_char=a[0]; //ex for abc string this change as a[0]=b;
for(i=0;i=n-2;i++) //a[1]=c;
a[i]=a[i+1]; //a[2]=a;
a[n-1]=st_char;
main_ctr++;}
printf(\nDesigned by Manish Pathak );
}
--
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.-Hide quoted text -
- Show quoted text -
--
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: Permutation of a string
int main(int argc, char* argv[])
{
char string[13];
char tmp[13];
int len, i, j, k, n;
printf(Length of string: );
fgets(string, 13, stdin);
sscanf(string, %d, len);
if (len 12) len = 12;
printf(Enter string: );
fgets(string, len+1, stdin);
string[len] = 0;
n = 1;
for(i = 0; i len; ++i)
n *= i+1;
printf(There are %d permutations\n, n);
for(i = 0; i n; ++i)
{
for(j = 0; j = len; ++j)
tmp[j] = string[j];
k = i;
for(j = 0; j len; ++j)
{
int indx = j + (k % (len-j));
char t=tmp[indx];
tmp[indx] = tmp[j];
tmp[j] = t;
}
printf(%s\n, tmp);
}
return 0;
}
On Apr 8, 1:34 pm, Subhransu subhransu.panigr...@gmail.com wrote:
What could be the efficient algo for finding permutation of string.
Lets say a user enter a string abc.
The output should be 6(3*2*1) along with he combination of them like
abc
bca
cab
bac
acb
cba
*Subhransu Panigrahi
*
*Mobile:* *+91-9840931538*
*Email:* subhransu.panigr...@gmail.com
--
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: Permutation of a string
int main(int argc, char* argv[])
{
char string[13];
char tmp[13];
int len, i, j, k, n=1;
printf(Length of string: );
fgets(string, 13, stdin);
sscanf(string, %d, len);
if (len 12) len = 12;
printf(Enter string: );
fgets(string, len+1, stdin);
string[len] = tmp[len] = 0;
for(i = 2; i = len; ++i)
n *= i;
printf(There are %d permutations\n, n);
for(i = 0; i n; ++i)
{
k = i;
tmp[0] = string[0];
for(j = 1; j len; ++j)
{
int indx = k % (j+1);
k /= (j+1);
tmp[j] = tmp[indx];
tmp[indx] = string[j];
}
printf(%s\n, tmp);
}
return 0;
}
On Apr 8, 1:34 pm, Subhransu subhransu.panigr...@gmail.com wrote:
What could be the efficient algo for finding permutation of string.
Lets say a user enter a string abc.
The output should be 6(3*2*1) along with he combination of them like
abc
bca
cab
bac
acb
cba
*Subhransu Panigrahi
*
*Mobile:* *+91-9840931538*
*Email:* subhransu.panigr...@gmail.com
--
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: Permutation of a string
This solution is incorrect.you are only considering ordered
permutations of all the rotations of the list ignoring random
permutations.
for eg in abcd you are missing random permutation like acbd.
here we need implementation of next_permutation() function of c++.
this http://wordaligned.org/articles/next-permutation might be
helpful.
Happy coding
On Apr 9, 12:13 am, Manish Pathak pathak@gmail.com wrote:
#include stdio.h
#include string.h
#include stdlib.h
int fact(int n);
void main()
{
char a[20],st_char;
static int i,j,k,n,ctr,main_ctr;
printf(Enter the string : );
//gets(a);
scanf(%s,a);
n=strlen(a);
if(n=1)
{
printf(please enter a valid string );
exit(0);
}
//label :
while(main_ctrn) //loop till length
{
for(i=0;i=n-2;++i) //loop to print first character of string ex abc,acb
{
ctr=0;
printf(\n);
printf(%c,a[0]);
for(j=i+1;j=n-1;j++) //take
{
printf(%c,a[j]);
ctr++;
}
if(ctr!=n-1)
{
for(k=1;k=i;k++)// print characters that left in above loop ex
from above i=2 print a[0], then j=3 print a[3], means to print a[1] and a[2]
{
printf(%c,a[k]);
ctr++;
}
}
}
st_char=a[0]; //ex for abc string this change as a[0]=b;
for(i=0;i=n-2;i++) //a[1]=c;
a[i]=a[i+1]; //a[2]=a;
a[n-1]=st_char;
main_ctr++;}
printf(\nDesigned by Manish Pathak );
}
--
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: Permutation.................
A nice explaination at
http://www.rawkam.com/?p=351
On Tue, Aug 24, 2010 at 6:49 PM, Chandan Balu chandann...@gmail.com wrote:
Can somebody please tell me, how does the above code for permutation
works(Algorithms behind) please?
On Mon, Aug 2, 2010 at 4:31 AM, bujji jajalabu...@gmail.com wrote:
Here is simple code to generate permutations
#include stdafx.h
#includestdio.h
int Permute( char *, int);
int PrintArray();
int swap(char *, int);
char A[]={'1','2','3','4','5','6','7','8'};
main( )
{
Permute(A,sizeof(A)/sizeof(char));
return 0;
}
int Permute(char * a, int n)
{ if(n==1)
{ PrintArray();
return 0;
}
int i=0;
for(i=0; in;i++)
{
swap(a,i);
Permute(a+1,n-1);
swap(a,i);
}
}
int PrintArray()
{
int i=0;
static int Number_of_Solutions=0;
printf(\n Conf: %-4d ,++Number_of_Solutions);
for(i=0;isizeof(A);i++)
printf(%c ,A[i]);
return 0;
}
int swap( char *a, int i)
{
if(i0)
return -1;
int temp=*a;
*a=a[i];
a[i]=temp;
return 0;
}
Regards,
Bujji
On Aug 1, 4:00 pm, UMESH KUMAR kumar.umesh...@gmail.com wrote:
Write a C code for generate all possible Permutation
as:- 1 2 3
Total no. of Per=6
also print all permutation
as:- 1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
if inpute is 1 2 3 2
total no of permutation = 12
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: Permutation of Array.
@aravind prasad cool man check this case consider the case 12 122 so if u arrange sub string(i.e; 12) as the first one so u have the best value 12 122 ok its good now suppose the case is 21 211 so according to the above way the solution is 21 211 which is not best so you have to add some more things good luck... from: srinivasa reddy eevuri M.C.A NIT DURGAPUR On Sun, Aug 22, 2010 at 11:08 AM, aravind prasad raja@gmail.com wrote: @srinivas reddy i suppose u took my algo wrongly.. consider ur eg: 2,242 first digits== 2,2(same) 2nd digits== 2,4(here 2 remains as it is as there is no futher digit for no 2) now arrange== 2242(output)... my algo works correctly here too.. correct me if am wrong.. On Sun, Aug 22, 2010 at 10:41 AM, srinivas reddy srinivaseev...@gmail.com wrote: @aravind prasad ho can u arrange the numbers 2,202 suppose if u arrange 202 2 ok u wiil get the least value now 2,242 if u arrange in same manner as above u will get 242 2 which is not smallest one... so better luck next time. On Sun, Aug 22, 2010 at 8:41 AM, Aravind Prasad raja@gmail.com wrote: for the method of comparison in insertion sort,, consider 1)compare the first digit of all nos and sort them 2)if they are same, go for next digit... correct me if am wrong... On Aug 21, 7:00 pm, Chonku cho...@gmail.com wrote: Treat each number as string and make a trie out of it. For the first input [55,31,312,33], it would look like the following . /\ 3/ 5\ 1/ 3\5\ 31/ 2\ 33\ \55 312\ Once we have a trie, just print it out by based on the smallest number first. In this case, the print would go as follows. 313123355 On Sat, Aug 21, 2010 at 12:53 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: Suppose the test is like: 21 71 217 after sorting and msb appending we get: 217 712 217 sort: 217 217 712 here we have 2 same elements 217 and 217 so we remove the 7 from the following logic: 1.if msb lsb we delete from the 2nd 217.else 2.we delete 7 from 1st one. so this gives 2121771 if it wud have been 41 200 412-412 200 412-200 412 412 here we will remove 2 from last one.giving 20041241 instead of 20041412 . On Sat, Aug 21, 2010 at 12:26 PM, BALARUKESH SIVARAMAN sbalarukesh1...@gmail.com wrote: @Nikhil I am clear with your first 2 algos but not with the change u introduced ie., adding a check. please give a working example -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- thanks and regards aravind prasad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com.
Re: [algogeeks] Re: Permutation of Array.
I've forgotten a case for the numbers like 632, 635. In this case while
inserting, if the remainders are same 6 in this example, check the mod
values for the equal length numbers. But for unequal lengths like, 12 and
126 compare the last digit of one number with the first digit of second i.e
6 1 hence 12 should appear first.
On Sun, Aug 22, 2010 at 12:39 PM, Raj N rajn...@gmail.com wrote:
Take the input from the user of the min length number he would input i.e
min_length. Then accept the the numbers in the form of strings and calculate
the length of every number. Construct a binary search tree with fields as
follows:
struct node
{
int number;// atoi(input)
int remainder; // number/pow(10,string_length-min_length) if
string_length min_length
else remainder = number
struct node *left;
struct node *right;
};
My idea is reduce all the numbers to the smallest digit number and then
sort the remainders and output the respective numbers.
Construct binary tree based on the remainder and perform the inorder
traversal i.e
while ( p!=NULL)
{
inorder(p-left);
printf(%d,p-number);
inorder(p-right);
}
For eg: 635, 12, 9, 76, 4
Every number is reduced to one digit
635= number=635 remainder=635/100=6
12= number=12 remainder=12/10=1
9=number=9 remainder=9
76=number=76 remainder=76/10=7
4= number=4 remainder=4
Inorder traversal based on remainder 1-4-6-7-9
But we output the numbers instead of remainders i.e
12-4-635-76-9
Correct me if I'm wrong !!
On Sun, Aug 22, 2010 at 11:08 AM, aravind prasad raja@gmail.comwrote:
@srinivas reddy
i suppose u took my algo wrongly..
consider ur eg: 2,242
first digits== 2,2(same)
2nd digits== 2,4(here 2 remains as it is as there is no futher digit for
no 2)
now arrange== 2242(output)...
my algo works correctly here too..
correct me if am wrong..
On Sun, Aug 22, 2010 at 10:41 AM, srinivas reddy
srinivaseev...@gmail.com wrote:
@aravind prasad
ho can u arrange the numbers
2,202
suppose if u arrange 202 2
ok u wiil get the least value
now 2,242
if u arrange in same manner as above u will get 242 2
which is not smallest one...
so better luck next time.
On Sun, Aug 22, 2010 at 8:41 AM, Aravind Prasad raja@gmail.com
wrote:
for the method of comparison in insertion sort,, consider
1)compare the first digit of all nos and sort them
2)if they are same, go for next digit...
correct me if am wrong...
On Aug 21, 7:00 pm, Chonku cho...@gmail.com wrote:
Treat each number as string and make a trie out of it. For the first
input
[55,31,312,33], it would look like the following
.
/\
3/ 5\
1/ 3\5\
31/ 2\ 33\ \55
312\
Once we have a trie, just print it out by based on the smallest
number
first. In this case, the print would go as follows.
313123355
On Sat, Aug 21, 2010 at 12:53 PM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
Suppose the test is like:
21 71 217
after sorting and msb appending we get: 217 712 217
sort: 217 217 712
here we have 2 same elements 217 and 217 so we remove the 7 from
the
following logic:
1.if msb lsb we delete from the 2nd 217.else
2.we delete 7 from 1st one.
so this gives 2121771
if it wud have been 41 200 412-412 200 412-200 412 412
here we will remove 2 from last one.giving 20041241 instead of
20041412 .
On Sat, Aug 21, 2010 at 12:26 PM, BALARUKESH SIVARAMAN
sbalarukesh1...@gmail.com wrote:
@Nikhil
I am clear with your first 2 algos but not with the change u
introduced
ie., adding a check. please give a working example
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
Re: [algogeeks] Re: Permutation of Array.
Take the input from the user of the min length number he would input i.e
min_length. Then accept the the numbers in the form of strings and calculate
the length of every number. Construct a binary search tree with fields as
follows:
struct node
{
int number;// atoi(input)
int remainder; // number/pow(10,string_length-min_length) if
string_length min_length
else remainder = number
struct node *left;
struct node *right;
};
My idea is reduce all the numbers to the smallest digit number and then sort
the remainders and output the respective numbers.
Construct binary tree based on the remainder and perform the inorder
traversal i.e
while ( p!=NULL)
{
inorder(p-left);
printf(%d,p-number);
inorder(p-right);
}
For eg: 635, 12, 9, 76, 4
Every number is reduced to one digit
635= number=635 remainder=635/100=6
12= number=12 remainder=12/10=1
9=number=9 remainder=9
76=number=76 remainder=76/10=7
4= number=4 remainder=4
Inorder traversal based on remainder 1-4-6-7-9
But we output the numbers instead of remainders i.e
12-4-635-76-9
Correct me if I'm wrong !!
On Sun, Aug 22, 2010 at 11:08 AM, aravind prasad raja@gmail.com wrote:
@srinivas reddy
i suppose u took my algo wrongly..
consider ur eg: 2,242
first digits== 2,2(same)
2nd digits== 2,4(here 2 remains as it is as there is no futher digit for no
2)
now arrange== 2242(output)...
my algo works correctly here too..
correct me if am wrong..
On Sun, Aug 22, 2010 at 10:41 AM, srinivas reddy
srinivaseev...@gmail.com wrote:
@aravind prasad
ho can u arrange the numbers
2,202
suppose if u arrange 202 2
ok u wiil get the least value
now 2,242
if u arrange in same manner as above u will get 242 2
which is not smallest one...
so better luck next time.
On Sun, Aug 22, 2010 at 8:41 AM, Aravind Prasad raja@gmail.com
wrote:
for the method of comparison in insertion sort,, consider
1)compare the first digit of all nos and sort them
2)if they are same, go for next digit...
correct me if am wrong...
On Aug 21, 7:00 pm, Chonku cho...@gmail.com wrote:
Treat each number as string and make a trie out of it. For the first
input
[55,31,312,33], it would look like the following
.
/\
3/ 5\
1/ 3\5\
31/ 2\ 33\ \55
312\
Once we have a trie, just print it out by based on the smallest number
first. In this case, the print would go as follows.
313123355
On Sat, Aug 21, 2010 at 12:53 PM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
Suppose the test is like:
21 71 217
after sorting and msb appending we get: 217 712 217
sort: 217 217 712
here we have 2 same elements 217 and 217 so we remove the 7 from the
following logic:
1.if msb lsb we delete from the 2nd 217.else
2.we delete 7 from 1st one.
so this gives 2121771
if it wud have been 41 200 412-412 200 412-200 412 412
here we will remove 2 from last one.giving 20041241 instead of
20041412 .
On Sat, Aug 21, 2010 at 12:26 PM, BALARUKESH SIVARAMAN
sbalarukesh1...@gmail.com wrote:
@Nikhil
I am clear with your first 2 algos but not with the change u
introduced
ie., adding a check. please give a working example
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
[algogeeks] Re: Permutation of Array.
for the method of comparison in insertion sort,, consider 1)compare the first digit of all nos and sort them 2)if they are same, go for next digit... correct me if am wrong... On Aug 21, 7:00 pm, Chonku cho...@gmail.com wrote: Treat each number as string and make a trie out of it. For the first input [55,31,312,33], it would look like the following . / \ 3/ 5\ 1/ 3\ 5\ 31/ 2\ 33\ \55 312\ Once we have a trie, just print it out by based on the smallest number first. In this case, the print would go as follows. 313123355 On Sat, Aug 21, 2010 at 12:53 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: Suppose the test is like: 21 71 217 after sorting and msb appending we get: 217 712 217 sort: 217 217 712 here we have 2 same elements 217 and 217 so we remove the 7 from the following logic: 1.if msb lsb we delete from the 2nd 217.else 2.we delete 7 from 1st one. so this gives 2121771 if it wud have been 41 200 412-412 200 412-200 412 412 here we will remove 2 from last one.giving 20041241 instead of 20041412 . On Sat, Aug 21, 2010 at 12:26 PM, BALARUKESH SIVARAMAN sbalarukesh1...@gmail.com wrote: @Nikhil I am clear with your first 2 algos but not with the change u introduced ie., adding a check. please give a working example -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: Permutation of Array.
@srinivas reddy i suppose u took my algo wrongly.. consider ur eg: 2,242 first digits== 2,2(same) 2nd digits== 2,4(here 2 remains as it is as there is no futher digit for no 2) now arrange== 2242(output)... my algo works correctly here too.. correct me if am wrong.. On Sun, Aug 22, 2010 at 10:41 AM, srinivas reddy srinivaseev...@gmail.com wrote: @aravind prasad ho can u arrange the numbers 2,202 suppose if u arrange 202 2 ok u wiil get the least value now 2,242 if u arrange in same manner as above u will get 242 2 which is not smallest one... so better luck next time. On Sun, Aug 22, 2010 at 8:41 AM, Aravind Prasad raja@gmail.com wrote: for the method of comparison in insertion sort,, consider 1)compare the first digit of all nos and sort them 2)if they are same, go for next digit... correct me if am wrong... On Aug 21, 7:00 pm, Chonku cho...@gmail.com wrote: Treat each number as string and make a trie out of it. For the first input [55,31,312,33], it would look like the following . / \ 3/ 5\ 1/ 3\ 5\ 31/ 2\ 33\ \55 312\ Once we have a trie, just print it out by based on the smallest number first. In this case, the print would go as follows. 313123355 On Sat, Aug 21, 2010 at 12:53 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: Suppose the test is like: 21 71 217 after sorting and msb appending we get: 217 712 217 sort: 217 217 712 here we have 2 same elements 217 and 217 so we remove the 7 from the following logic: 1.if msb lsb we delete from the 2nd 217.else 2.we delete 7 from 1st one. so this gives 2121771 if it wud have been 41 200 412-412 200 412-200 412 412 here we will remove 2 from last one.giving 20041241 instead of 20041412 . On Sat, Aug 21, 2010 at 12:26 PM, BALARUKESH SIVARAMAN sbalarukesh1...@gmail.com wrote: @Nikhil I am clear with your first 2 algos but not with the change u introduced ie., adding a check. please give a working example -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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. -- thanks and regards aravind prasad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: Permutation.................
Here is simple code to generate permutations
#include stdafx.h
#includestdio.h
int Permute( char *, int);
int PrintArray();
int swap(char *, int);
char A[]={'1','2','3','4','5','6','7','8'};
main( )
{
Permute(A,sizeof(A)/sizeof(char));
return 0;
}
int Permute(char * a, int n)
{ if(n==1)
{ PrintArray();
return 0;
}
int i=0;
for(i=0; in;i++)
{
swap(a,i);
Permute(a+1,n-1);
swap(a,i);
}
}
int PrintArray()
{
int i=0;
static int Number_of_Solutions=0;
printf(\n Conf: %-4d ,++Number_of_Solutions);
for(i=0;isizeof(A);i++)
printf(%c ,A[i]);
return 0;
}
int swap( char *a, int i)
{
if(i0)
return -1;
int temp=*a;
*a=a[i];
a[i]=temp;
return 0;
}
Regards,
Bujji
On Aug 1, 4:00 pm, UMESH KUMAR kumar.umesh...@gmail.com wrote:
Write a C code for generate all possible Permutation
as:- 1 2 3
Total no. of Per=6
also print all permutation
as:- 1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
if inpute is 1 2 3 2
total no of permutation = 12
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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: Permutation with a twist ??
On Feb 3, 4:41 am, Vijendra Singh [EMAIL PROTECTED] wrote: Isn't this a normal power set generation problem. What we are trying to do here is, get all possible subsets. you can look for it on Google/Live -Vijju Sorry I can't find the discussion you're talking about. What you said above makes no sense to me. The power set _is_ the set of all possible subsets. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Permutation with a twist ??
permutation (List resultSoFar, List remainingElements)
{
if(length(remainingElements)=0)
return;
for i = 1 to length(remainingElements)
{
print resultSoFar+remainingElements[i];
permutation (resultSoFar+remainingElements[i],
remainingElements-remainingElements[i]);
}
}
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Permutation with a twist ??
On 2/3/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
I will like to generate following (not sure if this will be called
permutation):
NULL
C
B
A
B C
A C
A B
A B C
I think you're looking to generate all possible combinations of n elements.
Essentially below I'm trying to simulate binary,
Combination(Array Elements, Array Answer)
{
if(Elements.size() == 0) print Answer, return;
for(i in Elements)
//Select the particular element -- equiv to 1 say
Combinations(Elements+1, Answer.push_back(Elements[0])
//Don't select the element -- equiv to 0 say
Combinations(Elements+1, Answer)
}
--
Regards,
Rajiv Mathews
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Permutation with a twist ??
yes..i agree with rajiv..you seem to be generating combinations rather than permutations..the algo that i have given generates permutations --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Permutation with a twist ??
I'm sorry. My algo is terribly wrong!
On 2/3/07, Rajiv Mathews [EMAIL PROTECTED] wrote:
Combination(Array Elements, Array Answer)
{
if(Elements.size() == 0) print Answer, return;
for(i in Elements)
//Select the particular element -- equiv to 1 say
Combinations(Elements+1, Answer.push_back(Elements[0])
//Don't select the element -- equiv to 0 say
Combinations(Elements+1, Answer)
}
It should be,
Combinations(Array Elements, Array Answer, int size)
{
if(size == 0) print(Answer);
//Select element
Answer.push_back(Elements[0]);
Combinations(Elements+1, Answer, size-1);
Answer.pop_back();
//Don't select element
Combinations(Elements+1, Answer, size-1);
}
Sorry for the last post. I shouldn't be typing while sleeping :-)
--
Regards,
Rajiv Mathews
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Permutation with a twist ??
On Feb 2, 5:02 pm, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
Hey,
I am looking for an algorithm to do as follows:
my @array = qw (A B C); # This array may have several parameters,
for
ex. A B C D
I will like to generate following (not sure if this will be called
permutation):
NULL
C
B
A
B C
A C
A B
A B C
Available permutation algorithms generate a different output, for
example:
b c a
c b a
c a b
a c b
b a c
a b c
Any suggestions! Thanks in advance.
This is called the power set. You can easily generate the power set
by identifying each of the original elements with a digit in a binary
number and then counting. The 1's in the successive counts tell you
whether to include the element in the current output or not.
Identify binary digits cba with C B A:
000 = {}
001 = A
010 = B
011 = BA
100 = C
101 = CA
110 = CB
111 = CBA
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Permutation Alogrithm very slow
Why do you need to do all the permutation? if you have 7 users, you need only 7 permutations, not 2**100. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Permutation Alogrithm very slow
You've hit the problem right on the head, kensuke. I believe he wants to give each viewer not just a random display from the database, but a display that won't be repeated, as well. Checking the random numbers off against a boolean array, would give him what he wants, (together with your suggestion, I believe. So if he's already shown the pic associated with #2 in the database, that pic will never be shown in the future random pics, to that viewer, on that visit to the website. Somewhat of a guess, given the scant info, but I believe that's what he wants. Adak --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Permutation Alogrithm very slow
alpaul wrote: Now make the issue a bit simple, I jsut it is only 3 datas, which is A, B, C, According to the permutation rule, 2**3=6 AB-AC-BA-BC-CA-CB It's hard to figure out what you are saying 2**3 is 8, not 6. I think you mean 2!=6. But it is enough for me to display on the web and retrieve it from the database, becasue it isn't much data, If I have 100 data, then it will be 2**100=XXX And it is very slow, Again it's hard to see what you mean. Do you mean you want to pick 5 out of the 100 at random?Try to make your question clearer and someone might be able to answer it. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: permutation (bottom up minimal change) ,(johnson trotter) ,(lexicographic)
Hi prince444, The right algo to use, depends on tests you make with your own representative data set. Trying to follow hard and fast rules for every problem, is the quickest way to find yourself falling short. If you search google for permutations, you'll get a zillion hits. Wikipedia might be the best for an overall, and sub-searches on specific types, should help out, as well. After all the mathematical and logical analysis, hot air, and hand waving, it's the testing that will answer your question, not proclamations. adak
