Permutating through the array of chars

Question

Suppose you need to discover all possible permutations of 'n' distinct characters, say 'a', 'b', 'c'. Can you suggest an algorithm I can use to get this done? Generally speaking, how would you go about it?

Answer 1

There is a Java implementation here.

Answer 2

Let 'Perms' be the collection of permutations found, and 'Used' be a list of the characters currently selected.

To find permutations of n chars from a set S:

1. If n = 0, then Used is a permutation. Add it to Perms and return.
2. For each char C in S:
   1. Remove C from S and append (or push) it to U.
   2. Find permutations of n-1 chars from S.
   3. Remove the end of (or pop) U and add C to S.

When you've returned from finding permutations of n chars, Perms contains all the possible permutations.

Note, this is all done using sets and lists. There are lighter-weight alternatives, but these structures make the steps more straightforward, so i used them.