sklima
November 7th, 2010, 01:35 PM
Hello!
I'm looking for a solution for the following problem:
Given an even permutation of a set {1,...,n} for an odd n, find a way to arrange it in the natural order (1,2,3,4,...,n-1,n) using two operations:
OP1(k): Shift the last element to the front (eg. [1,2,3,4,5] -> [5,1,2,3,4]), k times
OP2(k): Shift the third element to the front (eg. [1,2,3,4,5] -> [3,1,2,4,5]), k times
Do it in at most n^2 operations (OP1(1000) counts as one, not 1000)). So far my research has indicated that this can be accomplished using an initial OP1 (no idea about the argument, though) and then series of OP2(1) OP1(1) and OP2(2) OP1(1).
Any input would be highly appreciated. If you can't meet the n^2 cirterion, but have an idea, please chip in aswell.
Thanks in advance,
Stephen Klima
I'm looking for a solution for the following problem:
Given an even permutation of a set {1,...,n} for an odd n, find a way to arrange it in the natural order (1,2,3,4,...,n-1,n) using two operations:
OP1(k): Shift the last element to the front (eg. [1,2,3,4,5] -> [5,1,2,3,4]), k times
OP2(k): Shift the third element to the front (eg. [1,2,3,4,5] -> [3,1,2,4,5]), k times
Do it in at most n^2 operations (OP1(1000) counts as one, not 1000)). So far my research has indicated that this can be accomplished using an initial OP1 (no idea about the argument, though) and then series of OP2(1) OP1(1) and OP2(2) OP1(1).
Any input would be highly appreciated. If you can't meet the n^2 cirterion, but have an idea, please chip in aswell.
Thanks in advance,
Stephen Klima