Left/Right Rotation Permutations

[Leroy Quet]

[I will post the following to sci.math.]

Back in April 2003 I posted to sci.math the following puzzler/solution:

http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&safe=off&threadm=b4be2fd
f.0304131640.4855eb36%40posting.google.com&rnum=3&prev=

>...
>> Below is the 1st 16 permutations of {1,2,3,...,m}, m= 1 to 16, each
>> permutation achieved by the same algorithm.
>> 
>> 1
>> 2,1
>> 2,3,1
>> 3,1,2,4
>> 2,1,5,4,3
>> 1,3,2,5,6,4
>> 6,1,2,3,5,4,7
>> 1,7,4,5,6,8,3,2
>> 9,7,6,1,4,5,3,2,8
>> 7,10,8,3,6,9,5,4,1,2
>> 5,11,10,7,6,3,8,9,1,2,4
>> 11,10,12,1,4,5,9,6,3,2,7,8
>> 3,6,7,11,10,5,4,9,12,13,1,8,2
>> 14,6,7,1,2,3,13,10,9,4,5,8,11,12
>> 1,4,5,10,11,7,6,3,2,13,15,14,9,12,8
>> 8,4,5,9,2,1,16,14,13,10,3,6,7,12,15,11
>> 
>> What is the algorithm?
>> 
>> I have some questions about this permutation algorithm, which can be
>> discussed after the solution is given.
>> 
>
>Answer:
>
>Start with [1,2,3,...,m].
>Reverse the order of the leftmost 1 element. (trivial)
>Reverse the order of the rightmost 2 elements.
>Reverse the order of the leftmost 3 elements of the previous
>permutation.
>Reverse the order of the rightmost 4 elements of the previous
>permutation.
>...
>until...
>Reverse the order of the rightmost m elements of the (m-1)th
>permutation if m is even.
>Or reverse the order of the leftmost m elements of the (m-1)th
>permutation if m is odd.
>(Of course, these options are the same thing, reversing the order of
>the entire permutation.)
>
>Question...
>Is there an easy way to directly calculate the final position of k in
>the permutation of [1,2,3,...,m]?



I have noticed that neither the sequence of initial terms 
(1,2,2,3,2,1,6,1,9,7,...) of each line of the triangle,
the sequence of rightmost terms (1,1,1,4,3,4,7,2,8,...) of each line of 
the triangle,
nor the triangle itself is in the EIS.

No one posted a response to sci.math answering my question, how can we 
directly calculate the final position of each integer.
I wonder also about how the sequences of initial and final terms of each 
line be calculated without simply doing the recursive swapping.

thanks,
Leroy Quet