基于有效成对取值构造多索引合法组合的高效实现问题

假设存在n个索引，其所有两两组合的总数为n(n-1)/2，比如n=3时，索引(i,j,k)对应的两两组合为(i,j)、(i,k)、(j,k)。
已知每个两两组合的所有合法取值，要求生成的完整索引组合必须满足：所有对应的两两子组合都属于各自的合法取值集合。

给出合法两两组合如下：

(i,j) = (1,2), (1,3), (2,2)
(i,k) = (2,2), (1,2), (2,4)
(j,k) = (1,2), (4,3), (2,2)

符合要求的完整合法组合仅有2个：

(i,j,k) = (2,2,2)
(i,j,k) = (1,2,2)

当前可运行的实现代码如下：

import numpy as np

ij = np.array(([1,2], [1,3], [2,2]))
ik = np.array(([2,2], [1,2], [2,4]))
jk = np.array(([1,2], [4,3], [2,2]))

possibilities = []

possible_i = np.union1d(ij[:,0], ik[:,0])
possible_j = np.union1d(ij[:,1], jk[:,0])
possible_k = np.union1d(ik[:,1], jk[:,1])

for i in possible_i:
    for j in possible_j:

        if ([i,j] == ij).all(1).any():     
            for k in possible_k:
                if (([i,k] == ik).all(1).any() and
                    ([j,k] == jk).all(1).any()):
                    print(i,j,k)

该实现虽然兼容任意n的场景，但效率较低：会枚举大量无效的索引组合并重复校验，n值升高时性能下降非常明显。

• 提前构建哈希查询结构：将所有两两合法组合转换为哈希集合/字典，把原本逐行对比的O(m)查询复杂度（m为单组两两组合的合法值数量）降到O(1)。比如可以为每个左索引建立对应右索引的合法取值集合，后续直接查字典即可。
• 增量生成+提前剪枝：不要一开始就枚举所有维度的所有可能取值，而是从两两合法组合出发，递进生成更长的合法组合：比如n=3的场景下，直接遍历已经合法的(i,j)对，再基于每一组合法(i,j)找同时满足i、j约束的k值，完全避免无效的i、j枚举。如果n更大，就基于已生成的k元合法组合，筛选符合所有两两约束的第k+1位取值，每一步都提前剪枝，不会产生无效中间组合。
• 维度顺序优化：优先选择取值范围更小的维度作为起始生成维度，尽可能早地剪枝掉更多无效分支，减少后续遍历量。
• 向量化批量运算：如果使用numpy实现，可以用广播操作代替逐元素循环校验，一次性批量筛选合法值，进一步提升运行效率。

import numpy as np

ij = np.array(([1,2], [1,3], [2,2]))
ik = np.array(([2,2], [1,2], [2,4]))
jk = np.array(([1,2], [4,3], [2,2]))

# 预构建查询结构：O(1)校验合法组合
ij_set = set(map(tuple, ij))
ik_map = {}
for i, k in ik:
    ik_map.setdefault(i, set()).add(k)
jk_map = {}
for j, k in jk:
    jk_map.setdefault(j, set()).add(k)

result = []
# 仅遍历已合法的(i,j)组合，无无效枚举
for i, j in ij_set:
    # 直接取i、j允许的k值交集，无需逐个校验k
    valid_k = ik_map.get(i, set()) & jk_map.get(j, set())
    for k in valid_k:
        result.append((i,j,k))
        print(i,j,k)

该方案的时间复杂度和合法组合的总数量成正比，n值越高剪枝收益越明显，可轻松支撑更高n的场景。

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