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

Question

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.

Limekiln

Are you allowed to call rotl on a subarray (where .end() would indicate the end of that subarray)? Can you share the "loop-wise process" you mentioned? – Leis

@Leis one could assume that rotl has a similar interface to std;:rotate and provide the same side effects. – Limekiln

Is this a question specific to C++ then? Can you just answer the question on whether rotl can be called on subarrays? Or else tag your question with c++? – Leis

@trincot: yes rotl can be used to rotate-left subarrays of the array, the question is more about can a reversal be done using only rotations, similar to how a rotation can be achieved using only reversals over the array (or sub arrays of the array. – Limekiln

If you can use a combination of rotl calls on subarrays, then yes, it is possible, but this seems something you already mention in your post as a possibility (loop-wise). Is it maybe that you are looking for a way to do it with a fixed number of rotl calls, no matter how large the size of the original array is? I'm just trying to understand what you are asking here. Because the last paragraph of your post seems to answer the question in the title of your post. What exactly makes that approach not "simple" enough? – Leis

Answer 1

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.

Cupidity

the explanation makes sense – Limekiln