已知两个元素索引，如何计算其在两两关系列表中的位置

问题背景 #

我们有一个元素集合，所有满足i<j的两两元素对按照「i从小到大排序，i相同则j从小到大排序」的规则生成列表，生成逻辑的示例代码如下：

k=0; for (i=0;i<5;i++) {for (j=i+1;j<5;j++) { console.log(k++, ': ', i, '-', j) } }
// 输出结果
0 :  0 - 1
1 :  0 - 2
2 :  0 - 3
3 :  0 - 4
4 :  1 - 2
5 :  1 - 3
6 :  1 - 4
7 :  2 - 3
8 :  2 - 4
9 :  3 - 4

需要解决的问题是：给定任意大小的元素集合（总元素数记为n，元素索引范围为0~n-1），以及满足i<j的两个元素索引，快速计算该关联对在上述列表中的位置序号（从0开始计数）。例如输入i=1、j=2时期望输出4。

计算方法 #

计算公式 #

位置序号k的计算逻辑分为两部分求和：

1. 所有第一个索引小于i的关联对总数：这部分是首项为n-1、末项为n-i的等差数列求和，结果为 i*(2n - i - 1) / 2
2. 第一个索引等于i，且第二个索引小于j的关联对总数：结果为 j - i - 1
   最终合并公式为：

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

验证示例 #

以n=5的场景验证：

• 输入i=1、j=2：k = 1*(10 - 1 -1)/2 + 2 -1 -1 = 4 + 0 =4，和预期一致
• 输入i=2、j=4：k =2*(10 -2 -1)/2 +4-2-1 =7 +1=8，和示例输出一致
• 输入i=3、j=4：k=3*(10-3-1)/2 +4-3-1= 9 + 0 =9，和示例输出一致

内容的提问来源于stack exchange，提问作者Pedro L.