Faster matrix permutation algorithm?

Discussion in 'C Programming' started by Jack Middleton, Aug 13, 2005.

  1. 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
    Jack Middleton, Aug 13, 2005
    #1
    1. Advertising

  2. Jack Middleton

    Michael Mair Guest

    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.
    Michael Mair, Aug 13, 2005
    #2
    1. Advertising

  3. [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
    Richard Heathfield, Aug 13, 2005
    #3
  4. 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
    russell kym horsell, Aug 14, 2005
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. m sergei
    Replies:
    4
    Views:
    11,090
    Philip Parker
    Jun 29, 2004
  2. lvcargnini

    Matrix composed by two matrix

    lvcargnini, Jul 4, 2006, in forum: VHDL
    Replies:
    3
    Views:
    2,644
    Jonathan Bromley
    Jul 5, 2006
  3. robert
    Replies:
    2
    Views:
    589
  4. Replies:
    12
    Views:
    629
  5. Holgerson

    Matrix*Vector and Vector*Matrix

    Holgerson, Oct 25, 2007, in forum: C++
    Replies:
    3
    Views:
    396
    Holgerson
    Oct 26, 2007
Loading...

Share This Page