CODEWITHSUNDEEP
carrays
user565447
user565447

Reputation: 999

Row/column permutation

I have a quadratic matrix(two-dimensional dynamic array of pointers) and need to change rows/columns order. The matrix is very big that's why I have decided just to change pointers instead of copying all of elements. I also have another array which specifies a computation. Rows permutation specifies this way: 4,3,2,1 - it means that the first row must be on the fourth place, the second row must be on the third place, etc. The same situation is with the columns. http://xmages.net/storage/10/1/0/8/6/thumb/thumb_40561a35.jpg

How to implement such algorithm of changing of rows order(permutation of of pointers)? Here it is my version, but it doesn't work. I want to copy pointers but element is copied instead of it and then appears a segmentation fault. When I add '&' to get address, the compiler says that it is a syntax error:

orderOfRows[i] = &auxMatrix[computation[i]];

Here it is my code:

static int N = 6;
static int **orderOfRows;
int **sourceMatrix;
int **auxMatrix;

int main() {
int* computation = (int*)malloc(N*sizeof(int));

computation[0] = 1;
computation[1] = 6;
computation[2] = 3;
computation[3] = 7;
computation[4] = 4;
computation[5] = 2;

}
printf("After computation has been done: \n");
changeRowOrder(computation);

 void changeRowOrder(int *computation) {
int i;
// change rows order and dopy them into a temp array
for(i = 0; i < N; ++i) {
    // static arrays
    orderOfRows[i] = auxMatrix[computation[i]];
}
// recover matrix
for(i = 0; i < N; ++i) {
    auxMatrix[i] = orderOfRows[i];
}


void allocate2dMemory() {

int i = 0;
sourceMatrix = (int**)malloc(N * sizeof(int *));

if(sourceMatrix == NULL) {
    fprintf(stderr, "out of memory\n");
    exit(2);
}

for(i = 0; i < N; i++) {
    sourceMatrix[i] = (int*)malloc(N * sizeof(int));
    if(sourceMatrix[i] == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(2);
    }
}

auxMatrix = (int**)malloc(N * sizeof(int *));

if(auxMatrix == NULL) {
    fprintf(stderr, "out of memory\n");
    exit(2);
}

for(i = 0; i < N; i++) {
    auxMatrix[i] = (int*)malloc(N * sizeof(int));
    if(auxMatrix[i] == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(2);
    }
}

 orderOfRows = (int**)malloc(N * sizeof(int *));

if(orderOfRows == NULL) {
    fprintf(stderr, "out of memory\n");
    exit(2);
}

for(i = 0; i < N; i++) {
    orderOfRows[i] = (int*)malloc(N * sizeof(int));
    if(orderOfRows[i] == NULL) {
        fprintf(stderr, "out of memory\n");
        exit(2);
    }
}

}
}

I will spend 2*N(copy pointers and then recover) operations instead of N*N. And I have another question: how I can do the permutation of columns using this idea? If it isn't possible how can I do the permutation of columns but not to copy all elements of the matrix? The programming language is only C.

Upvotes: 0

Views: 1724

Answers (2)

Igor
Igor

Reputation: 27278

Instead of 

orderOfRows[i] = &auxMatrix[computation[i]];

you should have

for (int j = 0; j < N; ++j)
{
    orderOfRows[i][j] = auxMatrix[computation[i]][j];
}

And one more thing:

if you havecomputation[1] = 6, it means that by doing auxMatrix[computation[i]] you try to access auxMatrix[6], which you can't do because auxMatrix's size is 6x6.

Upvotes: 1

Vaughn Cato
Vaughn Cato

Reputation: 64308

If you want to be able to swap both rows and columns without copying, you are going to need to have two auxiliary indices:

int *row_index;
int *col_index;

and access the elements of your matrix using these:

element = matrix[row_index[row]][col_index[col]];

To swap a row or column, you simply swap the corresponding elements of row_index or col_index.

Upvotes: 1

Related Questions