Recursion to generate permutations

Question

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

Have you tried anything yet? Some code perhaps? Checkout this question on interview cake for a descent explanation of the mechanics — adamb
– adamb, Commented Jun 11, 2016 at 14:38
Factorial of 5 is 120... I think you meant permutations of length less or equal to 5 — OneCricketeer
– OneCricketeer, Commented Jun 11, 2016 at 14:55

delta · Accepted Answer · 2016-06-11 15:31:33Z

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.

base case, F(0)=1
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.

base case, P({}) = {{}}
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.

Collectives™ on Stack Overflow

Recursion to generate permutations

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related