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