arrays - 下一个独轮车排列

Question

我想得到nextPermutation刚刚的one cycle。我熟悉这个nextPermutation函数，但这也会产生不止一个循环的排列。我不知道如何修改这个函数来创建nextUnicyclePermution

长度为 4 的 unicycle 排列：

2341 -> 2413 -> 3142 -> 3421 -> 4123 -> 4312

标签： arraysmathpermutationcombinatoricscycle

Answer 1

这是生成所有单环排列的初步想法。

在循环表示法中，每个单环置换由来自原始数组的元素的单个循环组成（例如（1 2 3 4）或（4 1 3 2））。给定一个包含 n 个元素的数组的任何单环排列，有 n 种不同的方法可以将该排列写成一个简单的循环。例如，单环置换 (1 2 3 4) 可以写成 (1 2 3 4)，或 (2 3 4 1)，或 (3 4 1 2)，或 (4 1 2 3)。我们将通过强制数组的第一个元素出现在循环符号的前面来选择一种写出排列的规范方式。

一旦我们将那个元素固定到位，我们就可以通过简单地枚举循环符号中剩余元素的所有排列来枚举所有单环排列。例如，这是四个元素的所有单环排列：

• (1 2 3 4) ↠ [4, 1, 2, 3]
• (1 2 4 3) ↠ [3, 1, 4, 2]
• (1 3 2 4) ↠ [4, 3, 1, 2]
• (1 3 4 2) ↠ [2, 4, 1, 3]
• (1 4 2 3) ↠ [3, 4, 2, 1]
• (1 4 3 2) ↠ [2, 3, 4, 1]

一般算法如下：

• 计算当前排列的循环符号。
• 旋转该循环符号以将第一个元素放入第一个槽中。
• 使用标准的下一个置换算法将循环符号的最后 n-1 个元素推进到下一个置换。
• 重新排序元素以匹配该循环排序。

可能有一种更快的方法来枚举它们（例如，在排列之间完成 O(1) 工作），并且可能有一种方法可以按字典顺序生成它们。但这有希望提供一个可以使用的起始算法！