Multidimensional manipulation in C by Column

Question

There is still no good definition for this functionality that I can find anywhere on stack overflow.

What is the code or theorem associated with moving an entire column up or an entire row across? For instance

1 2 3
4 5 6
7 8 9

If I push the last column up it would be

1 2 6
4 5 9
7 8 3

If I push the last row rightward it would be

1 2 6
4 5 9
3 7 8

I want to know all different types of ways to approach this type of problem.

One way I know is to find an array and since multidimensional-arrays are just arrays of array, I can collect that array into a new array? A Pointer? Explain. It is a very difficult concept to grasp.

Answer 1

To rotate a column or a row, you can start by copying one element to a temp variable. Then overwrite that element with another element. Then overwrite the second element with a third element and so on til you reach the end of the column/row. Then you overwrite the last element with the temp variable.

Rotating a column up can be shown like this. The red numbers are the steps to perform.

Here is some code that may get you started.

#include <stdio.h>

// column  : The column to rotate
// rows    : The total number of rows
// columns : The total number of columns
void rotate_column_up(int column, int rows, int columns, int arr[][columns])
{
    int i;
    int temp = arr[0][column];
    for (i=1; i<rows; ++i)
    {
        arr[i-1][column] = arr[i][column];
    }
    arr[rows-1][column] = temp;
}

void rotate_column_down(int column, int rows, int columns, int arr[][columns])
{
    int i;
    int temp = arr[rows-1][column];
    for (i=rows-1; i>0; --i)
    {
        arr[i][column] = arr[i-1][column];
    }
    arr[0][column] = temp;
}

// row     : The row to rotate
// rows    : The total number of rows
// columns : The total number of columns
void rotate_row_left(int row, int rows, int columns, int arr[][columns])
{
    int i;
    int temp = arr[row][0];
    for (i=1; i<columns; ++i)
    {
         arr[row][i-1] = arr[row][i];
    }
    arr[row][columns-1] = temp;
}

void rotate_row_rigth(int row, int rows, int columns, int arr[][columns])
{
    int i;
    int temp = arr[row][columns-1];
    for (i=columns-1; i>0; --i)
    {
         arr[row][i] = arr[row][i-1];
    }
    arr[row][0] = temp;
}

void print_array(int columns, int rows, int arr[][columns])
{
    int i, j;
    for(j=0; j<rows; ++j)
    {
        for(i=0; i<columns; ++i)
        {
            printf("%d ", arr[j][i]);
        }
        printf("\n");
    }
        printf("\n");
}

int main(void) {
    int arr[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

    printf("Original array\n");
    print_array(3, 3, arr);

    printf("Column 2 up\n");
    rotate_column_up(2, 3, 3, arr);
    print_array(3, 3, arr);

    printf("Row 2 rigth\n");
    rotate_row_rigth(2, 3, 3, arr);
    print_array(3, 3, arr);

    printf("Row 2 left\n");
    rotate_row_left(2, 3, 3, arr);
    print_array(3, 3, arr);

    printf("Column 2 down\n");
    rotate_column_down(2, 3, 3, arr);
    print_array(3, 3, arr);

    return 0;
}

Output:

Original array
1 2 3
4 5 6
7 8 9

Column 2 up
1 2 6
4 5 9
7 8 3

Row 2 rigth
1 2 6
4 5 9
3 7 8

Row 2 left
1 2 6
4 5 9
7 8 3

Column 2 down
1 2 3
4 5 6
7 8 9

Answer 2

There are many ways of looking at this problem.

Let's start with something simple. Here we don't move things around, but just make it look like it. So for an array of n-elements:

A_n = [ e₀, e₁, e₂, ..., e_n-1 ];

We can just do interesting maths on index (using its size and the remainder function) to rotate through the array starting at the i^th element where 0 ≤ k < n. The pseudo code for making would be:

    i = (n - (k - j)) % n

So let's look at an example program that rotates an array of ints, that takes a starting point from the command-line and lists the elements in the array as if the starting point was 0 and that the end was connected back to the beginning.

rotate1.c:

#include <stdio.h>
#include <stdlib.h>

const int a[] = { 10, 20, 30, 40, 50 };
const int N = sizeof(a) / sizeof(int);

int main(int argc, char *argv[]) {
    int i, j;
    int BASE = 0;
    if (argc > 1) {
        BASE = atoi(argv[1]);
    }
    for(j = 0; j < N; j++) {
        i = (N - (BASE - j)) % N;
        fprintf(stderr, "%d\n", a[i]);
    }
}

You can modify this program to rotate any type of array, even columns or rows of a matrix because those are just arrays of arrays.

Another approach would be to use a ring.

Creating a ring using linked lists

A ring as a linked list where the last element of the list points to the first element of the list.

Linux kernel list.h implements doubly linked "rings". There are very nice consequences of having a ring. For instance, since there's no actual head, every element works as a head; If you have a doubly linked "ring" you can simplify the programming.

I won't go into how that's accomplished as the canonical implementation is available in the linux kernel source code at include/linux/list.h and is beautifully documented.