Permutations by Swapping Adjacent Pairs

References:
1) Counting and Listing All Permutations
2) An algorithm to list all the permutations

Known variously as the Steinhaus-Johnson-Trogger algorithm, the Johnson-Trotter algorithm, or the Steinhaus algorithm. Summarized in these steps:

Initialize the first permutation with <1 <2 ... <n
While there exists a mobile integer:

1. Find the largest mobile integer k.
2. Swap k and the adjacent integer it is looking at.
3. Reverse the direction of all integers larger than k.
   

To embody the traveling metaphor into action, the algorithm replaces integer as the basic element of the procedure with a structure that maintains an integer and a direction. Call the structure a directed integer, or just an integer if the context is clear. The direction may take on only one of two values, "left" or "right", and can be implemented as a boolean. It's convenient and certainly appropriate to say that a directed integer is looking left- or rightwards depending on the value of the attached field direction.

The algorithm requires one more definition: a directed integer is said to be mobile if it is greater than its immediate neighbor in the direction it is looking at.

Example output:

1 2 3 4
1 2 4 3
1 4 2 3
4 1 2 3
4 1 3 2
1 4 3 2
1 3 4 2
1 3 2 4
3 1 2 4
3 1 4 2
3 4 1 2
4 3 1 2
4 3 2 1
3 4 2 1
3 2 4 1
3 2 1 4
2 3 1 4
2 3 4 1
2 4 3 1
4 2 3 1
4 2 1 3
2 4 1 3
2 1 4 3
2 1 3 4