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.

VALUES
a b c
1 2 3
x y z
PERMUTATIONS
a1x a1y a1z a1
a2x a2y a2z a2
a3x a3y a3z a3 a
b1x b1y b1z b1
b2x b2y b2z b2
b3x b3y b3z b3 b
c1x c1y c1z c1
c2x c2y c2z c2
c3x c3y c3z c3 c

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

The array is mostly small. The total permutation values shouldn't be more than a few thousand.

The values are generated dynamically, and the number of rows and column in the array is variable.

Showing the values by a simple string is just a simplification of what I need. In the real case, I generate an array of permuted values, and I perform the algorithm's steps on them.

Order is important. The permutations must be generated exactly in the order shown.

Research

I found several permutation examples, and I tried out merlyn's Permutations and combinations. It works as advertised, but it doesn't do what I need.

Other variants of permutation algorithms don't offer any handle to do what I need, and some don't even guarantee a given order.