Permutation

Please support our C++ advertiser: Intel Parallel Studio Home
Thread Solved

Join Date: Jun 2007
Posts: 82
Reputation: hinduengg is an unknown quantity at this point 
Solved Threads: 3
hinduengg's Avatar
hinduengg hinduengg is offline Offline
Junior Poster in Training

Permutation

 
0
  #1
Jul 6th, 2007
Hello once again . My teacher has given us the assignment to enter a string a maximum of 7 charecters and permute it.
Then print all of possible permutations . Like if the inputted word is
JAY so Output would be
JAY
AJY
AYJ
JYA
YAJ
YJA


I do not seem to understand how to go about it. Please help.
I wish to know about some initial logic before developing the right code.

Thank you in advance.
hinduengg
Last edited by hinduengg; Jul 6th, 2007 at 3:02 pm.
Learning C++ is easy with Daniweb :)
Reply With Quote Quick reply to this message  
Join Date: Aug 2005
Posts: 5,264
Reputation: iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold 
Solved Threads: 377
Featured Poster
iamthwee's Avatar
iamthwee iamthwee is offline Offline
Posting Expert

Re: Permutation

 
0
  #2
Jul 6th, 2007
There's a few examples in the code snippets, some recursive some not.

There is also a function in the STL.
*Voted best profile in the world*
Reply With Quote Quick reply to this message  
Join Date: Jul 2005
Posts: 1,671
Reputation: Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all Lerner is a name known to all 
Solved Threads: 261
Lerner Lerner is offline Offline
Posting Virtuoso

Re: Permutation

 
0
  #3
Jul 6th, 2007
Since this is probably a learning experience in how to manipulate data rather than scrounging the archives of the Standard Template Library, I would suggest you consider this:

Using the JAY example if you did this:

JAY
JYA
AJY
AYJ
YJA
YAJ

and note that you can get all permutations by taking each element of the original and combining it with each of the remaining elements in order. Each element could be an element of an array and then you could loop through the array starting each loop with a new element and using other loops to get the rest of the elements in order. This process lends itself quite nicely to the concept of nested loops, which I have little doubt was the subject of one of your classes, although as iamthwee indicates there are other ways of doing this.
Last edited by Lerner; Jul 6th, 2007 at 3:13 pm.
Reply With Quote Quick reply to this message  
Join Date: Jun 2007
Posts: 82
Reputation: hinduengg is an unknown quantity at this point 
Solved Threads: 3
hinduengg's Avatar
hinduengg hinduengg is offline Offline
Junior Poster in Training

Re: Permutation

 
0
  #4
Jul 6th, 2007
Could you advice the link . I am not allowed to use stl strings its the char array that I need to use and functions related to it.
What I need is just the starting logic should I use for loops.
Learning C++ is easy with Daniweb :)
Reply With Quote Quick reply to this message  
Join Date: Aug 2005
Posts: 5,264
Reputation: iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold 
Solved Threads: 377
Featured Poster
iamthwee's Avatar
iamthwee iamthwee is offline Offline
Posting Expert

Re: Permutation

 
0
  #5
Jul 6th, 2007
>should I use for loops

whatever works...
*Voted best profile in the world*
Reply With Quote Quick reply to this message  
Join Date: Mar 2007
Posts: 1,429
Reputation: Nichito is an unknown quantity at this point 
Solved Threads: 29
Featured Poster
Nichito's Avatar
Nichito Nichito is offline Offline
Nearly a Posting Virtuoso

Re: Permutation

 
0
  #6
Jul 6th, 2007
if you show us how far you have gone, it will be easier for us to help you
-->sometimes i wanna take my toaster in a bath<--
Reply With Quote Quick reply to this message  
Join Date: Jun 2007
Posts: 82
Reputation: hinduengg is an unknown quantity at this point 
Solved Threads: 3
hinduengg's Avatar
hinduengg hinduengg is offline Offline
Junior Poster in Training

Re: Permutation

 
0
  #7
Jul 7th, 2007
Originally Posted by Nichito View Post
if you show us how far you have gone, it will be easier for us to help you
the concept is still in infancy development , I need your help:
this is so far I have developed the code:
  1. #include<iostream>
  2. int main()
  3. {
  4. int c,y,m=0;
  5. int z,fact;
  6. char a[100];
  7. for(y=0;a[y]!='\0';y++)
  8. c++;
  9. cout<<"the length"<<c<<endl;
  10. for(x=1;x<=c;x++)
  11. {
  12. fact=1;
  13. fact=fact*c;
  14. }
  15. cout<<"no of permutations"<<fact<<endl;
  16. for(int w=1;w<=fact;w++)
  17. for(int y=0;a[y]!='\0';y++)
  18. {
  19. m=y+1;
  20. cout<<a[m];
  21. }

I am unable to understand what to do to print permutations
and address index of the previous value of the string.
Last edited by ~s.o.s~; Jul 7th, 2007 at 10:58 am. Reason: Fixed code tags, learn to use them.
Learning C++ is easy with Daniweb :)
Reply With Quote Quick reply to this message  
Join Date: Aug 2005
Posts: 5,264
Reputation: iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold iamthwee is a splendid one to behold 
Solved Threads: 377
Featured Poster
iamthwee's Avatar
iamthwee iamthwee is offline Offline
Posting Expert

Re: Permutation

 
0
  #8
Jul 7th, 2007
If you know what a flow chart is you better start drawing one.


#include <iostream>
int main()
{
   int c, y, m = 0;
   int z, fact;
   char a[100];
   for ( y = 0; a[y] != '\0'; y++ )
      c++;
   cout << "the length" << c << endl;
   for ( x = 1; x <= c; x++ )
   {
      fact = 1;
      fact = fact * c;
   }
   cout << "no of permutations" << fact << endl;
   for ( int w = 1; w <= fact; w++ )
      for ( int y = 0; a[y] != '\0'; y++ )
      {
         m = y + 1;
         cout << a[m];
      }
}

Address the parts in red...
Last edited by iamthwee; Jul 7th, 2007 at 10:02 am.
*Voted best profile in the world*
Reply With Quote Quick reply to this message  
Join Date: Jun 2007
Posts: 82
Reputation: hinduengg is an unknown quantity at this point 
Solved Threads: 3
hinduengg's Avatar
hinduengg hinduengg is offline Offline
Junior Poster in Training

Re: Permutation

 
0
  #9
Jul 7th, 2007
this is the code that I actually got while browsing through code snippets

  1. #include<iostream>
  2. #include<cstring>
  3.  
  4. using namespace std;
  5.  
  6. void char_permutation(char str[],char append[])
  7. {
  8. int length = strlen(str);
  9. if (length)
  10. {
  11. for(int i=0;i<length;++i)
  12. {
  13. char* str1 = new char[length+1];
  14. int cnt;
  15. int cnt2;
  16. for(cnt=0,cnt2=0; cnt<length; ++cnt,++cnt2)
  17. {
  18. if (cnt == i)
  19. {
  20. str1[cnt] = str[++cnt2];
  21. continue;
  22. }
  23. else
  24. str1[cnt] = str[cnt2];
  25. }
  26. str1[cnt] = '\0';
  27.  
  28. int alength = strlen(append);
  29. char* append1 = new char [alength+2];// why adding 2 here
  30. strncpy(append1,append,alength);
  31. append1[alength] = str[i];
  32. append1[alength+1] = '\0';
  33.  
  34. char_permutation(str1,append1);
  35.  
  36. delete []str1;
  37. delete []append1;
  38. }
  39. }
  40. else
  41. {
  42. cout << append << endl;
  43. }
  44. }
  45.  
  46.  
  47. int main()
  48. {
  49. char str[] = "BUSH"; // shows a little humor
  50. char append[] = "\0";
  51.  
  52. cout << "Original = " << str << endl;
  53. char_permutation(str,append);
  54. cout << "Done ........" << endl;
  55.  
  56. cin.get(); // wait
  57. return 0;
  58. }

Please devote some of your precious time in making me understand this. My question is in the code comments , please,please tell the reason for that. Varunthai had understood it but he did not write any grain of logic for me to understand!

Till now I have understood that there are 2 strings on which permutation is working but the process of cnt cnt2 ,and statements like - char* append1 = new char [alength+2]; confuse me then.
please help

I would appreciate your help greatly

hinduengg
Last edited by WaltP; Jul 8th, 2007 at 1:29 am. Reason: Fixed CODE tags -- please use the PREVIEW button
Learning C++ is easy with Daniweb :)
Reply With Quote Quick reply to this message  
Join Date: Jun 2007
Posts: 13
Reputation: darkscript is an unknown quantity at this point 
Solved Threads: 1
darkscript darkscript is offline Offline
Newbie Poster

Re: Permutation

 
1
  #10
Jul 8th, 2007
The idea here is to make each character in the string exist in every position, for example:

string is "JOY"

so taking J:-
1st pass: "JOY"
2nd pass: "OJY"
3rd pass: "OYJ"

taking O:-
1st pass: "OJY"
2nd pass: "JOY"
3rd pass: "JYO"

taking Y:-
1st pass: "YOJ"
2nd pass: "JYO"
3rd pass: "JOY"

then remove the repeated results, and you'll get all the combinations for that string
Reply With Quote Quick reply to this message  
Reply

This thread has been marked solved.
Perhaps start a new thread instead?
Message:



Similar Threads
Other Threads in the C++ Forum
Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC