pat*_*rit 7 algorithm permutation
您将获得一个数字列表1, 2, ... ,n- 是否有一系列n!-1 swap操作可以生成n!列表的所有排列,其中swap (i, j)单元格中的交换元素i和j？当输入列表没有排序开始和/或列表中有重复时,一般情况如何？
上下文:我正在解决一个问题,如果你已经知道了2个元素被交换并且我想要使用C++(使用C++ next_permutation())所有可能的排列,那么数组的"得分"很容易计算.
ric*_*ici 15
当然,17世纪的铃声已经为人所知.那么对于一些组合历史来说怎么样呢？
请参阅Steinhaus Johnson Trotter算法或咨询当地的变革组.
我对你问题的第二部分进行了一些研究,即是否可以用重复的元素来做这件事.我相信答案是"是的,但不是那么容易".此外,不可能使用仅具有相邻交换的重复元素来置换列表,这对于该集合是容易看到的{0, 0, 1, 1}.但是,只需单次交换就可以实现.
基本方法是使用基本的变换振铃算法,但是使用相同元素的组而不是单个元素.对于一组k相同的元素,您需要能够使用列表0 n-k 1 k(其中n是基集的总大小)的组合的算法.存在许多这样的算法,但我找不到任何真正简单的算法; 最简单的一个是(粗略地说)为整个组分配方向,以及每个组的方向1(以与Shimon Even算法类似的方式).向左移动组时,最左边的元素来回扫描; 每次改变方向时,右边的下一个移动元素步骤一; 这最终将整个组从列表的右侧移动到左侧,之后其整个方向被翻转并且它返回到原始配置,现在最右边的元素引导扫描.
由于在这种情况下方向反转的数量可能是偶数,因此上述算法可能无法追踪置换周期,但我相信可以使用更复杂的算法产生周期.实际上,你正在寻找图中的哈密顿循环,这是由每个排列可能的单个交换引起的 - 变换器的变体 - 但是,虽然存在哈密顿循环,但它们并不那么容易找到,因为图表是非常大.