仅根据旋转操作反转数组/字符串的算法

Question

假设我们只能通过调用反转来对数组进行左旋转（然后右旋转），如下所示：

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()      );
}

仅通过旋转操作来反转数组/字符串的算法是什么？

有一个循环过程，将长度的数组旋转 N，n 次，但我想知道是否有一种类似于上面使用反向但仅使用旋转调用的简单方法。

Answer 1

我认为仅使用旋转来反转数组（超过 2 个项目）是可能的。 例如，如果数组以元素

[A,B,C]

开头， 任何旋转组合只能导致 3 种可能的结果：

[A,B,C]

[B,C,A]

[C,A,B]

这些都不是逆转。如果您将其视为从一个字母到下一个字母的级联，则趋势始终向右（在某处跳转回

A

）。我发现这在循环缓冲区样式数组上更容易可视化。

当使用反转实现旋转时，每个项目都会涉及 2 次反转，这是偶数。仅使用旋转无法实现奇数个反转。