finding position in triangle matrix

I have symmetric matrix stored in column major way. But I am storing only lower part of matrix to save space.

so my matrix looks like this:

1
2 6 
3 7 10
4 8 11 13
5 9 12 14 15

I have to write code to find position of element in this matrix depending on index i(row),j(col) of that matrix.

I have written sth like this:

pos = (n*j) - j*j/2 + (i - j);

pos - position of my element in matrix - a[pos] n - size of matrix

Unfortunately It doesn't find good position always. I write program to test it and it prints:

1
2 6 
3 7  11
4 8  12 14
5 9  13 15 17
6 10 14 16 18 18

I know it happens like that because when we divide j*j/2 we get int/int. But I have no idea what to do to make it work 开发者_如何学Ccorrectly.

please help!

Let's examine the calculation one column at a time, assuming:

i <= j
1 <= i <= n
1 <= j <= n:

then:

i=1, pos=j
i=2, pos=n+j-1
i=3, pos=n+n-1+j-2
i=4, pos=n+n-1+n-2+j-3
etc...

we can deduce from this a general formula:

p=n*(i-1)+j-(i-1)*i/2

which can be tested using a simple bit a C#:

using System;
using System.IO;

namespace Stream
{
  class Program
  {
    static void Main (string [] args)
    {
      for (int j = 1 ; j <= 5 ; ++j)
      {
        for (int i = 1 ; i <= 5 ; ++i)
        {
          Console.Write (GetIndex (i, j).ToString ("00 "));
        }
        Console.WriteLine ("");
      }
    }

    static int GetIndex (int in_i, int in_j)
    {
      int
        n = 5,
        i = Math.Min (in_i, in_j),
        j = Math.Max (in_i, in_j);


      return n * (i - 1) + j - (i - 1) * i / 2;
    }
  }
}

First of all, it would be much more simple to store the matrix by line (first line at the beginning of the array) to compute the indexes.

Your formula seems wrong, I would say it is (for j > 0):

               n + (n-1) + ... + (n-j+1)              + (i - j)

  =      (( sum [0 <= k <= j-1]  (n-j+1) + k ))       + (i - j)

  =    (n-j+1) * j   +  (( sum [0 <= k <= j-1]  k ))  + (i - j)

  =    (n-j+1) * j   +       (j * (j+1)) / 2          + (i - j)

if your indices (i,j) start at 0 and you store the first column (with n elements) at the first position in the array.

Edit: modified for indexes starting at 0.

#include <iostream>
using namespace std;

int main()
{
    int i=0,k=1,j=0;
    int a[5][5];
    int n=0;

        for (j=0; j<5;j++)
        {
           for (i=n; i<5;i++)
            {
                a[i][j]=k++;
                cout<<i<<" "<<j<<" "<<(a[i][j])<<'\n';
            }
          n++;
        }

    return 0;
}