algorithm - 如何按字典顺序枚举无序的整数对

Question

什么是算法(或更确切地说是公式)，对于每对整数 i 和 j 且 j >= i，给出一个整数 k = k(i,j) 使得

• k(0,0) = 0
• k(i,j2) = k(i,j1)+1 对于 j2 = j1 + 1
• k(i,0) = k(i-1,i-1) + 1 , i >= 1

持有？

换句话说，如果你用自然数从左到右逐行填充矩阵的左下部分，从0开始，你如何计算给定第i行索引的单元格的值和列索引 j <= i?

非常感谢!

Answer 1

Alleo 答案的证明:

首先写下你的第二个公式，从 j 到 1

k(i,j)= k(i,j-1) + 1
k(i,j-1) = k(i,j-2) + 1
...
k(i,1) = k(i,0) + 1

总结你得到的这些公式:

k(i,j) = k(i,0) + 1+1 ..+1 = k(i,0) + j  (1)

现在从你的第三个公式:

k(i,0) = k(i-1,i-1) + 1  

使用(1):

k(i-1,i-1) = k(i-1,0) + i-1 

然后

k(i,0) = k(i-1,0) + i

那么因为 k(0,0) = 0

k(i,0) = sum(p for p=0 to i) = i*(i+1)/2 (2)

然后

(1) & (2) => k(i,j) = i*(i+1)/2 + j