Cyclic permutation of elements in one-dimensional array

In this paper, we obtain an expression for the smallest number J(N, K) of pairwise permutations of elements in an one-dimensional N-element array for resulting in the array being cyclically shifted k positions. An algorithm implementing this k-cyclic permutation is also constructed. For an arbitrary integer i, 0 ^ i < N, let ш (i) denote the smallest integer for which f(i) ^ i, where f (i) = i - k if i ^ k, and f (i) = = N (1 + [k/N])-k+i otherwise. Then the smallest number J(N, K) equals the cardinality of the set {i : N > i ^ 0 & g (i) > i}, where the map g : {0,..., N - 1} ^ {0,..., N - 1} is given by the rule g (i) = f(i) (0 ^ i < N).

Keywords

Authors

References