Research PaperNo Access

Exact upper bound for sorting $R_{n}$ with LE

Sai Satwik Kuppili

Dept. of Computer Science and Engineering, Amrita Vishwa Vidyapeetham, Amritapuri, India

E-mail Address: satwik.kuppili@gmail.com

Search for more papers by this author

and

Bhadrachalam Chitturi

http://orcid.org/0000-0002-8768-9183

Dept. of Computer Science, University of Texas at Dallas, Richardson, TX, USA

E-mail Address: chalam@utdallas.edu

Search for more papers by this author

https://doi.org/10.1142/S1793830920500330Cited by:2 (Source: Crossref)

Abstract

A permutation over alphabet $Σ = (1, 2, 3, \dots, n)$ is a sequence over $Σ$ , where every element occurs exactly once. $S_{n}$ denotes symmetric group defined over $Σ$ . $I_{n} = (1, 2, 3, \dots, n) \in S_{n}$ denotes the Identity permutation. $R_{n} \in S_{n}$ is the reverse permutation i.e., $R_{n} = (n, n - 1, n - 2, \dots, 2, 1)$ . An operation, that we call as an LE operation, has been defined which consists of exactly two generators: set-rotate that we call Rotate and pair-exchange that we call Exchange (OEIS). At least two generators are the required to generate $S_{n}$ . Rotate rotates all elements to the left (moves leftmost element to the right end) and Exchange is the pair-wise exchange of the two leftmost elements. The optimum number of moves for transforming $R_{n}$ into $I_{n}$ with LE operation are known for $n \leq 10$ ; as listed in OEIS with identity A048200. However, no general upper bound is known. The contributions of this article are: (a) a novel upper bound for the number of moves required to sort $R_{n}$ with LE has been derived; (b) the optimum number of moves to sort the next larger $R_{n}$ i.e., $R_{11}$ has been computed; (c) an algorithm conjectured to compute the optimum number of moves to sort a given $R_{n}$ has been designed.

Keywords:

AMSC: 68Q25, 68Q17

References

1. The On-Line Encyclopedia of Integer Sequences: oeis.org. Google Scholar
2. S. B. Akers and B. Krishnamurthy , A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput. 38(4) (1989) 555–566. Crossref, Google Scholar
3. A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A. M. Naredla, J. Tkadlec and A. Turcotte, arXiv preprint, arXiv:1903.06981, 2019. Google Scholar
4. T. Chen and S. S. Skiena , Sorting with fixed-length reversals, Discr. Appl. Math. 71(1–3) (1996) 269–295. Crossref, Google Scholar
5. B. Chitturi , A note on complexity of genetic mutations, Discr. Math. Algorith. Appl. 3(03) (2011) 269–286. Link, Google Scholar
6. B. Chitturi and P. Das , Sorting permutations with transpositions in $O (n^{3})$ amortized time, Theoret. Comput. Sci. (2018). Google Scholar
7. B. Chitturi, W. Fahle, Z. Meng, L. Morales, C. O. Shields and H. Sudborough , An (18/11) n upper bound for sorting by prefix reversals, Theoret. Comput. Sci. 410(36) (2009) 3372–3390. Crossref, Google Scholar
8. B. Chitturi, Computing cardinalities of subsets of $S_{n}$ with k adjacencies, to appear in JCMCC, 2020. Google Scholar
9. B. Chitturi and K. S. Krishnaveni, Expected genomic dissimilarity, ICMSAO 2019. Google Scholar
10. G. Erskine and T. James , Large Cayley graphs of small diameter, Disc. Appl. Math. (2018). Crossref, Google Scholar
11. X. Feng, B. Chitturi and H. Sudborough , Sorting circular permutations by bounded transpositions, in Advances in Computational Biology (Springer, New York, NY, 2010), pp. 725–736. Crossref, Google Scholar
12. D. A. Gostevsky and E. V. Konstantinova , Greedy cycles in the star graphs, Discr. math. Math. Cybernet. 15(0) (2018) 205–213. Google Scholar
13. M. R. Jerrum , The complexity of finding minimum-length generator sequences, Theoret. Comput. Sci. 36 (1985) 265–289. Crossref, Google Scholar
14. S. S. Kuppili1, B. Chitturi1 and T. Srinath, An upper bound for sorting $R_{n}$ with LE, ICACDS 2019. Google Scholar
15. S. Lakshmivarahan, J-S. Jho and S. K. Dhall , Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey, Parallel Comput. 19 (1993) 361–407. Crossref, Google Scholar
16. H. Mokhtar , A few families of Cayley graphs and their efficiency as communication networks, Bull. Austr. Math. Soc. 95(3) (2017) 518–520. Crossref, Google Scholar
17. J. Pai and B. Chitturi, Super oriented cycles in permutations, ICMSAO 2019. Google Scholar
18. T. Zhang and G. Gennian , Improved lower bounds on the degree–diameter problem, J. Algebr. Combinat. (2018) 1–12. Google Scholar