<分区>
给你一个数字列表 1, 2, ... ,n - 是否有 n!-1 swap 的序列> 将生成列表的所有 n! 排列的操作，其中 swap (i, j) 交换单元格 i 和 j 中的元素？当输入列表未按开头排序和/或列表中有重复时，一般情况如何？
上下文:我正在解决一个问题，如果您已经知道交换 2 个元素的分数并且我想蛮力计算数组的“分数”很容易(使用 C++ next_permutation()) 所有可能的排列。
<分区>
给你一个数字列表 1, 2, ... ,n - 是否有 n!-1 swap 的序列> 将生成列表的所有 n! 排列的操作，其中 swap (i, j) 交换单元格 i 和 j 中的元素？当输入列表未按开头排序和/或列表中有重复时，一般情况如何？
上下文:我正在解决一个问题，如果您已经知道交换 2 个元素的分数并且我想蛮力计算数组的“分数”很容易(使用 C++ next_permutation()) 所有可能的排列。
最佳答案
当然，17 世纪的敲钟人就知道了。那么对于一些组合历史来说怎么样？
参见 the Steinhaus Johnson Trotter algorithm或咨询您本地的变更电话小组。
我对你问题的第二部分做了一些研究，即是否可以用重复的元素来做到这一点。我相信答案是“是的，但没那么容易”。此外，不可能通过仅相邻交换来置换具有重复元素的列表，对于集合 {0, 0, 1, 1} 可以很容易地看出这一点。但是，仅进行一次交换是可能的。
基本方法是使用基本的更改振铃算法，但是是在一组相同的元素上而不是在单个元素上。对于一组 k 相同的元素，您需要能够对列表 0n-k1k 的组合进行算法(其中 n 是基集的总大小)。存在许多这样的算法，但我找不到任何真正简单的算法；最简单的方法是(粗略地说)为整个组分配一个方向，也为每个 1 分配一个方向(以类似于 Shimon Even 算法的方式)。向左移动组时，最左边的元素来回扫过；每次它改变方向时，右边的下一个移动元素都会移动一个；等等。这最终将整个组从列表的右侧移动到左侧，之后它的整体方向被翻转并返回到原始配置，现在最右边的元素领导扫描。
由于在这种情况下方向反转的次数可能是偶数，因此上述算法可能无法追踪出排列循环，但我相信可以使用更复杂的算法来生成循环。实际上，您正在寻找由每个排列可能的单次交换引起的哈密顿循环——置换面体的变体——但是，虽然哈密顿循环确实存在，但它们并不容易找到，因为图形是相当大。
关于algorithm - 是否存在可以生成所有可能排列的交换序列？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13205573/