神刀安全网

All permutations of a string using iteration

A permutation, also called an “arrangement number” or “order”, is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. A string of length n has n! permutation ( Source: Mathword )

Below are the permutations of string ABC.ABC ACB BAC BCA CBA CAB

We have discussed different recursive approaches to print permutationshere andhere.

How to print all permutations iteratively?

Recursion is always costly and iteration is preferred. Below are steps of iterative approach.

  1. Find no of permutations of the string by calculating value of n!. Then use this value to iterate.
  2. Store the original string in an auxiliary string and use that string to do the math.
  3. Fix the first position(character), and swap all the j’th and (j+1)’th characters till (n-1)!.
  4. At the end of first (n-1)! all the (n-1)th characters will be permuted.
  5. Now again store the original string to the auxiliary string and swap i’th and (i+1)’th characters and repeat the 3rd and 4th process.

AND VOILA!!! with all the Permutations of the string.

Example :Consider a string “abcd”.

Concept Used :We keep swapping a character only till it reaches the end

  1. Fix ‘a’. Swap ‘b’ with its next neighbors till b reaches the end.
    ( “acbd”, “acdb”)
  2. Now ‘c’ will be at the 2nd position, do the same thing with it.
    ( “adcb”, “adbc”)
  3. Now ‘d’ will be at the 2nd position, do the same thing with it.
    ( “abdc”, “abcd”)
  4. All 6 i.e., (4!/4)permutations of the first cycle obtained.
  5. Repeat the above process by bringing swapping ‘a’ with ‘b’
  6. The new string to “play” will be “bacd”.

Below is C++ implementation of above idea.

// An iterative C++ program to find all permutations of // a given string. #include<bits/stdc++.h> using namespace std;  // A utility function to find n! int fact(int n) {     return (n==1)? 1 : n*fact(n-1); }  // An iterative function to print all permutations of s. void printPermutation(string s) {     // Find length of string and factorial of length     int n = s.length();     int fc = fact(n);      // Point j to the 2nd position     int j = 1;      // To store position of character to be fixed next.     // m is used as in index in s[].     int m = 0;      // Iterate while permutation count is     // smaller than n! which fc     for (int perm_c = 0; perm_c < fc; )     {         // Store perm as current permutation         string perm = s;          // Fix the first position and iterate (n-1)         // characters upto (n-1)!         // k is number of iterations for current first         // character.         int k = 0;         while (k != fc/n)         {             // Swap jth value till it reaches the end position             while (j != n-1)             {                 // Print current permutation                 cout << perm << "/n";                  // Swap perm[j] with next character                 swap(perm[j], perm[j+1]);                  // Increment count of permutations for this                 // cycle.                 k++;                  // Increment permutation count                 perm_c++;                  // Increment 'j' to swap with next character                 j++;             }              // Again point j to the 2nd position             j = 1;         }          // Move to next character to be fixed in s[]         m++;          // If all characters have been placed at         if (m == n)            break;          // Move next character to first position         swap(s[0], s[m]);     } }  // Driver code int main() {     string s = "ABC";     printPermutation(s);     return 0; }

Output :

ABC ACB BAC BCA CAB CBA

This article is contributed by Abhishek Kumar . If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » All permutations of a string using iteration

分享到:更多 ()

相关推荐

  • 暂无文章

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址