有没有掉期，将产生所有可能的排列顺序？ [英] Is there a sequence of swaps that would generate all possible permutations?
问题描述
您给出的数字 1，2，...，N 的名单 - ！有 n的序列-1 交换的操作将产生所有 N！列表排列，其中掉期（I，J）交换在细胞元素我和Ĵ？那么一般情况下，当输入列表未排序开始与和/或有列表中重复？
You are given a list of numbers 1, 2, ... ,n - is there a sequence of n!-1 swap operations that would generate all n! permutations of the list where swap (i, j) swaps elements at cell i and j? What about the general case when the input list is not sorted to start with and/or there are repetitions in the list?
上下文：我解决一个问题，即数组的得分是很容易计算出，如果你已经知道分数，如果2个元素进行交换，我想蛮力（使用C ++ next_permutation（ ））的所有可能的排列。
Context: I am solving a problem where the "score" of an array is easy to calculate if you already know the score if 2 elements are swapped and I want to brute force (using C++ next_permutation()) all possible permutations.
推荐答案
当然，和它被称为17世纪的钟铃声。因此，如何是，对于有些组合的历史？
Sure, and it was known to 17th century bell-ringers. So how's that for a bit of combinatorial history?
请参阅的豪斯生猪蹄算法或咨询当地的变化振铃组。
See the Steinhaus Johnson Trotter algorithm or consult your local change-ringing group.
我做了一些调查，对您的问题，也就是是否有可能与重复的元素做到这一点的第二部分。答案，我相信，是是的，但不是那么容易。此外，它是不可能重排的列表，包括与刚刚相邻互换重复元素，如可以很容易地看到该组 {0，0，1，1} 。然而，也可以只用单一的互换。
I did a bit of research on the second part of your question, which is whether it is possible to do this with repeated elements. The answer, I believe, is "yes, but not so easily". Furthermore, it is not possible to permute a list with repeated elements with just adjacent swaps, as can be easily seen for the set {0, 0, 1, 1}. However, it is possible with just single swaps.
的基本方法是使用基本改变振铃算法，但对相同的元件，而不是对单个元素组。对于一组 K 相同的元素，你需要能够算法的名单组合0 NK 1 K （其中，n是基本集的总大小）。许多这样的算法存在，但我无法找到任何这是非常简单的;最简单的一个是（粗略地讲）的方向分配到整体组，并且也是方向到每个 1 （以类似的方式向希蒙即使算法）。当移动组离开后，最左边的元素来回扫描;每次改变方向时，下移动构件向右步骤之一;等，这最终将整个组从列表的左手侧，在这之后其总体方向被翻转的右侧并前进回到原来的配置，现在用最右边的元件领先扫描。
The basic approach is to use the basic change-ringing algorithm, but on groups of identical elements instead of on single elements. For a group of k identical elements, you need to be able an algorithm for combinations of the list 0n-k1k (where n is the total size of the base set). A number of such algorithms exist, but I can't find any which are really simple; the simplest one is (roughly speaking) to assign a direction to the overall group, and also a direction to each 1 (in a similar fashion to the Shimon Even algorithm). When moving the group left, the leftmost element sweeps back and forth; every time it changes direction, the next mobile element to the right steps one; etc. This eventually moves the entire group from the right-hand side of the list to the left-hand side, after which its overall direction is flipped and it proceeds back to the original configuration, now with the rightmost element leading the sweeps.
由于方向反转数目可能是即使在这种情况下，上述的算法可能不描绘出一个排列周期，但我相信，有可能产生使用更老练算法循环。实际上，你正在寻找一个汉密尔顿的周期从每个排列引起可能的单交换的图表 - permutehedron的一个变种 - 但是，尽管哈密尔顿周期确实存在，他们不那么容易找到，因为图都是相当大的。
Since the number of direction reversals might be even in this case, the above algorithm might not trace out a permutation cycle, but I believe that it is possible to produce a cycle using a more sophisticate algorithm. In effect, you're looking for a hamiltonian cycle in the graph induced by possible single swaps from each permutation -- a variant of the permutehedron -- but, while hamiltonian cycles do exist, they are not so easy to find since the graphs are quite large.
这篇关于有没有掉期，将产生所有可能的排列顺序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
