如何实现无重复无序索引对到组合索引范围的双射函数

完全可以实现这个需求——因为n个元素的无序双元素组合总数正好是n*(n-1)/2，和目标值域0~C(n,2)-1的基数完全一致，必然存在一一对应的双射关系。下面给出具体的构造方法：

核心思路 #

由于组合是无序的，我们先将任意索引对{i,j}转换为有序对(a,b)，其中a = min(i,j)，b = max(i,j)（每个无序对唯一对应一个a < b的有序对）。随后按照a从小到大、b从a+1到n-1的顺序为每个组合分配连续索引，即可得到符合要求的双射。

正向映射（索引对→组合索引） #

对于a < b的有序对，对应的组合索引计算公式为：

f(a,b) = a*(2n - a - 1) // 2 + (b - a - 1)

• a*(2n - a -1)//2：计算所有a' < a的组合总数（即(n-1)+(n-2)+...+(n-a)的累加和）。
• (b - a -1)：当前a对应的组合中，b相对于a+1的偏移量（比如a=0时，b=1偏移0，b=2偏移1）。

如果输入的i,j是任意顺序（如i > j），只需先取min和max再代入公式即可。示例代码（Python）：

def pair_to_idx(i, j, n):
    a, b = sorted((i, j))
    return a * (2 * n - a - 1) // 2 + (b - a - 1)

反向映射（组合索引→索引对） #

为证明这是双射，可构造反向函数根据索引还原对应无序对：

1. 找到最大的a，使得前a组的组合总数不超过目标索引。
2. 计算索引在当前a组内的偏移量，得到b的值。

示例代码（Python）：

def idx_to_pair(idx, n):
    total = n * (n - 1) // 2
    if not 0 <= idx < total:
        raise ValueError("索引超出范围")
    
    a = 0
    # 定位对应的a值
    while (a + 1) * (2 * n - (a + 1) - 1) // 2 <= idx:
        a += 1
    # 计算偏移量得到b
    offset = idx - a * (2 * n - a - 1) // 2
    b = a + 1 + offset
    return (a, b)

验证示例 #

以n=4为例，所有组合的映射关系完全匹配：

• {0,1}→0；{0,2}→1；{0,3}→2
• {1,2}→3；{1,3}→4；{2,3}→5

该构造完全避开了i=j的情况，值域严格覆盖0~C(n,2)-1，完全满足你的需求。

内容的提问来源于stack exchange，提问作者rustacean