7

I have an non-square array like this:

const int dim1 = 3, dim2 = 4;
int array[12] = { 1, 2, 3, 
                  4, 5, 6,
                  7, 8, 9,
                 10,11,12};

and I need to convert it to:

{3,6,9,12,
 2,5,8,11,
 1,4,7,10}

that is, rotate/shuffle it counter-clockwise (or clockwise, the algorithm should be similiar).

The algorithm should use a minimal amount of space. I have to rotate an image in an extremely memory-constrained environment, so the less space the better. Speed is not as big an issue.

Improve this question
1
  • 1
    Is the rotation always in 90° steps? Commented Sep 23, 2010 at 10:00

5 Answers 5

Reset to default
9

You can transpose the matrix in-place (see http://en.wikipedia.org/wiki/In-place_matrix_transposition) and then reverse the rows which is trivial.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I'm afraid that your only choice is either translate the fortran source or read the papers and implement it from scratch. Note that any algorithm you find for your original problem implies a solution for matrix-transposition problem which is widely known.
2

Assume the arr is m x n. If you rotate it clockwise, it's easy to summarize that arr[i][j] becomes arr[j][m - 1 - i].

To reach there, we could first transpose so that arr[i][j] becomes arr[j][i]. Then we reverse current each row so that arr[j][i] becomes arr[j][m - 1 - i].

To avoid index out of bound, we need to figure out the maximal of m and n and fill the arr to make it a square. Then to apply our algorithm. I think this filling doesn't violate the in-place requirement. The code is shown as below:

pub fn rotate_matrix_90_degrees(matrix: &mut Vec<Vec<i32>>) {
    let (m, n) = (matrix.len(), matrix[0].len());
    let mx = m.max(n);
    
    if mx > m {
        for _ in m..mx {
            matrix.push(vec![i32::MIN; mx]);
        }
    }
    if mx > n {
        for i in 0..mx {
            for _ in n..mx {
                matrix[i].push(i32::MIN);
            }
        }
    }

    // arr[i][j] = arr[j][m - i - 1]
    // arr[i][j] -> arr[j][i]
    for i in 0..mx {
        for j in (i + 1)..mx {
            let tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }
    
    // arr[j][i] -> arr[j][m - i - 1]
    for i in 0..mx {
        matrix[i].reverse();
    }
   
    // Remove fillings
    if mx > m {
        for i in 0..mx {
            for _ in m..mx {
                matrix[i].pop();
            }
        }
    }

    if mx > n {
        for _ in n..mx {
            matrix.pop();
        }
    }
}
Improve this answer

Comments

1

The 2D rotation formula is:

x' = x cos f - y sin f
y' = y cos f + x sin f

If you only rotate in 90° steps, the resulting formula becomes:

x' = -y
y' =  x

Since the array isn't square you'll have to look for assignment cycles, i.e. element (0, 0) gets assigned element (2, 0) which in turn gets assigned (2, 2) etc. You'll need to assign each cycle at the "same" time.

Thus to rotate the whole array you'll do something like (pseudo-code):

// this function rotates 90 degrees
point successor(const point &p)
{
  return (-p.y, p.x);
}

// this function rotates 90 degrees in opposite direction
point predecessor(const point &p)
{
  return (p.y, -p.x);
}

void replace_cycle(const point &start)
{
  int data = get_data(start);
  point x = predecessor(start);
  while(x != start)
  {
    set_data(successor(x), get_data(x));
    x = predecessor(x);
  }
  set_data(successor(start), data);
}

void rotate_in_place()
{
  list<point> l;
  find_cycles(l);
  foreach(c in l)
  {
    replace_cycle(c);
  }
}
Improve this answer

3 Comments

I think you are answering different question here.
@wilx: Please read the question again, rotate the array in place! Please don't downvote unless you understand both the question and the answer.
@wilx: Agreed my initial attempt may have been a bit naïve, but it was no less helpful than the answer describing an xor swap and it was definitely not a different question I was answering.
0

Not rotating at all may be an option. You just set a flag that would give the way the matrix should be read.

The drawback is that if that image must be provided to some display device or such with fixed direction, that may not be possible.

Improve this answer

4 Comments

there is also a cache locality penalty when traversing the table. Before, traversing row by row is efficient, afterward it would imply seemingly random reads.
@Matthieu M. This is right if you are traversing tables by rows but we have no information on that. Also OP explicitely stated that he was more concerned about space than speed.
I know, yet it is somewhat to take into account. Most of the times I don't care too much about performance, unless it makes my soft unusable that is :-)
@Matthieu M.: in such a case not using the right access to memory could indeed slow down by several orders of magnitude.
-2

You can use xor to use no additional memory.

// Switch a and b
int a;
int b;
a ^= b;
b ^= a;
a ^= b;

Then you can use a simple for loop to make your whole matrix.

Improve this answer

2 Comments

Looks that would easily work for square matrix, but (as far as I can see) not for non square matrixes.
It's of size [12]. it's not 2 dimentional in memory. Only the interpretation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.