掉期在排列号码 [英] Number of swaps in a permutation
问题描述
是否有一个有效的算法（高效大O符号表示）寻找掉期号码转换转置P到身份置换吗？的互换不必是对相邻元件，但在任何元素
Is there an efficient algorithm (efficient in terms of big O notation) to find number of swaps to convert a permutation P into identity permutation I? The swaps do not need to be on adjacent elements, but on any elements.
因此，例如：
I = {0, 1, 2, 3, 4, 5}, number of swaps is 0
P = {0, 1, 5, 3, 4, 2}, number of swaps is 1 (2 and 5)
P = {4, 1, 3, 5, 0, 2}, number of swaps is 3 (2 with 5, 3 with 5, 4 with 0)
一个想法是写一个这样的算法：
One idea is to write an algorithm like this:
int count = 0;
for(int i = 0; i < n; ++ i) {
for(; P[i] != i; ++ count) { // could be permuted multiple times
std::swap(P[P[i]], P[i]);
// look where the number at hand should be
}
}
但它不是很清楚，我是否实际上是保证终止，或者是否发现掉了正确的号码。它适用于上面的例子。我试图生成5和12号的所有排列，它总是终止这些。
But it is not very clear to me whether that is actually guaranteed to terminate or whether it finds a correct number of swaps. It works on the examples above. I tried generating all permutation on 5 and on 12 numbers and it always terminates on those.
这个问题出现在数值线性代数。一些矩阵分解使用枢转，从而有效地交换行与下一行的最大价值被操纵，以避免除小号码和提高数值稳定性。一些分解，如LU分解以后可以用于计算矩阵行列式，但分解的行列式的符号是相反的原始矩阵，如果排列的数量为奇数。
This problem arises in numerical linear algebra. Some matrix decompositions use pivoting, which effectively swaps row with the greatest value for the next row to be manipulated, in order to avoid division by small numbers and improve numerical stability. Some decompositions, such as the LU decomposition can be later used to calculate matrix determinant, but the sign of the determinant of the decomposition is opposite to that of the original matrix, if the number of permutations is odd.
修改：我同意，这个问题类似于<一href="http://stackoverflow.com/questions/7797540/counting-the-swaps-required-to-convert-one-permutation-into-another">Counting要求掉期将一种置换成另一种。但我认为，这个问题是更根本的。从一个到另一个转换置换可通过颠倒在O（n）的目标置换，构成排列在O（n）和再发现掉期的数量从那里身份转换到这个问题。通过明确地解决了这个问题重新presenting身份，另一种排列似乎不理想。此外，其他的问题了，直到昨天，四个答案，其中只有一座（由| \ / |广告）是看似有用，但该方法的描述显得含糊不清。现在，用户lizusek提供回答我的问题在那里。我不同意关闭这个问题是重复的。
EDIT: I agree that this question is similar to Counting the swaps required to convert one permutation into another. But I would argue that this question is more fundamental. Converting permutation from one to another can be converted to this problem by inverting the target permutation in O(n), composing the permutations in O(n) and then finding the number of swaps from there to identity. Solving this question by explicitly representing identity as another permutation seems suboptimal. Also, the other question had, until yesterday, four answers where only a single one (by |\/|ad) was seemingly useful, but the description of the method seemed vague. Now user lizusek provided answer to my question there. I don't agree with closing this question as duplicate.
EDIT2 ：该算法实际上显得较为理想，如在评论用户rcgldr指出，看到我的回答<一href="http://stackoverflow.com/questions/7797540/counting-the-swaps-required-to-convert-one-permutation-into-another/22916192#22916192">Counting要求掉期将一种置换成另一种。
EDIT2: The proposed algorithm actually seems to be rather optimal, as pointed out in a comment by user rcgldr, see my answer to Counting the swaps required to convert one permutation into another.
推荐答案
我认为关键是要想到排列在的周期分解。
I believe the key is to think of the permutation in terms of the cycle decomposition.
这EX presses任何排列不相交周期的产品。
This expresses any permutation as a product of disjoint cycles.
主要事实是：
- 在两个不相交的循环交换的元素产生一个较长的周期
- 在同一个周期内交换的元素产生一个较少的周期
- 所需排列的个数为n C，其中c是循环的数量在分解
您算法总是交换在同一周期的元素，以便将正确计算互换的数量需要的。
Your algorithm always swaps elements in the same cycle so will correctly count the number of swaps needed.
如果需要，还可以通过计算周期分解并返回ñ减去发现的周期数这样在为O（n）。
If desired, you can also do this in O(n) by computing the cycle decomposition and returning n minus the number of cycles found.
计算周期分解为O（N）由开始的第一个节点，并按照排列，直到再次达到启动来完成。马克所有访问过的节点，然后在下次访问过的节点再次启动。
Computing the cycle decomposition can be done in O(n) by starting at the first node and following the permutation until you reach the start again. Mark all visited nodes, then start again at the next unvisited node.
这篇关于掉期在排列号码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
