wh*************@gmail.com said:
What does inner outer and unchanged do?
Partition the array into two parts, an empty part, and the part you want to
permute.
| ABCDE
Move each element on the right-hand side to the left-hand side, in turn.
A | BCDE
B | CDEA
C | DEAB
D | EABC
E | ABCD
All you're really doing is rotating the array, yes?
For each of those partitioned array arrangements, we now have to solve the
problem of permuting the right-hand side, and incorporating the left-hand
side, ***unchanged***, into the final result.
Take A | BCDE, for example. We have 1 unchanged element, which will prefix
each solution, and an array, BCDE. We can solve this problem by recursing.
How? Well, like this...
Move each element on the right-hand side to the left-hand side, in turn.
AB | CDE
AC | DEB
AD | EBC
AE | BCD
All you're really doing is rotating the BCDE part of the array, yes?
For each of those partitioned array arrangements, we now have to solve the
problem of permuting the right-hand side, and incorporating the left-hand
side, ***unchanged***, into the final result.
Take AB | CDE, for example. We have 2 unchanged elements, which will prefix
each solution, and an array, CDE. We can solve this problem by recursing.
How? Well, like this...
Move each element on the right-hand side to the left-hand side, in turn.
ABC | DE
ABD | EC
ABE | CD
All you're really doing is rotating the CDE part of the array, yes?
For each of those partitioned array arrangements, we now have to solve the
problem of permuting the right-hand side, and incorporating the left-hand
side, ***unchanged***, into the final result.
Take ABC | DE, for example. We have 3 unchanged elements, which will prefix
each solution, and an array, DE. We can solve this problem by recursing.
How? Well, like this...
Move each element on the right-hand side to the left-hand side, in turn.
ABCD | E
ABCE | D
All you're really doing is rotating the DE part of the array, yes?
For each of those partitioned array arrangements, we now have to solve the
problem of permuting the right-hand side, and incorporating the left-hand
side, ***unchanged***, into the final result. But since each right-hand
side only has 1 element therein, there is only one permutation.
So for each of them we just display the result. ABCDE, and ABCED.
Then we drop out of this recursion, and continue with the next, and so on
until everything is done.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)