Permutations

Write a program to display all possible permutations of a given input string--if the string contains duplicate characters, you may have multiple repeated results. Here is a sample for the input cat
cat,cta,act,atc,tac,tca

Questions by dhairaybablani

Showing Answers 1 - 15 of 15 Answers

Tehan Frago

  • Feb 13th, 2015
 

Here is an answer that considers all possible permutations including duplicates. If, however, you wanted to remove duplicated, you could save the answers into a vector if they are unique then print all the elements.


Code
  1. #include <string>

  2. #include <iostream>

  3.  

  4. using namespace std;

  5.  

  6. void Permutations(string str)

  7. {

  8.         for(int i = 0; i < str.size(); i++)

  9.         {

  10.                 for(int j = 0; j < str.size()-1; j++)

  11.                 {

  12.                         char temp = str[j];

  13.                         str[j] = str[j+1];

  14.                         str[j+1] = temp;

  15.                         cout << str << endl;

  16.                 }

  17.         }

  18. }

  19.  

  20. int main()

  21. {

  22.         string str;

  23.         cin >> str;

  24.  

  25.         Permutations(str);

  26.  

  27.         return 0;

  28. }

  29.  

  Was this answer useful?  Yes

Sergey

  • May 4th, 2015
 

Hi Tehan! This is a wrong solution. A string of the size N has N! (N factorial) permutations while you have only N*(N-1) ones
One of the solutions is to use some kind of recursion

  Was this answer useful?  Yes

Rajni kant

  • Aug 27th, 2015
 

Code
  1. #include <iostream>

  2. using namespace std;

  3.  

  4. int visited[10000];

  5. char array1[10000];

  6. int count1 = 3;

  7.  

  8. int ttaa;

  9.  

  10.  

  11. void print_perm(char* srt, int index)

  12. {

  13.         if (index == count1) {

  14.                 cout << array1<<"

  15. ";

  16.                 ttaa++;

  17.                 return;

  18.         }

  19.         for (int p = 0; p < count1;p++)

  20.         {

  21.                 if (visited[p] == 1)continue;

  22.                 array1[index] = srt[p];

  23.                 visited[p] = 1;

  24.                 print_perm(srt,index+1);

  25.                 visited[p] = 0;

  26.         }

  27. }

  28.  

  29. void main()

  30. {

  31.         count1 = strlen("abc");

  32.         print_perm("abc", 0);

  33.        

  34.         cout << ttaa << endl;

  35. }

  Was this answer useful?  Yes

neha

  • Aug 27th, 2015
 

Plz see below code

Code
  1. #include <string>

  2.  

  3.  

  4. #include <iostream>

  5.  

  6.  

  7.  

  8.  

  9.  

  10. using namespace std;

  11.  

  12.  

  13.  

  14.  

  15.  

  16. void Permutations(string str)

  17.  

  18.  

  19. {

  20.         for(int i = 0; i < str.size(); i++)

  21.         {

  22.                 for(int j = i; j < str.size(); j++)

  23.                 {

  24.                         char temp = str[j];

  25.  

  26.  

  27.                         str[j] = str[i];

  28.  

  29.  

  30.                         str[i] = temp;

  31.  

  32.  

  33.                         cout << str << endl;

  34.                 }

  35.         }

  36. }

  37.  

  38.  

  39.  

  40. int main()

  41. {

  42.         string str;

  43.         cin >> str;

  44.         Permutations(str);

  45.  

  46.         return 0;

  47. }

  Was this answer useful?  Yes

Jin Hyuk Cho

  • Feb 3rd, 2016
 

A working example

Code
  1. #include <iostream>

  2. #include <string>

  3. #include <set>

  4. #include <sstream>

  5.  

  6. using namespace std;

  7.  

  8. void permute (set<char> &chars, set<string> &permuted) {

  9.     if (chars.size() == 1) {

  10.         stringstream charSS;

  11.         charSS << *(chars.begin());

  12.         permuted.insert(charSS.str());

  13.         return;

  14.     }

  15.     for (set<char>::iterator it = chars.begin(); it != chars.end(); ++it) {

  16.         // constructing remaining characters

  17.         set<char> remainingChars(chars);

  18.         remainingChars.erase(*it);

  19.         // constructing empty set for results

  20.         set<string> permutedRemainingStrings;

  21.         permute(remainingChars, permutedRemainingStrings);

  22.         for (set<string>::iterator rit = permutedRemainingStrings.begin();

  23.              rit != permutedRemainingStrings.end();

  24.              ++rit) {

  25.             stringstream ss;

  26.             ss << *it << *rit;

  27.             string onePermute = ss.str();

  28.             //cout << onePermute << endl;

  29.             permuted.insert(onePermute);

  30.         }

  31.     }

  32. }

  33. int main () {

  34.    

  35.     ostream_iterator<string> output(cout, " " );

  36.     set<char> chars = {c, a, t};

  37.     set<string> permuted;

  38.     permute(chars, permuted);

  39.     copy(permuted.begin(), permuted.end(), output);

  40.     cout << "Done!" << endl;

  41.    

  42.    

  43.     return 0;

  44. }

  Was this answer useful?  Yes

Give your answer:

If you think the above answer is not correct, Please select a reason and add your answer below.

 

Related Answered Questions