CODEWITHSUNDEEP
c++algorithmrecursion
JX2612
JX2612

Reputation: 45

Recursion to generate permutations

I find recursion, apart from very straight forward ones like factorial, very difficult to understand. If i want to print all permutations of a string, well lets say the string length is 5, like "abcde", the permutations of the length 7 should be

abced
abdce
abdec
abecd
abedc
acbde
acbed
acdbe
acdeb
acebd
acedb
adbce
adbec
adcbe
adceb
adebc
adecb
aebcd
aebdc
aecbd
aecdb
aedbc
aedcb
bacde
baced
badce
badec
baecd
baedc
bcade
bcaed
...

If I want a recursion to calculate all permutation of the Factorial of 5, like 4, 3, 2 or 1. Which algorithm should I use? Is there any function in a C++ library for this?

Assume the printout should look like this:

acbd
bcad
abc
bac
ab
ba

Upvotes: 2

Views: 2072

Answers (1)

delta
delta

Reputation: 3818

Using recursion algorithm, is pretty much like mathematical induction. First you need to deal with the base case, and then find the sub-problem pattern.

For factorial, define the problem as F(n) factorial of n.

  1. base case, F(0)=1
  2. sub-problem pattern, F(n)=n!=n*(n-1)!=n*F(n-1)

And for permutations, define P(E) as all permutation of set E.

  1. base case, P({}) = {{}}
  2. sub-problem pattern. Consider the process of permutation, let's say I have chosen the first element x, then we got a sub-problem, P(E-x), then for each p in P(E-x), and x to the front, we got all permutations starting with element x, iterate x you got all the permutations, aka P(E).

In C++, you can use next_permutation.

And the example code from the above thought is like:

// generate permutation of {a[st], a[st+1], ..., a[ed]}
void P(char a[], int st, int ed) {
    if (st > ed) { puts(a); return; } // nothing to generate
    for (int i=st; i<=ed; ++i) {
        swap(a[st], a[i]);            // enumerate first element
        P(a, st+1, ed);
        swap(a[st], a[i]);            // recover
    }
}

Check it on http://ideone.com/zbawY2.

Upvotes: 4

Related Questions