Cyclic permutation of elements in one-dimensional array

V. V. Gotsulenko

Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 145-149

Résumé

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\le i$, let $\omega(i)$ denote the smallest integer for which $f^{(\omega(i))}(i)\ge i$, where $f(i)=i-k$ if $i\ge 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\colon N>i\ge0\ \\ g(i)> i\}$, where the map $g\colon\{0,\dots,N-1\}\to\{0,\dots,N-1\}$ is given by the rule $g(i)=f^{(\omega(i))}(i)$ $(0\le i$.

Détail

Keywords: one-dimensional array, pairwise permutation of array elements.
Mots-clés : $k$-cyclic permutation