On the generalized shuffle-exchange problem

Xiaoming Sun (State Key Lab of Processors, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China; and University of the Chinese Academy of Sciences, Beijing, China)

Yuan Sun (State Key Lab of Processors, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China; and University of the Chinese Academy of Sciences, Beijing, China)

Kewen Wu (University of California, Berkeley, Calif., U.S.A.)

Zhiyu Xia (State Key Lab of Processors, Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China; and University of the Chinese Academy of Sciences, Beijing, China)

Abstract

We investigate the shuffle-exchange problem in this paper: given a permutation $\pi$ on $[n] \times [m]$ and two permutation groups $G$ on $[n]$ and $H$ on $[m]$, the goal is to generate $\pi$ by alternately using the following two types of operations:

• Select $g_1, g_2, \dotsc , g_m \in G$ and perform each $g_i$ on the $i$-th column of $[n] \times [m]$ in parallel;

• Select $h_1, h_2, \dotsc, h_n \in H$ and perform each $h_j$ on the $j$-th row of $[n] \times [m]$ in parallel.

We discuss the shuffle-exchange, i.e., the composition of these allowable operations, from the perspective of the Cayley graph.

For cases where the base groups G and H are both cyclic groups, we prove that the diameter of the underlying Cayley graph, i.e., the minimum number of steps sufficient to achieve any permutation, is upper bounded by $O (\min {\lbrace n + m, n \log m, m \log n \rbrace})$, which is asymptotically optimal when $\min {\lbrace n, m \rbrace} = O(1)$ or $n = \Theta (m)$. The main idea is to simulate the shuffle-exchange over symmetric groups with cyclic operations and further accelerate the process with the low-depth periodic switching network. For the shuffle-exchange over general groups, we characterize the reachability of any two given vertices on the Cayley graph, and prove the minimum number of steps to achieve a permutation, if possible, is $O(nm)$. This implies that though a connected component of the Cayley graph could contain exponential number of vertices, its diameter is only at most a polynomial of $n, m$.

Full Text (PDF format)

This work was supported in part by the National Natural Science Foundation of China Grant No. 61832003, 61872334, the Strategic Priority Research Program of Chinese Academy of Sciences Grant No. XDB27000000.

Received 27 July 2021

Received revised 30 August 2022

Accepted 18 September 2022

Published 29 March 2023