trying to understand string permutations?

Question

I found this sweet code here: http://geeksforgeeks.org/?p=767 the source link: http://mathworld.wolfram.com/Permutation.html

ok how do I even begin to understand these codes? how do I start coding like this? I have encountered many such codes...using dynamic programming, backtracking, branch and bound...and understood squat.

even if u debug them..u cannot understand much..let alone start coding like them.

is some kind of advanced math knowledge is needed..?

Answer 1

You need to understand the algorithm first - that's the hard part. Once you understand the algorithm then the implementation in an actual programming language is relatively straightforward. So - forget about code for now - focus on algorithms and data structures.

Answer 2

Try to first understand the higher level pseudocode instead of all the language specific details. If you are not well versed in the computer language of the code that you are trying to disect, it will also make things much tougher.

Answer 3

Here's a quick explanation.

Consider a set X = {x1, x2, ..., xn}. A permutation of X must start with some xi, followed by a permutation of X \ {xi}.

The cunning C implementation does just this, exploiting the following invariant: every call to permute() returns leaving the array unchanged (essentially it computes a permutation of the array, prints it out, then undoes the permutation). That's what these lines do:

// Permute a[i..n]:
swap((a+i), (a+j));  // Make a[j] the start of this (sub-)permutation starting at i.
permute(a, i+1, n);  // Find the permuations of a[i+1..n] - and undo them.
swap((a+i), (a+j));  // Undo the swap of a[i] and a[j].