[...]
totally has 27 combinations. I know recursion should be used but don't know
how.
Just curious...are you and Michalik taking the same class?
As far as the question goes, it would be cheating you to actually give the
exact answer. But consider this:
-- if in your method you pick one character from the string, and then
combine that character with all the permutations of the original string
without that character, you get all the possible permutations.
-- if you are asked to permute a string that is only one character long,
there is only one permutation
Those two facts together should suggest a possible recursive approach. That
is, you've got one statement that provides a "base case" solution, and
another statement that defines the problem in terms of itself, but reducing
the complexity in a well-defined way before referring to itself. That's
basically recursion in a nutshell.
I was thinking about how you could do this non-recursively and without
using a stack. The set of all permutations of a sequence (such as a
string) constitutes a group under composition of permutations. Is there
some bit of group theory we can use to efficiently enumerate the elements
of the group? I was thinking that if there was a generator, you could just
start with that, and compute powers of it to run through the whole group.
However, a symmetric group (which is what the group of all permutations of
a set is called) doesn't have a single generator; it has a generating set
consisting of two permutations - one which swaps the first two elements,
and one which barrel shifts all elements one place. What i don't know is
how you combine these to enumerate all the elements of the group.
Another approach would be to map each permutation onto a number such that
the numbers form a continuous range, then walk through that range and
reverse the mapping. That's easy enough: put the members of the set to be
permuted in order, then go through the permutation, finding the element
picked by each position of the permutation, recording its index in the
ordered set, and then removing it from the set. Then compute the product
of each index with the number of elements in the set before each removal.
That description doesn't make any sense, does it? Consider the
permutation:
<B A D C>
The set is :
{A B C D}
So the first position, B, gets index 1, for 4 elements. You then have
remaining:
{A C D}
So the second position, A, comes out as 0, of 3 elements. The it's:
{C D}
Position three is D, which is 1 of 2. Then it's just:
{C}
And C is 0 of 1. The products are:
(1 * 4) + (0 * 3) + (1 * 2) + (0 * 1) = 6
To decode this to a permutation, you do it all in reverse, modding out
indices with a decrementing modulus starting at the size of the set. Once
you have the indices, you do a draw-without-replacement from the ordered
set to assemble the permutation.
This avoids any recursion, but i can't see a terrifically efficient way to
implement it.
However, this only works up to sets of 12 elements, at which point there
are more than 2**31 permutations, and the number overflows, at least if
you're using ints. Using longs gets you up to 21 elements. Although,
whilst that doesn't seem a lot, you're never going to need more - any plan
which involves going through all possible permutations more than 21
elements is a non-starter, because it would take forever.
(I know the OP wasn't actually asking about permutations - but this is
more interesting!)
tom
