char s[] = "1a2b3c4d5e6f7g8h9i";
int n = strlen(s);
inPlaceMove(s, n);
cout << s << endl;
cin.get();
return 0;
}
#include
#include
#include
using namespace std;
void swap(char &a, char &b) {
b ^= a;
a ^= b;
b ^= a;
}
void reverse(char *s, int start, int end) {
while (start < end) {
swap(*(s + start), *(s + end));
start++;
end--;
}
}
void cycleLeader(char *s, int offset, int len) {
int i, index;
char item;
for (i = 1; i < len; i *= 3) {
index = i;
item = s[index + offset];
do {
if (index & 0x01)
index = len / 2 + index / 2;
else
index = index / 2;
swap(*(s + index + offset), item);
} while (index != i);
}
}
void inPlaceMove(char *s, int length) {
int left_len = length;
int part_len = 0;
int k = 0;
int offset = 0;
while (left_len) {
k = 0;
while (pow((double)3, k) + 1 <= left_len)
k++;
part_len = pow((double)3, k - 1) + 1;
left_len -= part_len;
cycleLeader(s, offset, part_len);
if (offset) {
reverse(s, offset / 2, offset - 1);
reverse(s, offset, offset + part_len / 2 - 1);
reverse(s, offset / 2, offset + part_len / 2 - 1);
}
offset += part_len;
}
}
int main(int argc, char *argv[]) {
char s[] = "1a2b3c4d5e6f7g8h9i";
int n = strlen(s);
inPlaceMove(s, n);
cout << s << endl;
cin.get();
return 0;
}