0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
a b c d e f g h i j 10 9 8 7 6 5 4 3 2 1 <--------- First Sub-string
20 21 22 23
l k 11 12 <--------- Second Sub-string
24 25
m 13
2. Second half of first sub-string and first half of second sub-string reversed together( They are merged, i.e. there are only two sub-strings now ).
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
a b c d e f g h i j k l 1 2 3 4 5 6 7 8 9 10 11 12
24 25
m 13
Joining first sub-string and second sub-string:
1. Second half of first sub-string and first half of second sub-string reversed.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
a b c d e f g h i j k l 12 11 10 9 8 7 6 5 4 3 2 1 <----- First Sub-string
24 25
m 13 <----- Second Sub-string
2. Second half of first sub-string and first half of second sub-string reversed together( They are merged, i.e. there is only one sub-string now ).
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
a b c d e f g h i j k l m 1 2 3 4 5 6 7 8 9 10 11 12 13
Since all sub-strings have been joined together, we are done.
How does cycle leader iteration algorithm work
Let us understand it with an example:
Input:
0 1 2 3 4 5 6 7 8 9
a 1 b 2 c 3 d 4 e 5
Output:
0 1 2 3 4 5 6 7 8 9
a b c d e 1 2 3 4 5
Old index New index
0 0
1 5
2 1
3 6
4 2
5 7
6 3
7 8
8 4
9 9
Let len be the length of the string. If we observe carefully, we find that the new index is given by below formula:
if( oldIndex is odd )
newIndex = len / 2 + oldIndex / 2;
else
newIndex = oldIndex / 2;
So, the problem reduces to shifting the elements to new indexes based on the above formula.
Cycle leader iteration algorithm will be applied starting from the indices of the form 3^k, starting with k = 0.
Below are the steps:
1. Find new position for item at position i. Before putting this item at new position, keep the back-up of element at new position. Now, put the item at new position.
2. Repeat step#1 for new position until a cycle is completed, i.e. until the procedure comes back to the starting position.
3. Apply cycle leader iteration algorithm to the next index of the form 3^k. Repeat this step until 3^k < len.
Consider input array of size 28:
The first cycle leader iteration, starting with index 1:
1->14->7->17->22->11->19->23->25->26->13->20->10->5->16->8->4->2->1
The second cycle leader iteration, starting with index 3:
3->15->21->24->12->6->3
The third cycle leader iteration, starting with index 9:
9->18->9
[cpp]
#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