ViktorG
ViktorG

Reputation: 515

Triangular matrix get() in one dimensional array

I want to save a triangular matrix in a 1 dim array (to minimize needed space, all zeros are left out) and create a function get() to find a specific entry from the original matrix.

For example:

Lets look at the following triangular matrix :

0 1 2 3 
0 0 4 5 
0 0 0 6 
0 0 0 0

I am saving this matrix like this:

double[] test = {1,2,3,4,5,6};

So all the zeros are left out.

I want to write a function that gives me a value of the original matrix:

get(3,4)

should give me 6

I am checking the input to see if its out of bound and if it is below or on the diagonal.

//Checking if input is valid 
        if (i <= n &&  j <= n && i >= 1 && j >= 1){
            if( j <= i ){
                return 0.0;
            }else {

            }
        }

This works.

How do I proceed though? I have trouble finding the equivalent matrix entry in my array.

Any help would be appreciated.

EDIT:

My whole code:

public class dreiecksmatrix {
    int n = 4;
    double[] a = {1,2,3,4,5,6};

    public double get( int i, int j){

        //Checking if input is valid 
        if (i <= n &&  j <= n && i >= 0 && j >= 0){
            if( j <= i ){
                return 0.0;
            }else {

            }
        }

        return 1.0;
    }

    public static void main(String [] args ){
        dreiecksmatrix test = new dreiecksmatrix();
        System.out.println(test.get(2,3));

    }
}

Upvotes: 2

Views: 1225

Answers (2)

Dzmitry Bahdanovich
Dzmitry Bahdanovich

Reputation: 1815

Here is the sample code calculating the value of top-triange. No corner cases check like i,j >= 1 yet, but it's easy to add them.

arr = [[0, 1, 2, 3, 4],
       [0, 0, 5, 6, 7],
       [0, 0, 0, 8, 9],
       [0, 0, 0, 0, 10],
       [0, 0, 0, 0, 0]];

flatArr = [1,2,3,4,5,6,7,8,9,10];

n = 5; // matrix size
i = 1; 
j = 3;

if (j <= i) {

    alert(0);

} else {
    pos = 0;
    // find an offset caused by first (i - 1) lines
    for (k = 1; k < i; k++) {
       pos += n - k;
    }

    // find an offset in line x
    pos += j - i;

    // array index start from 0 so decrement value
    pos = pos - 1;

    alert('flatArr[' + pos + '] = ' + flatArr[pos]);
}

Upvotes: 3

dmuir
dmuir

Reputation: 4431

If you were instead to store the matrix by columns, there is a simple formula for the index into test of the i,j'th matrix element.

In your example you would have

double[] test = {1,2,4,3,5,6};

If Col(i) is the index pf the start of column i then

  Col(2) = 0
  Col(3) = Col(2) + 1
..
  Col(n) = Col(n-1) + n-1

Hence

Col(j) = ((j-1)*(j-2))/2

The i,j matrix element is stored i further on from the start of column j, ie at Col(j)+i, so that you should add

  return test[ ((j-1)*(j-2))/2 + i];

to your code

There is an analogous formula if you must store by rows rather than columns. It's a wee bit messier. The idea is to first figure out, starting with the last non-zero row, where the ends of the rows are solved.

Upvotes: 3

Related Questions