The permutations of abcd are:
a, followed by all permutations of bcd, plus
b, followed by all permutatinos of acd, plus
c, followed by all permutations of bad, plus
d, followed by all permutations of bcd.
Expressed as an algorithm:
for each position i in the string
swap the first letter with the i'th letter
figure all permutations of positions 1-n
swap the first letter with the i'th letter (to restore the original order)
The base case is when the length of the string is zero.
That's the basic idea. To refine it, we have to recognize that the algorithm is really permuting a string from positions K-N where N is the length of the string and K is is value less than N, so
1 2 3 4 5 6 7 8 9 10 11 12
|
permute(string, K) // permute the string, starting at position K
{
if K is the length of the string then
string contains one permuation. Print it out or so whatever with it.
else
for (i = k; i<string.size(); ++k) {
swap string[k] with string[i]
permute(string, K+1);
swap string[k] with string[i]
}
}
}
|