How to calculate the cycles that change one permutation into another?
I'm looking for an algorithm th开发者_如何学JAVAat given two permutations of a sequence (e.g. [2, 3, 1, 4]
and [4, 1, 3, 2]
) calculates the cycles that are needed to convert the first into the second (for the example, [[0, 3], [1, 2]]
).
The link from mathworld says that Mathematica's ToCycle function does that, but sadly I don't have any Mathematica license at hand... I'd gladly receive any pointer to an implementation of the algorithm in any FOSS language or mathematics package.
Thanks!
I found a solution here http://www.codechef.com/problems/PCYCLE it only needs to be adjusted to remap the indices to the sorting order established by the second permutation...
精彩评论