Faster matrix permutation algorithm?

[Jack Middleton]

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.

Thanks for help,

Jack Middleton

 

[Michael Mair]

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.

Note that this is off-topic in comp.lang.c from where I am posting.
-> f'up2c.p

Some thoughts on your question:
- Do you want to restrict yourself to certain classes of permutations
or do you just want the matrix elements reordered in a random way?
- In the latter case, if you are programming in a language where you
know the memory layout and where the memory layout of the matrix is
essentially an array, you can just use (perfect) shuffling -- or,
if you need all permutations, a loop through all array permutations.
- Otherwise, just perform the effective action of the matrix-matrix
multiplication: Interchange the rows/columns of the target matrix as
intended.


Cheers
Michael

 

[Richard Heathfield]

[Followups set to comp.programming]

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.

 

[russell kym horsell]

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.

[...]


If you want to permute rows/cols (or both) then you can simply iterate
through one or more maps/indexes. Manipulate the maps directly and
only use them as indexes at the last second.


==========
Before you ask a question you must know most of the answer.
-- anon