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:
Thanks to @loopy-walt's observation, we have an answer! Using the result from Linear index upper triangular matrix, a transformation of the result
(i, j) |-> (j-i-1, j)
Gives the expected outcome.
Here is a C++ implementation.
#include<tuple>
#include<cmath>
// Linear indexing of the upper triangle, row by row
std::tuple<size_t, size_t> k2ij(size_t n, size_t k){
size_t i = n - 2 - (size_t)std::floor(std::sqrt(4*n*(n-1) - (8*k) -7)/2.0 - 0.5);
size_t j = k + i + 1 - n*(n-1)/2 + (n-i)*((n-i)-1)/2;
return {i,j};
}
// Linear indexing of the upper triangle, diagonal by diagonal
std::tuple<size_t, size_t> d2ij(size_t n, size_t d){
const auto [i, j] = k2ij(n, d);
return {j-i-1, j}; // Conversion from row by row to diag by diag
}
#include<iostream>
#include<set>
int main(int argc, char** argv) {
size_t n = 4;
size_t top = n*(n-1)/2;
for(size_t d=0; d<top; ++d){
const auto [i,j] = d2ij(n, d);
std::cout << "d2ij(" << n << ", " << d << ") = (" << i << ", " << j << ")" << std::endl;
}
return 0;
}
Producing
d2ij(4, 0) = (0, 1)
d2ij(4, 1) = (1, 2)
d2ij(4, 2) = (2, 3)
d2ij(4, 3) = (0, 2)
d2ij(4, 4) = (1, 3)
d2ij(4, 5) = (0, 3)
Note: if someone wishes the form f(d) instead, a lambda can be used to capture the dimension 'n'
auto f = [n](size_t d){return d2ij(n, d);};
const auto [i,j] = f(5);
Thanks to everybody that took the time to read and help!