# 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?

1
50
1/18/2010 2:25:37 AM

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.

64
2/25/2015 4:52:30 AM

Why dont you try std::next_permutation() or 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