左の m文字と 右の (n-m)文字を交換するのは、
1文字ずつの左ローテートを m回実行すれば実現できます。
ローテートは、s[0] の値を退避し、残りを左にシフトし、
退避していた s[0] を s[n-1] にコピーすることです。
右側の方が短いときは、(n-m)回右ローテートすればよいでしょう。
コード:
void swap(char s[], int n, int m)
{
if (m < n - m)
while (--m >= 0) {
char t = s[0];
for (int i = 1; i < n; i++) s[i-1] = s[i];
s[n-1] = t;
}
else
for (m = n - m; --m >= 0; ) {
char t = s[n-1];
for (int i = n; --i >= 0; ) s[i] = s[i-1];
s[0] = t;
}
}
でも、これは O(n
2) のアルゴリズムで、あまりよくありません
swap("abcdefghijklmnopqrstuvwxyz", 26, 13); だと遅いです。
そこで私は、各文字の移動が 1回だけで済むやり方を考えてみました。
s[0] を退避し、s[0] に s[m] をコピー、s[m] に s[m*2] をコピー、
s[ i] = s[j]; の j が n以上になったら j -= n; で戻します。
このやり方は、n と m が互いに素の場合は、うまくいくんですが、
そうでない場合は、一部だけで循環し、移動が起こらない部分が残ります。
そこで、n と m の最小公倍数を求めておいて、その回数だけずらして
実行することで解決しました。
コード:
int gcd(int a, int b)
{
int r;
while (r = a % b) a = b, b = r;
return b;
}
void swap(char s[], int n, int m)
{
if (m == 0 || m == n) return;
int g = gcd(n, m);
for (int b = 0; b < g; b++) {
char t = s[b];
int i = b, k = b + n - m;
do {
int j = i + m;
if (j >= n) j -= n;
s[i] = s[j];
i = j;
} while (i != k);
s[i] = t;
}
}
ところが、この問題の解答は次のようなものでした。
コード:
void reverse(char s[], int n)
{
char t;
for (int m = 0; m < --n; m++)
t = s[m], s[m] = s[n], s[n] = t;
}
void swap3(char s[], int n, int m)
{
reverse(s, m);
reverse(s + m, n - m);
reverse(s, n);
}
驚きました。移動回数は多いのに速いのです。
「珠玉のプログラミング 本質を見抜いたアルゴリズムとデータ構造」
Jon Bentley著 Programming Pearls Second Edition に載っています。
2014年に丸善出版から再発売されたものが 3672円になっていますが、
2000年にピアソンエデュケーションから出たものが中古で約1000円で買えます。
私はこれを持っています。
Second Edition ではないものの訳本「プログラム設計の着想」なら
中古で 500円程度で買えます。