Are there any better methods to do permutation of string?

Question

void permute(string elems, int mid, int end) {     static int count;     if (mid == end) {         cout << ++count << " : " << elems << endl;         return ;     }     else {     for (int i = mid; i <= end; i++) {             swap(elems, mid, i);             permute(elems, mid + 1, end);             swap(elems, mid, i);         }     } } 

The above function shows the permutations of str(with str[0..mid-1] as a steady prefix, and str[mid..end] as a permutable suffix). So we can use permute(str, 0, str.size() - 1) to show all the permutations of one string.

But the function uses a recursive algorithm; maybe its performance could be improved?

Are there any better methods to permute a string?

Answer 1

Here is a non-recursive algorithm in C++ from the Wikipedia entry for unordered generation of permutations. For the string s of length n, for any k from 0 to n! - 1 inclusive, the following modifies s to provide a unique permutation (that is, different from those generated for any other k value on that range). To generate all permutations, run it for all n! k values on the original value of s.

#include <algorithm>  void permutation(int k, string &s)  {     for(int j = 1; j < s.size(); ++j)      {         std::swap(s[k % (j + 1)], s[j]);          k = k / (j + 1);     } } 

Here swap(s, i, j) swaps position i and j of the string s.

Answer 2

Why dont you try std::next_permutation() or std::prev_permutation() ?

Links:

std::next_permutation()
std::prev_permutation()

A simple example:

#include<string> #include<iostream> #include<algorithm>  int main() {    std::string s="123";    do    {        std::cout<<s<<std::endl;     }while(std::next_permutation(s.begin(),s.end())); } 

Output:

123 132 213 231 312 321