Are there any better methods to do permutation of string?

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?

Solution 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.

Solution 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

Solution 3:

I'd like to second Permaquid's answer. The algorithm he cites works in a fundamentally different way from the various permutation enumeration algorithms that have been offered. It doesn't generate all of the permutations of n objects, it generates a distinct specific permutation, given an integer between 0 and n!-1. If you need only a specific permutation, it's much faster than enumerating them all and then selecting one.

Even if you do need all permutations, it provides options that a single permutation enumeration algorithm does not. I once wrote a brute-force cryptarithm cracker, that tried every possible assignment of letters to digits. For base-10 problems, it was adequate, since there are only 10! permutations to try. But for base-11 problems took a couple of minutes and base-12 problems took nearly an hour.

I replaced the permutation enumeration algorithm that I had been using with a simple i=0--to--N-1 for-loop, using the algorithm Permaquid cited. The result was only slightly slower. But then I split the integer range in quarters, and ran four for-loops simultaneously, each in a separate thread. On my quad-core processor, the resulting program ran nearly four times as fast.

Just as finding an individual permutation using the permutation enumeration algorithms is difficult, generating delineated subsets of the set of all permutations is also difficult. The algorithm that Permaquid cited makes both of these very easy