[Followups set to comp.programming]

Jack Middleton wrote:

Hi!

I'm lookin for a faster permutation algorithm for matrices. I know that

it can be done with multiplying a matrix with a permutation matrix. It

just seems a waste to iterate through all those zeroes. Is there an

algorithm for matrixes that is optimized just for permutations? The

matrices that I use are fairly small (around 6*6) and I only use

positive integers as elements.

Consider a mapping between a matrix X * Y elements in size and a series of

numbers from 0 to X * Y - 1. Such a mapping is reversible. To map from the

matrix cell references to a single number, use:

m = x * Y + y;

To map from the single number to cell references, use:

x = (m - y) / Y;

y = m % Y;

Set up a list of single numbers, 0 to X * Y - 1, in an array, and permute

the array, using the normal recursive technique. T is some (sensible)

assignable type. Perm is a pointer to the first element in an array of n

elements of type T. The final parameter, 'unchanged', is set to 0 in the

initial call:

void Permute(T *Perm, size_t n, size_t unchanged)

{

size_t outer = 0;

size_t inner = 0;

T temp = 0;

if(unchanged < n)

{

for(outer = unchanged; outer < n; outer++)

{

temp = Perm[outer];

for(inner = outer; inner > unchanged; inner--)

{

Perm[inner] = Perm[inner - 1];

}

Perm[unchanged] = temp;

Permute(Perm,

n,

unchanged + 1);

for(inner = unchanged; inner < outer; inner++)

{

Perm[inner] = Perm[inner + 1];

}

Perm[outer] = temp;

}

}

else

{

/* Perm[0] through Perm[n - 1] now form a permutation.

* If T is char, Perm points to a modifiable string

* containing the three letters 'a', 'b', 'c', n is 3, and

* unchanged is initially 0, then this else-block will be

* visited six times, and a printf("%s\n", Perm); at this

* point will write each of the six possible permutations,

* one per visit.

*/

}

}

Call this once, and it will do all your permutations for you. By making T

int, you can get a simple correspondence between the array and your matrix.

If you're feeling really brave, you could modify Permute() to talk to your

matrix directly, using the mapping I suggested earlier.

--

Richard Heathfield

"Usenet is a strange place" - dmr 29/7/1999

http://www.cpax.org.uk
mail: rjh at above domain