Finding an algorithm that goes through all the possible permutations of a set only by swapping 2 elements

Question

I recently came across a problem when trying to deal with a set of numbers with n elements. The problem is as follows:

Starting with a set of n distinct elements, how would one generalize a unique algorithm such that all the possible permutations of the set would appear exactly once, with the following rules:

1. Denote (a,b) as the action of swapping the a-th and b-th element of the set of size n, and in the following examples, we let the set A_n={a1,a2,a3,...,a_n}, and its initial permutation begins in the specified order, ie, a1,a2,a3,...,a_n
2. We can change the permutation of the set only by swapping any 2 elements of the set
3. After 2 elements are swapped, the permutation stays that way, and a new swapping move should begin from there
4. The total number of swaps should be equal to (n!-1), and all the possible permutations should appear only once
5. The elements that appear later in the set should not be involved in swapping until no further new permutations can be found if they are not swapped (further explained in the example of n=3)
6. A rule to guarantee uniqueness: when swapping a_k with another element and there are multiple choices we can swap it with, we should swap it with a_k-1
7. The algorithm is self similar (further elaboration below, by the example of n>=4)

Examples:

For n=2, the solution is trivial: (1,2) is the unique solution. We first begin with a1,a2, and after swapping we get a2,a1. Thus all permutations are found. We then now define the algorithm as S2=(1,2).

For n=3, we should avoid swapping the elements that appear later in the list, ie, a3 (rule 5), so the first swap should be (1,2), resulting in a2,a1,a3. Since no more possible permutations can be reached if we don't swap a3, we have to swap a3. Thus we can do (1,3) or (2,3). To guarantee uniqueness, we should swap a2 with a3 (rule 6). So the move is (1,3). Based on these rules, we can quickly find that the unique solution would be (1,2),(1,3),(1,2),(1,3),(1,2). After these 5 swaps, all the possible permutations of the 3 elements a1,a2,a3 would have appeared exactly once, and the final permutation we arrive at is a3,a2,a1. We then now define the algorithm as S3=S2,(1,3),S2,(1,3),S2

For n=4 (and beyond), we guarantee the uniqueness by requiring the algorithm to be self similar. Beginning from a1,a2,a3,a4, we first do swapping among the first 3 elements, by applying S3 to the first 3 elements. From the results we find in the case of n=3, we see that after doing 5 swappings, we would arrive at a3,a2,a1,a4. Then, we have to swap away the a4. Based on the uniqueness rule, we should swap a4 with a3, and then go back to swapping the first 3 elements of the set, which is now arranged as a4,a2,a1. We then apply the algorithm S3 to these 3 elements to go through their possible permutaions. After applying, we would arrive at a1,a2,a4,a3. Then, we should swap a2 with a3, and then apply S3 to the first 3 elements, and repeat the steps.

Visually:

a1,a2,a3,a4

--> a3,a2,a1,a4 (Apply S3 to first 3 elements)

--> a4,a2,a1,a3 (Swap a4 with a3, ie, do (1,4))

--> a1,a2,a4,a3 (Apply S3 to first 3 elements)

--> a1,a3,a4,a2 (Swap a3 with a2, ie, do (2,4))

--> a4,a3,a1,a2 (Apply S3 to first 3 elements)

--> a4,a3,a2,a1 (Swap a2 with a1, ie, do (3,4))

--> a2,a3,a4,a1 (Apply S3 to first 3 elements)

All 24 permutations are now listed, with the last permutation being a2,a3,a4,a1. Then define this algorithm as S4=S3,(1,4),S3,(2,4),S3,(3,4),S3

A summarized recursive definition of S_n:

For n=2, S_n=(1,2)

For n>2, S_n=S_n-1, (x₁,n), S_n-1, (x₂,n), S_n-1,..., (x_n-1,n), S_n-1 where there are in total n S_n-1s, and x_k denotes the position of a_n-k

Now, we can see how this can be generalized to S_n. The goal is to find a general formula for S_n, as well as finding its transformation of the set after applying the algorithm. My problem is that I see some initial pattern, but I encounter a weird pattern breaking phenomenon when n=8. Details is as follows:

S2=(1,2), the base case.(Transforms a1,a2 into a2,a1)

S3=S2,(1,3),S2,(1,3),S2 (Transforms a1,a2,a3 into a3,a2,a1)

S4=S3,(1,4),S3,(2,4),S3,(3,4),S3 (Transforms a1,a2,a3,a4 into a2,a3,a4,a1)

S5=S4,(3,5),S4,(1,5),S4,(3,5),S4,(1,5),S4 (Transforms a1,a2,a3,a4,a5 into a3,a4,a5,a2,a1)

S6=S5,(3,6),S5,(4,6),S5,(3,6),S5,(2,6),S5,(3,6),S5 (Transforms a1,a2,a3,a4,a5,a6 into a2,a3,a4,a5,a6,a1)

S7=S6,(5,7),S6,(3,7),S6,(1,7),S6,(5,7),S6,(3,7),S6,(1,7),S6 (Transforms a1,a2,a3,a4,a5,a6,a7 into a3,a4,a5,a6,a7,a2,a1)

The problem is that the pattern breaks horribly for S8:

S8=S7,(5,8),S7,(2,8),S7,(7,8),S7,(2,8),S7,(1,8),S7,(2,8),S7,(3,8),S7 (Transforms a1,a2,a3,a4,a5,a6,a7,a8 into a2,a7,a4,a3,a6,a5,a8,a1)

The problem reduces to finding the values of x_k for 1<k<n-1. We can see that if n is odd, there is a clear pattern.

Let X_n={x1,x2,x3,...,x_n-1}. Then X3={1,1}, X5={3,1,3,1}, X7={5,3,1,5,3,1}

More importantly, the pattern of the transformation of A_n by S_n is even more obvious:

If n is even, A_n{a1,a2,a3,...,a_n-1,a_n} is transformed by S_n into {a2,a3,a4,...,a_n,a1}

If n is odd, A_n{a1,a2,a3,...,a_n-1,a_n} is transformed by S_n into {a3,a4,...,a_n,a2,a1}

The pattern breaks at n=8. S8 transforms A8 into {a2,a7,a4,a3,a6,a5,a8,a1}, which is a completely random looking sequence of numbers. Also, X9 does not equal {7,5,3,1,7,5,3,1}, breaking the mentioned pattern as well. Moreover, I can't even figure out a pattern for X_n for n<=8 if n is even. Is there any reason as to why the patterns of X_n when n is odd, as well as the pattern of the transformation of S_n breaks when n>7? Is it even possible to find an expression for finding X_n?