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

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 行和第 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

Answer 2

这是 i*(i+1)/2 + j。欢迎您检查