A Linear In-situ Algorithm for the Power of CyclicPermutation

摘要

We present and develop a linear in-situ algorithm for the power of a cyclic permutation P~r (-n < r < n). Several related algorithms become the special cases of this algorithm. At first, we used an abstract structure, named twin ring, to represent cyclic permutation and derive a simple algorithm to compute P~r on twin ring. Then, the algorithm and the abstract structure twin ring were implemented based on PAR platform that consists of a set of program generating tools. The correctness of the final algorithmic program is based on the data coupling invariant and the assumption of PAR Platform correct. The abstract structure twin ring and the program generating tools take a key role in deriving the simple algorithm for computing P~r. The techniques demonstrated in this paper can be used in developing intricate algorithms.