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

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 值，但想知道是否有生成这些序列的好方法。我相当确定这是过滤掉唯一序列 [允许重复元素] 的特定情况，受这些序列中可能元素的排列影响，但也许我正在寻找的东西有一些特别之处，这比粗暴的更容易 -强制生成所有可能序列然后过滤的方法。

Answer 1

看看回溯算法:

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

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