下一个独轮车排列
Next unicycle Permutation
我想要 nextPermutation，它只有 one cycle。我熟悉 nextPermutation 函数，但这也会产生不止一个循环的排列。我不知道如何修改这个函数来创建 nextUnicyclePermution
长度为 4 的独轮车排列：
2341 -> 2413 -> 3142 -> 3421 -> 4123 -> 4312
这是生成所有单环排列的初步想法。
每个单环排列，以循环表示法，由原始数组元素的单个循环组成（例如（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) 的工作量）并且可能有一种方法可以按字典顺序生成它们。但这有望提供一个可以使用的起始算法！
我想要 nextPermutation，它只有 one cycle。我熟悉 nextPermutation 函数，但这也会产生不止一个循环的排列。我不知道如何修改这个函数来创建 nextUnicyclePermution
长度为 4 的独轮车排列：
2341 -> 2413 -> 3142 -> 3421 -> 4123 -> 4312
这是生成所有单环排列的初步想法。
每个单环排列，以循环表示法，由原始数组元素的单个循环组成（例如（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) 的工作量）并且可能有一种方法可以按字典顺序生成它们。但这有望提供一个可以使用的起始算法！