上三角矩阵的对角线运行的线性索引

Question

给定一个 NxN 矩阵，我想线性索引到它的右上三角形，按照对角线模式，从主对角线之后开始。

例如，给定一个 4x4 矩阵

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

我正在寻找一个非递归（封闭形式）函数，将线性索引从 0 到 5 映射到 (x,y) 实现

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

与逐行运行相关：

Linear index upper triangular matrix
algorithm for index numbers of triangular matrix coefficients

Answer 1

我为您提供的数组和值创建了自定义方法。

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

代码就是这样。你给数组无论你给 Func 方法中的第二个值，上对角线中的值的索引都会到达你。

#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;
}

感谢您USEFUL 如果它对您有用，请提供反馈

Answer 2

也许有人可以想出一个不需要循环的数学公式，但在那之前我想出了一个 O(N) 解决方案：

#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});

Answer 3

感谢@loopy-walt 的观察，我们有了答案！使用 Linear index upper triangular matrix 的结果，对结果

进行转换

(i, j) |-> (j-i-1, j)

给出了预期的结果。

这是一个 C++ 实现。

#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;
}

制作中

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)

注意：如果有人希望采用 f(d) 形式，可以使用 lambda 来捕获维度 'n'

auto f = [n](size_t d){return d2ij(n, d);};
const auto [i,j] = f(5);

感谢所有花时间阅读和帮助的人！

Answer 4

所以你想要以下函数的反函数

包含对角线

的n×n上三角矩阵的元素[i,j]的从零开始的索引形式

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

i=0..4, j=0..4, index=
|  0 |  1 |  2 |  3 |  4 |
|  X |  5 |  6 |  7 |  8 |
|  X |  X |  9 | 10 | 11 |
|  X |  X |  X | 12 | 13 |
|  X |  X |  X |  X | 14 |

我能想到的最简单的算法是遍历所有行 i 并查看是否存在与列 j 匹配的内容，例如：

i <= j
j>=0
j<n

这是给定 index 和 n

的示例代码

for(i=0; i<n; i++)
{
    j = index - i*n + i*(i+1)/2
    if( j>=0 && j<n && j>= i)
    {
       break;
    }
}

n=7 和 [i,j]=[1,5] 的示例生成 index=11。现在这个索引的坐标是

`i`	`j`	`i<=j && j>=0 && j<7`
`0`	`11`
`1`	`5`	valid
`2`	`0`
`3`	`-4`
`4`	`-7`
`5`	`-9`
`6`	`-10`

如果你想要严格的上三角元素，不包括对角线那么

元素 [i,j] 的从零开始的索引形式对于 n×n 不包括对角线的上三角矩阵

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

i=0..3, j=0..4, index=
|  X |  0 |  1 |  2 |  3 |
|  X |  X |  4 |  5 |  6 |
|  X |  X |  X |  7 |  8 |
|  X |  X |  X |  X |  9 |
|  X |  X |  X |  X |  X |

现在的算法是循环所有行 i 并查看是否存在与列 j 的匹配，使得：

i < j
j>0
j<n

这是给定 index 和 n

的示例代码

for(i=0; i<n; i++)
{
    j = index - i*n + i*(i+3)/2 + 1
    if( j>0 && j<n && j>i)
    {
       break;
    }
}

n=7 和 [i,j]=[1,5] 的示例生成 index=9。现在这个索引的坐标是

`i`	`j`	`i<j && j>0 && j<7`
`0`	`10`
`1`	`5`	valid
`2`	`1`
`3`	`-2`
`4`	`-4`
`5`	`-5`

上三角矩阵的对角线运行的线性索引

Linear index for a diagonal run of an upper triangular matrix

c++

arrays

numpy

linear-algebra

triangular

上三角矩阵的对角线 运行 的线性索引

Linear index for a diagonal run of an upper triangular matrix

c++

arrays

numpy

linear-algebra

triangular

上三角矩阵的对角线运行的线性索引