生成所有成对排列，不包括单个元素的排列。

Question

我想生成所有有序对（a，b）的排列，其中a！= b，a，b是集合S的元素（假设S：= {1..k}），但是要排除S中个别元素的排列。

例如，令k = 2，则可能的有序对为(1,2)，(2,1), 共有2个可能的顺序：

- (1,2)，(2,1) - (2,1)，(1,2)

但这些实际上是在{1->2，2->1}置换映射下的重复。

当k = 3时，将有6个可能的有序对，给出6!个序列（包括重复项）。但是，只有3！= k种可能的排列，需要的唯一序列数量为5！，并且可以通过仅考虑以对(1,2)开头的序列来轻松生成。

通常情况下，将有k *（k-1）个对，给出[k *（k-1）]!个序列（包括重复项），并且将有k！个排列，因此最终会得到[k *（k-1）]！/ k！个序列。

我只打算使用小的k值，但我想知道是否有任何好的方法来生成这些序列。我相当确定这是过滤唯一序列[允许重复元素]的特定情况，受到这些序列中可能元素的置换的影响，但也许在我寻找的内容中有一些特殊之处，比暴力生成所有可能序列然后过滤更容易。

- Hao Ye

---

从我的理解来看，他已经尝试创建所有的排列组合并且丢弃冗余的记录。但是这需要相当大的开销——创建最终不需要的记录。他正在寻找一种直接计算所需结果而无需此开销的方法。 - amit

@amit 你是对的，OP只想消除额外开销，但如果他能提出一些消除开销的方法，那么效果会更好。所以我们可以考虑他的方法，如果他采取正确的方法，我们将助他实现他的目标。同时很抱歉我之前不必要地回应了OP。下次我会记住这一点，并且已经删除了我的先前评论。再次感谢Amit。 - Jayesh Bhoi

Answer 1

请看回溯算法：

请查看http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html。

生成排列是一个NPC问题，因此所有解决方案都将具有指数复杂度。

- Ilie NEACSU

---

(1) NP问题也是可以在多项式时间内解决的问题。您可能指的是NP完全问题。 (2) 这不是NP完全问题，因为输出大小是指数级别的，所以即使P=NP，也没有多项式解决方案来解决这个问题。 - amit

此外，OP已经描述了一种使用排列的方法来完成它，但是希望避免生成太多排列并且废弃其中一个的开销。 - amit

枚举算法通常根据它们产生每个输出所需的时间来判断。对于彼得的算法，这个时间受k的多项式限制。 - David Eisenstat

Answer 2

我认为你可以扩展你的方法，只生成以(1,2)开头的序列，改为只生成这样的序列：如果逐个考虑每个数字，则该数字要么与先前的数字匹配，要么是下一个未见过的数字。

因此，像(1,2)(2,1)和(1,2)(3,4)这样的序列是允许的，但(1,2)(4,5)不行，因为4违反了规则（在这个阶段，3是下一个未见过的数字）。

有了这个条件，你可以通过递归地选择每一对来生成所有的组合，其中每一对都必须是新的，并满足这些规则。

例如，对于k=3。

(1,2) Only option for level 1
(1,2) can be followed by (2,1) or (1,3) or (2,3) or (3,1) or (3,2)
(1,2)(2,1) can be followed by (3,1) or (3,2) or (1,3) or (2,3)
(1,2)(2,1)(3,1) can be followed by...

- Peter de Rivaz

---

这是实现的方法。我们可以使用麦凯的框架来证明。该算法使用词典序最小作为其规范标记，构建此标记的隐式算法很简单：将第j个不同出现的元素映射到j。由于标记算法是在线的，因此下/上对象的处理非常简单。 - David Eisenstat