开发者

How to calculate the cycles that change one permutation into another?

开发者 https://www.devze.com 2022-12-24 00:26 出处:网络
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

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...

0

精彩评论

暂无评论...
验证码 换一张
取 消