An Upper Bound for Sorting R_n with LRE

MaRDI QIDQ6335020zbMATH OpenFDO

Authors Sai Satwik Kuppili, Bhadrachalam Chitturi

Publication date 17 February 2020

Abstract: A permutation $pi$ over alphabet $Sigma=1,2,3,ldots,n$, is a sequence where every element $x$ in $Sigma$ occurs exactly once. $S_n$ is the symmetric group consisting of all permutations of length $n$ defined over $Sigma$. $I_n$ = $(1,2,3,ldots,n)$ and $R_n=(n,n-1,n-2,ldots,2,1)$ are identity (i.e. sorted) and reverse permutations respectively. An operation, that we call as an $LRE$ operation, has been defined in OEIS with identity A186752. This operation is constituted by three generators: left-rotation, right-rotation and transposition(1,2). We call transposition(1,2) that swaps the two leftmost elements as $Exchange$. The minimum number of moves required to transform $R_n$ into $I_n$ with $LRE$ operation are known for $nleq11$ as listed in OEIS with sequence number A186752. For this problem no upper bound is known. OEIS sequence A186783 gives the conjectured diameter of the symmetric group $S_n$ when generated by $LRE$ operations cite{oeis}. The contributions of this article are: (a) The first non-trivial upper bound for the number of moves required to sort $R_n$ with $LRE$; (b) a tighter upper bound for the number of moves required to sort $R_n$ with $LRE$; and (c) the minimum number of moves required to sort $R_{10}$ and $R_{11}$ have been computed. Here we are computing an upper bound of the diameter of Cayley graph generated by $LRE$ operation. Cayley graphs are employed in computer interconnection networks to model efficient parallel architectures. The diameter of the network corresponds to the maximum delay in the network.

This page was built for publication: An Upper Bound for Sorting $R_n$ with LRE

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6335020)