是否存在时间复杂度低于O(n!)的多项式时间算法求解特定二元组合列表生成问题

首先可以直接给出明确结论：存在远低于O(n!)的多项式时间算法解决该问题，且该问题不存在尚未找到多项式解法的疑问。

问题本质 #

你描述的问题等价于构造偶数阶完全无向图Kₙ的1-因子分解：你要求的每n/2个二元组构成的分组，本质就是Kₙ的一个完美匹配——即包含恰好n/2条互不共享顶点的边，刚好覆盖全部n个顶点；而1-因子分解就是把Kₙ的所有边恰好拆分为互不重叠的完美匹配，刚好对应你要求的全部二元组合的列表输出。

时间复杂度说明 #

该问题的最优算法时间复杂度为O(n²)，和输出结果的规模完全匹配：

• n个元素的总二元组合数为n(n-1)/2，也就是输出的总长度本身就是O(n²)量级，算法时间开销不可能超过输出本身的规模，远低于O(n!)。
• 目前已有非常成熟的循环构造法可以实现O(n²)的时间复杂度，构造逻辑非常简单：
  • 把编号为0的元素固定位置
  • 剩余n-1个元素按顺序排成环形
  • 每一轮取0和环的顶端元素配对，剩下的元素按环上对称位置两两配对，得到一个符合要求的分组
  • 将环旋转一个位置后重复上述操作，直到生成全部n-1个分组即可
    你给出的n=4、n=8的示例输出，完全符合该构造方法的结果。

关于NP类问题的说明 #

该问题不属于尚未找到多项式时间解法的NP类问题：

• NP类的定义针对判定类问题，该问题本身是构造类问题；就算对应到相关的判定场景（比如判断给定的二元组列表是否符合分组规则、判断任意无向图是否存在完美匹配），也都有成熟的多项式时间解法。
• 偶数阶完全图的1-因子分解的存在性早已被严格证明，构造方法也已经非常成熟，没有“是否存在多项式解法”的争议。

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