# Optimal Algorithms for Sorting Permutations with Brooms
## 2 Preliminaries and Background  
In this article, we employ the alphabet \(\{1,2,\cdots,n-1,n\}\) to generate the symmetric group \(S_{n}\). The permutation \(I=(1,2,3,4,\cdots,n-1,n)\) is the identity permutation in \(S_{n}\). An operation \(\mathcal{G}\) is specified by a generator set that is a subset of \(S_{n}\); \(\mathcal{G}\subset S_{n}\). Each permutation in the generator set is a _generator_. Let \(\pi\) be a permutation in \(S_{n}\), and \(\sigma\) be a generator. Applying \(\sigma\) on \(\pi\) yields another permutation, say \(\gamma\in S_{n}\). We say that \(\sigma\)_transforms_\(\pi\) into \(\gamma\). Given two permutations \(\alpha,\beta\in S_{n}\), and an operation \(\mathcal{G}\), the minimum number of generators of \(\mathcal{G}\) required to transform \(\alpha\) into \(\beta\) is called the _distance_ from \(\alpha\) to \(\beta\) under \(\mathcal{G}\), denoted by \(d_{\mathcal{G}}(\alpha,\beta)\) and in general, it is hard to compute the same if the number of generators is two or more [12]. When \(\mathcal{G}\) is symmetric, then \(d_{\mathcal{G}}(\alpha,\beta)=d_{\mathcal{G}}(\beta,\alpha)\). If the target permutation is \(I\), then \(d_{\mathcal{G}}(\alpha,l)\) is succinctly denoted as \(d_{\mathcal{G}}(\alpha)\), which is called the distance of \(\alpha\). Transforming \(\alpha\) into \(I\) is called as sorting \(\alpha\), and thus \(d_{\mathcal{G}}(\alpha)\) is the number of generators required to sort \(\alpha\) parsimoniously. Let \(g_{1},g_{2},\ldots g_{t}\) be a shortest sequence of generators such that \(\alpha\circ g_{1}\circ g_{2}\ldots g_{t}=\beta\). Then \(\beta^{-1}\circ\alpha\circ g_{1}\circ g_{2}\ldots g_{t}=\beta^{-1}\circ\beta=I\). That is, the number of moves required to transform \(\alpha\) into \(\beta\) is same as that of transforming \(\beta^{-1}\circ\alpha\) into the identity permutation \(I\). Thus, the problem of finding minimum distance between two given permutations reduces to the problem of sorting a related permutation. If the target permutation is \(I\), then \(d_{\mathcal{G}}(\beta^{-1}\circ\alpha,I)\) is denoted as \(d_{\mathcal{G}}(\beta^{-1}\circ\alpha)\), which is called the distance of a single permutation \(\beta^{-1}\circ\alpha\). Various operations have been studied in the past. Some of them are reversal, transposition, block interchange, etc. A block move operation moves a block; e.g., block transposition, suffix block transposition etc. A small sample of the research in this broad area follows. [PERSON] studied sorting permutations by transpositions and proved a tighter lower bound based on the hurdles of the underlying cycle graph and designed a simpler \(3/2\)-approximation algorithm [13]. The first non-trivial lower and upper bounds for prefix transposition distance over permutations were given in [2]. [PERSON] et al. [14] shows how to compute the transposition distances of all permutations in \(S_{n}\) in an amortized time of \(O(n^{3})\). Recently, subsets of permutations related to a certain type of block move operation have been counted [15]. These results are varied in type that employ distinct techniques such as dynamic programming and applications of graph properties, and constructs such as cycle graphs and adjacencies in permutations. A Cayley graph \(\Gamma_{T}\) under the operation \(T\) over \(S_{n}\) is defined as follows. The vertex set \(V\) of \(\Gamma_{T}\) consists of all permutations in \(S_{n}\). There is an edge from vertex \(u\) to vertex \(v\) if there is a generator \(g\in T\) such that \(ug=v\). The distance between two permutations \(\alpha\), and \(\beta\) under the operation \(T\), \(d_{T}(\alpha,\beta)\) is equal to the number of edges in the shortest path between the corresponding vertices in \(\Gamma_{T}\). The _diameter_ of \(\Gamma_{T}\), \(D_{T}(n)=max_{u,v\in S_{n}}d_{T}(u,v)\). A transposition tree in turn gives rise to a Cayley graph (refer Figure 1). The problem of sorting permutations using transposition trees is also known as _token swapping on trees_[16; 17; 18; 5; 6; 11; 19].