permutation matrix

Originally Posted by bossie

I want to create an algoritm (to use in VBA) that produces all "permutation matrices" (each row and each column has maximum one "1", the other cells are "0") for any given number of rows and columns.
The goal is to find the best possible matches between two groups.
Creating these permutation matrices for a low number of rows and columns can be done manually, but since the number of possibilities grows exponentially, I need an algoritm.

Anybody has any experience in this area? Anyone with ideas?

I do think it's possible, but my math knowledge is limited...

It should be something along the lines of "start with a model matrix, and switch (permute?) all rows and columns one by one..."

I've attached an example file (with comments in Dutch).
This is a simple model (only 3 by 3), hand made.
I'm looking for a way to get the same result for bigger numbers (up to 50*50).
The way I'm trying to solve this is a s follows:
The candidates choose which area they want to work in, they choose by ranking the possible choiches (best choice = 1; second best = 2, etc)
The providers do the same (they choose among the candidates.
I multiply both matrices.
The I multiply the 'product' matrix with every possible way (the permutation matrices) to 'match all of the candidates.
The combination with the 'lowest' score is the best match.

It is quite easy for low numbers, but the amount of possibillities grows exponentially, with every next number. Which is why I want to find an algoritm that produces these 'permutation matrices'.

Sorry folks if my previouw explanation wasn't clear enough...

I don't have any experience programming these, but a quick look at the "permutation" article at Wikipedia suggests to me that the Steinhous-Johnson-Trotter algorithm might be useful. The example they use is for integers 1,2,3,...,n. If you think of those as column (or row) labels for the identity matrix, you should be able to see how to apply it to your matrices.

alright! Thx folks.
I do believe this helps to find the right way tot the (a) solution.
I'll give it a go. and this way, I can mark this thread as solved!
thx 'snb', thx 'MrShorty'