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?

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

Solution 4

In particular, you want std::next_permutation.

void permute(string elems, int mid, int end)
{
  int count = 0;
  while(next_permutation(elems.begin()+mid, elems.end()))
    cout << << ++count << " : " << elems << endl;
}

... or something like that...

Solution 5

The Knuth random shuffle algorithm is worth looking into.

// In-place shuffle of char array
void shuffle(char array[], int n)
{
    for ( ; n > 1; n--)
    {
        // Pick a random element to move to the end
        int k = rand() % n;  // 0 <= k <= n-1  

        // Simple swap of variables
        char tmp = array[k];
        array[k] = array[n-1];
        array[n-1] = tmp;
    }
}

View more solutions

Comments

[Omry Yadan]

keep in mind that in order to get all permutations your initial string/array must be sorted in ascending order.

[Jason Orendorff]

I think the STL has to re-examine the sequence each time it is called. The code in the question doesn't have to do any comparisons, so I think that might be more efficient (plus, it would work even on types that don't support <).

[tster]

n! is not polynomial, so no algorithm will be able to run in polynomial time.

[Potatoswatter]

Omry: INCORRECT. It goes in a cycle. The next permutation of the greatest permutation is the least permutation.

[Potatoswatter]

Using the return bool return value as the condition, you're correct, though.

[Potatoswatter]

concat is just an inferior version of v.insert(v.begin(), item). GetPermutations just does the same thing as OP's code, which is inferior to a loop with std::next_permutation.

[StackedCrooked]

I never claimed my solution to be superior :) That said, I don't see how my GetPermutations function is the same as the OP's code.

[David R Tribble]

Oh, never mind, I didn't read the problem closely enough. OP wants all permutations, not just one.

[Potatoswatter]

Any constructive criticism, or an example of input for which it fails?

[Jichao]

while ( pen != s.end() && * pen == value ) ++ cnt will cause infinite loop.

[Potatoswatter]

ah, correct. By the way, do you want permutations of unique elements, (n!) total, as your algo returns, or unique permutations, as counted by this?

[Jon Reid]

Remember, STL was invented by crazed mathematicians. Seriously, if you apply the algorithms correctly, you get high efficiency. And it's all part of C++!

[Jichao]

actually,I hanv't consider unique before,i assume elements of the input string are unique in my alg.

[Jichao]

notice there are many other problems in your algorithm.here is my version to count unique permutations:code.google.com/p/jcyangs-alg-trunk/source/brow‌​se/trunk/recur/…

[Potatoswatter]

Other problems such as what? Add ++pen after ++cnt. You shouldn't use double as a bignum class, by the way. Hmm, looking at my code, the call to sort isn't O(N). Whatever.

[Jichao]

have you tested your code?simple case abc would produce wrong answer or even crash the program.

[Jichao]

i haven't use uint64 before and <cstdint> would bring protability problem.definitly,i would update the code later.the call to sort isn't O(n),what do you mean by this?

[Potatoswatter]

I hadn't tested it before, but now that you ask, yes, it appears to work correctly once you add ++cnt.

[Potatoswatter]

uint64 also isn't a bignum class. You can use whatever kind of number you want; in any case, be sure you don't overflow. sort doesn't run in O(N) time, it's O(N log N).

[Potatoswatter]

Each call partitions the string into a stable and a recursively permuted part.

[Potatoswatter]

If the STL were really crazy math, it would have these: en.wikipedia.org/wiki/Fibonacci_heap

[Jichao]

it didn't work.while ( pen != s.end() && * pen == value ) ++ cnt, ++ pen; ,while pen iterate to the end of the string,cnt become 0,then divisor should be 0 too,which lead to the wrong result.

[Jichao]

antoher problem lies in your alg.Considering input 'aabbc',your alg would produce 5! / (2! * 2!),but the right answer should be c(5,2) * c(3,2) * 1!.

[Jichao]

could you explain it a bit more.this alg is hard to me.

[Omnifarious]

This is a poor variant of the answer actually selected.

[Omnifarious]

Someone selected the answer that said your answer was the best one. sigh And your answer is the best one.

[Potatoswatter]

1. cnt will always be advanced at least once. 2: factorial(0) = 1 even if it weren't. 3. C(n,k) = n!/(k!(n-k)!) so C(5,2)*C(3,2) = 5!3!/(2!3!2!1!) = 5!/(2!2!). You can work through the algebra to see they're always the same.

[Jichao]

correct.i'm wrong.i didn't use the standard factorial function.and your alg is much cleaner than mine.anyway thanks.

[Jichao]

one more trivial question:what compiler do you use?whats tr1 in the <tr1/stdint>?

[Potatoswatter]

Lol, thx, I didn't even think you could do that. Usually (on other people's questions I guess) the vote locks in after about a minute.

[Jichao]

not exactly.after you editing twice,the lock will be cleaned.

[Omnifarious]

I use g++ 4.4.x. TR1 is an interim standard for adding a few things to the C++ standard library. All headers that are part of TR1 will have tr1/ in front of them. See en.wikipedia.org/wiki/C%2B%2B_Technical_Report_1

[Omnifarious]

And the new C99 stdint.h header isn't part of C++, but with TR1 they added it as <tr1/cstdint>.

[Jeff Dege]

Another thought - the algorithm maps permutations to an integer between 0 and n!-1, which quickly overflows any reasonable integer size. If you need to work with larger permutations, you need an extended integer representation. In this case, a factoradic representation will serve you best. In a factoradic representation, instead of each digit representing a multiple of 10^k, each digit represents a multiple of k!. There is a direct algorithm for mapping a factoradic representation into a permutation. You can find details at en.wikipedia.org/wiki/Factoradic#Permutations

[Permaquid]

Such is life. The best-laid plans o mice and men gang aft agley.

[Reza Toghraee]

you can still get all the permutations based on Knuth shuffling algo! I just modified your solution and posted it below ;-)

[Harshdeep]

It's been four year since and Wikipedia article has been changed now so can you please elaborate why this would work! Exactly why it is guaranteed to be a kth unique permutation?

[Antiokus]

I know this is a few years old - but this solution doesn't give you all of the permutations. which ya know - is a problem.

[Kedar Mhaswade]

@Harshdeep I guess en.wikipedia.org/wiki/… is where it is explained ...