448,659 Members | 1,689 Online Need help? Post your question and get tips & solutions from a community of 448,659 IT Pros & Developers. It's quick & easy.

# Faster matrix permutation algorithm?

 P: n/a 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 Nov 15 '05 #1
3 Replies

 P: n/a Jack Middleton wrote: 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 -- E-Mail: Mine is an /at/ gmx /dot/ de address. Nov 15 '05 #2

 P: n/a [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 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 Nov 15 '05 #3

 P: n/a In comp.lang.c 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. [...] 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 Nov 15 '05 #4

### This discussion thread is closed

Replies have been disabled for this discussion. 