Subj : Re: Faster matrix permutation algorithm?
To   : comp.lang.c,comp.programming
From : Richard Heathfield
Date : Sat Aug 13 2005 02:02 pm

[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

.