Recursion permutations

[Kalcor]

Aargh, I really need a way to know how to use recursion functions to permute abcd for example e.e I just can't seem to find an understandable way

[ne555]

¿do you mean to have all the permutations or the next_permutation()?

[dhayden]

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

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]
        }
   }
}

[Kalcor]

What if it's user input related? Not just a fixed abcd.

[dhayden]

I was just using abcd as an example. The algorithm will work with any input.