arraysalgorithmrotationreverse

Algorithm to reverse an array/string only in terms of rotate operations


Given we can do a left-rotate (and subsequently a right-rotate) of an array only in terms of calls to reverse, like so:

void rotl(std::string &s, const int d)
{
    std::reverse(s.begin()    , s.begin() + d);
    std::reverse(s.begin() + d, s.end()      );
    std::reverse(s.begin()    , s.end()      );
}

What would the algorithm be to reverse an array/string in terms of only rotating operations?

There's a loop-wise process which rotates the array of lengths N, n-times, but I was wondering if there's a simple approach similar to the above using reverse but only using rotate calls.


Solution

  • I don't think it's possible to reverse an array (of more than 2 items) using only rotations. For example if an array starts with the elements [A,B,C], any combination of rotations can only result in 3 possible outcomes: [A,B,C]

    [B,C,A]

    [C,A,B]

    None of which is a reversal. If you view this as a cascade from one letter to the next, the trend is always to the right (with a jump somewhere back to A). I find this easier to visualise on a circular buffer style array.

    When you achieve rotations using reversals, each item is involved in 2 reversals, this is an even number. You can't achieve an odd number of reversals using rotations only.