Linear index for a diagonal run of an upper triangular matrix-CodePudding

Given a NxN matrix, I would like to linearly index into its upper right triangle, following a diagonal by diagonal pattern, starting after the main diagonal.

For example, given a 4x4 matrix

X 0 3 5
X X 1 4
X X X 2
X X X X

I'm looking for a non recursive (closed form) function mapping linear indices from 0 to 5 to (x,y) achieving

f(0) = (0, 1)
f(1) = (1, 2)
f(2) = (2, 3)
f(3) = (0, 2)
f(4) = (1, 3)
f(5) = (0, 3)

Related for row by row runs:

CodePudding user response：

I created a custom method for the array and value you gave.

int a[4][4] ={{-1, 0, 3, 5}, {-1, -1, 1, 4}, {-1, -1, -1, 2}, {-1, -1, -1, -1}};

The code is exactly like this. You give the array And whatever you give to the second value in the Func method, the indexes of the value in the upper diagonal will reach you.

#include <iostream>

using namespace std;

int b[2] ={-1,-1};

int Func(int a[4][4],int n)
{
    
    for(int i =0;i<4;i  )
    {
        for(int j=0;j<4;j  )
        {
            if(a[i][j]==n)
            {
                if(i<j)
                {
                    b[0]=i;
                    b[1]=j;
                    return 0;
                }
            }
        }
    }
}
int main()
{
    int a[4][4] ={{-1, 0, 3, 5}, {-1, -1, 1, 4}, {-1, -1, -1, 2}, {-1, -1, -1, -1}};
    Func(a,5);
    for(int i=0;i<2;i  )
    {
        cout<<b[i]<<" ";
    }
    return 0;
}

thank you USEFUL for feedback if it worked for you

CodePudding user response：

Maybe someone can come up with a math formula that doesn't require a loop, but until then I've come up with a O(N) solution:

#include <utility>

constexpr std::pair<int, int> f(int n, int idx)
{
    int group_size = n - 1;
    int rest = idx   1;

    while (rest > group_size)
    {
        rest = rest - group_size;
        --group_size;
    }
    return {(rest - 1) % group_size,
            n - group_size    (rest - 1) % group_size};
}

/* 3x3
X 0 2
X X 1
X X X
*/
static_assert(f(3, 0) == std::pair{0, 1});
static_assert(f(3, 1) == std::pair{1, 2});
static_assert(f(3, 2) == std::pair{0, 2});

// 4x4
static_assert(f(4, 0) == std::pair{0, 1});
static_assert(f(4, 1) == std::pair{1, 2});
static_assert(f(4, 2) == std::pair{2, 3});
static_assert(f(4, 3) == std::pair{0, 2});
static_assert(f(4, 4) == std::pair{1, 3});
static_assert(f(4, 5) == std::pair{0, 3});

/* 5x5
X 0 4 7 9
X X 1 5 8
X X X 2 6
X X X X 3
X X X X X
*/
static_assert(f(5, 0) == std::pair{0, 1});
static_assert(f(5, 1) == std::pair{1, 2});
static_assert(f(5, 2) == std::pair{2, 3});
static_assert(f(5, 3) == std::pair{3, 4});
static_assert(f(5, 4) == std::pair{0, 2});
static_assert(f(5, 5) == std::pair{1, 3});
static_assert(f(5, 6) == std::pair{2, 4});
static_assert(f(5, 7) == std::pair{0, 3});
static_assert(f(5, 8) == std::pair{1, 4});
static_assert(f(5, 9) == std::pair{0, 4});