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