|Perl: the Markov chain saw|
Variant permutationby gmax (Abbot)
|on Aug 30, 2003 at 11:00 UTC||Need Help??|
gmax has asked for the
wisdom of the Perl Monks concerning the following question:
For an algorithm related to code generation I need to permute the values of an array, but in addition to a regular permutation, I need also to report the partial permutation of the values.
In the example above, the first three columns are the result of a standard permutation, in addition to that, I need to generate "a1" when it is no longer part of the permuted value. Therefore, before "a2x", I need to create "a1", before "b1x" I must create "a3". The same goes for "a", which is generated immediately before the permuted value starts showing "b".
I hope the example is clearer than my explanation. :)
More detail about the problem
Other variants of permutation algorithms don't offer any handle to do what I need, and some don't even guarantee a given order.
The problem is recursive, not only that, but it has also some reminiscence of tree traversal, so I tried with a Tree.
This does exactly what I need, even though I have a gut feeling that it could be better.
I can live with this solution, if there is nothing else available.
Any paths for improvement?
Can anyone suggest a more linear course of action?
_ _ _ _ (_|| | |(_|>< _|