基于std::next_permutation排列构建邻接交换无向图的高效方法问询

你要实现的这个图本质是n元对称群的凯莱图，生成元为所有相邻位置交换置换，完全不需要逐对遍历所有排列判断连边，单节点邻接枚举的时间复杂度仅为O(n)，整体建图复杂度为O(n·n!)，效率远高于逐对判断的O((n!)²)。

具体实现逻辑 #

1. 预建立双向映射（可选，按需实现） #

你需要先实现两个转换函数，不需要提前预存所有排列也能正常工作：

• 排列转节点编号：用**阶乘数位系统（莱布尼茨编码）**计算排列的字典序排名，和你用next_permutation生成的顺序完全一致，基础实现时间复杂度O(n²)，优化后可到O(n log n)。
• 节点编号转排列：同样用阶乘数位系统，给定排名直接还原出对应排列，时间复杂度O(n²)。

2. 单节点邻接枚举方法 #

给定任意排列P（长度为n），它的所有邻接排列生成规则非常直接：

• 遍历所有相邻索引对 k ∈ [0, n-2]
• 每次交换P[k]和P[k+1]，得到新排列P_k
• 所有P_k就是当前节点的全部邻接点，每个排列最多有n-1个邻接节点

举你给出的示例验证：排列1对应[0,1,2,3]，遍历k=0、1、2交换后得到[1,0,2,3]、[0,2,1,3]、[0,1,3,2]，正好对应你列表里的排列7、3、2，完全符合你的连边规则。

3. 效率对比 #

以n=4为例：

• 逐对判断需要比对24*23/2=276次，每次比对需要O(n)时间，总操作量约1100次
• 本方法仅需要处理24个节点，每个节点最多3次交换，总操作量不到100次
  n越大优势越明显，n=5时逐对判断需要7140次比对，本方法仅需要600次左右操作。

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