Editing Permutation (section)

====Generation of permutations in nested swap steps====
Explicit sequence of swaps (transpositions, 2-cycles <math>(pq)</math>), is described here, each swap applied (on the left) to the previous chain providing a new permutation, such that all the permutations can be retrieved, each only once.<ref>{{cite book
|author1=Popp, O.T. | title = Quickly Handling Big Permutations
| orig-year = 
| edition = 
| year = 2002
| pages = 
| publisher = priv. comm.
| location = 
| oclc = 
}}</ref> This counting/generating procedure has an additional structure (call it nested), as it is given in steps: after completely retrieving <math>S_{k-1}</math>, continue retrieving <math>S_{k}\backslash S_{k-1}</math> by cosets <math>S_{k-1}\tau_i</math> of <math>S_{k-1}</math> in <math>S_k</math>,  by appropriately choosing the coset representatives <math>\tau_i</math> to be described below. Since each <math>S_m</math> is sequentially generated, there is a ''last element'' <math>\lambda_m\in S_m</math>. So, after generating <math>S_{k-1}</math> by swaps, the next permutation in <math>S_{k}\backslash S_{k-1}</math>  has to be <math>\tau_1=(p_1k)\lambda_{k-1}</math> for some <math>1\leq p_1<k</math>. Then all swaps that generated  <math>S_{k-1}</math> are repeated, generating the whole coset <math>S_{k-1}\tau_1</math>, reaching the last permutation in that coset <math>\lambda_{k-1}\tau_1</math>; the next swap has to move the permutation to representative of another coset <math>\tau_2=(p_2k)\lambda_{k-1}\tau_1</math>. 

Continuing the same way, one gets coset representatives <math>\tau_j=(p_{j}k)\lambda_{k-1}\cdots \lambda_{k-1}(p_{i}k)\lambda_{k-1}\cdots\lambda_{k-1}(p_{1}k)\lambda_{k-1}</math> for the cosets of  <math>S_{k-1}</math> in <math>S_k</math>; the ordered set <math>(p_1,\ldots , p_{k-1})</math> (<math>0\leq p_i<k</math>) is called the set of coset beginnings. Two of these representatives are in the same coset if and only if  <math>\tau_j(\tau_i)^{-1}=(p_{j}k)\lambda_{k-1}(p_{j-1}k)\lambda_{k-1}\cdots \lambda_{k-1}(p_{i+1}k)=\varkappa_{ij}\in S_{k-1}</math>, that is,  <math>\varkappa_{ij} (k)=k</math>. Concluding, permutations <math>\tau_i\in S_k-S_{k-1}</math> are all representatives of distinct cosets if and only if for any <math>k>j>i\geq 1</math>, <math>(\lambda_{k-1})^{j-i}p_{i}\neq p_j</math> (no repeat condition).  In particular, for all generated permutations to be distinct it is not necessary for the <math>p_i</math> values to be distinct. In the process, one gets that <math>\lambda_k=\lambda_{k-1}(p_{k-1}k)\lambda_{k-1}(p_{k-2}k)\lambda_{k-1}\cdots\lambda_{k-1}(p_{1}k)\lambda_{k-1}</math> and this provides the recursion procedure. 

EXAMPLES: obviously, for <math>\lambda_2</math> one has <math>\lambda_2=(12)</math>; to build <math>\lambda_3</math> there are only two possibilities for the coset beginnings satisfying the no repeat condition; the choice <math> p_1=p_2=1</math> leads to <math>\lambda_3=\lambda_2(13)\lambda_2(13)\lambda_2=(13)</math>. To continue generating <math>S_4</math> one needs appropriate  coset beginnings (satisfying the no repeat condition): there is a convenient choice: <math>p_1=1, p_2=2, p_3=3</math>, leading to  <math>\lambda_4=(13)(1234)(13)=(1432)</math>. Then, to build <math>\lambda_5</math> a convenient choice for the coset beginnings (satisfying the no repeat condition) is <math> p_1=p_2=p_3=p_4=1</math>, leading to <math>\lambda_5=(15)</math>. 

From examples above one can inductively go to higher <math>k</math> in a similar way, choosing coset beginnings of <math>S_{k}</math> in  <math>S_{k+1}</math>, as follows: for <math>k</math> even choosing all coset beginnings equal to 1 and for <math>k</math> odd choosing coset beginnings equal to <math>(1, 2,\dots , k)</math>. With such choices the "last" permutation is <math>\lambda_k=(1k)</math> for <math>k</math> odd and  <math>\lambda_k=(1k_-)(12\cdots k)(1k_-)</math> for <math>k</math> even (<math>k_-=k-1</math>). Using these explicit formulae one can easily compute the permutation of certain index in the counting/generation steps with minimum computation. For this, writing the index in factorial base is useful. For example, the permutation for index <math>699=5(5!)+4(4!)+1(2!)+1(1!)</math> is: <math>\sigma=\lambda_2(13)\lambda_2(15)\lambda_4(15)\lambda_4(15)\lambda_4(15)\lambda_4(56)\lambda_5(46)\lambda_5(36)\lambda_5(26)\lambda_5(16)\lambda_5=</math> <math>\lambda_2(13)\lambda_2((15)\lambda_4)^4(\lambda_5)^{-1}\lambda_6=(23)(14325)^{-1}(15)(15)(123456)(15)=</math><math>(23)(15234)(123456)(15)</math>, yelding finally, <math>\sigma=(1653)(24)</math>.

Because multiplying by swap permutation  takes  short computing time and every new generated permutation requires only one such swap multiplication, this generation procedure is quite efficient. Moreover as there is a simple formula, having the last permutation in each <math>S_k</math>  can save even more time to go directly to a permutation with certain index in fewer steps than expected as it can be done in blocks of subgroups rather than swap by swap.