论文标题
lre的上限用于对$ r_n $排序
An Upper Bound for Sorting $R_n$ with LRE
论文作者
论文摘要
Alphabet上的排列$π$ $σ= {1,2,3，\ ldots，n} $，是一个序列，其中每个元素$ x $ in $σ$中的每个元素都完全发生一次。 $ s_n $是对称群体，由所有长度$ n $定义的$σ$定义的排列组成。 $ i_n $ = $（1，2，3，\ ldots，n）$和$ r_n =（n，n，n-1，n-2，\ ldots，2，1）$是身份（即排序）和反向排列。我们称之为$ lre $操作的操作已在OEI中定义为具有身份A186752的操作。此操作由三个发电机组成：左转，右转和换位（1,2）。我们将转换（1,2）称为将两个最左边元素交换为$ Exchange $。将$ r_n $转换为$ i_n $带有$ lre $操作所需的最小移动次数以$ n \ leq 11 $而闻名，OEI中列出了序列号A186752。对于这个问题，没有上限。 OEIS序列A186783在由$ lre $ operations \ cite {oeis}生成时，给出对称组$ s_n $的猜想直径。本文的贡献是：（a）用$ lre $对$ r_n $排序$ r_n $所需的移动次数的第一个非平凡的上限； （b）用$ lre $对$ r_n $排序所需的移动次数的更紧密的上限； （c）已经计算了排序$ r_ {10} $和$ r_ {11} $所需的最小移动数。在这里，我们正在计算由$ lre $操作生成的Cayley图直径的上限。 Cayley图用于计算机互连网络中，以建模有效的并行体系结构。网络的直径对应于网络中的最大延迟。
A permutation $π$ over alphabet $Σ= {1,2,3,\ldots,n}$, is a sequence where every element $x$ in $Σ$ occurs exactly once. $S_n$ is the symmetric group consisting of all permutations of length $n$ defined over $Σ$. $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 $n \leq 11$ 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.
