อัลกอริทึม In-Place สำหรับการแปลง String (ย้ายตัวอักษรตำแหน่งคู่ไปท้าย) ใน C++

โจทย์ปัญหา

ได้รับ String ให้ย้ายตัวอักษรที่อยู่ตำแหน่ง คู่ (Even Index: 0, 2, 4...) ไปอยู่ท้าย String โดย รักษาลำดับสัมพัทธ์ ของทั้งกลุ่มตัวอักษรตำแหน่งคู่และคี่ ใช้ In-Place และ O(n) Time

ตัวอย่าง

นำเข้า: "a1b2c3d4e5f6g7h8i9j1k2l3m4"
ผลลัพธ์: "abcdefghijklm1234567891234"

คำอธิบาย: ตัวอักษร (Index 0,2,4...) → "abcdefghijklm", ตัวเลข (Index 1,3,5...) → "1234567891234"

อัลกอริทึม (Cycle Leader + Reversal)

อัลกอริทึมนี้ซับซ้อน ใช้หลักการ Cycle Leader Iteration ร่วมกับ String Reversal:

1. หา Prefix ใหญ่สุดขนาด 3^k + 1 ที่ ≤ n
2. Cycle Leader Algorithm บน Prefix นั้น:
   • เริ่มที่ Index 1, 3, 9, ... (Powers of 3)
   • หมุนเวียนย้าย Element ไปตำแหน่งที่ถูกต้อง (Odd→Left Half, Even→Right Half)
3. ทำซ้ำกับ Suffix ที่เหลือ (Recursive)
4. Merge Substrings ด้วยการ Reverse 3 ขั้นตอน:
   • Reverse Second Half ของ Substring แรก
   • Reverse First Half ของ Substring ที่สอง
   • Reverse ทั้งสองส่วนรวมกัน

โค้ดตัวอย่าง (C++)

#include <bits/stdc++.h>
using namespace std;

void swap(char* a, char* b) { char t = *a; *a = *b; *b = t; }

void reverse(char* str, int low, int high) {
    while (low < high) { swap(&str[low], &str[high]); low++; high--; }
}

void cycleLeader(char* str, int shift, int len) {
    for (int i = 1; i < len; i *= 3) {
        int j = i;
        char item = str[j + shift];
        do {
            // Odd index -> move to left half
            // Even index -> move to right half
            if (j & 1) j = len / 2 + j / 2;
            else j /= 2;
            swap(&str[j + shift], &item);
        } while (j != i);
    }
}

void moveNumberToSecondHalf(char* str) {
    int lenRemaining = strlen(str);
    int shift = 0;

    while (lenRemaining) {
        int k = 0;
        // หา 3^k + 1 ใหญ่สุด ≤ lenRemaining
        while (pow(3, k) + 1 <= lenRemaining) k++;
        int lenFirst = pow(3, k - 1) + 1;
        lenRemaining -= lenFirst;

        // Cycle Leader
        cycleLeader(str, shift, lenFirst);

        // Merge with previous (3 Reversals)
        reverse(str, shift/2, shift - 1);
        reverse(str, shift, shift + lenFirst/2 - 1);
        reverse(str, shift/2, shift + lenFirst/2 - 1);

        shift += lenFirst;
    }
}

int main() {
    char str[] = "a1b2c3d4e5f6g7";
    moveNumberToSecondHalf(str);
    cout << str << endl;  // abcdefg1234567
    return 0;
}

ผลลัพธ์

abcdefg1234567

คำอธิบายเพิ่มเติม

• อัลกอริทึมนี้เป็น In-Place จริง (O(1) Extra Space)
• Time Complexity: O(n) - แต่ละตัวอักษรถูกย้าย O(1) ครั้ง
• Cycle Leader ใช้เลขฐาน 3 (3^k) เพื่อให้ Cycle ครอบคลุมทุกตำแหน่ง
• ซับซ้อนมาก - ในทางปฏิบัติมักใช้ Extra Array O(n) Space เพื่อความชัดเจน
• เหมาะสำหรับ Embedded Systems ที่ Memory จำกัดมาก

วิธีง่ายกว่า (O(n) Time, O(n) Space)

string transform(const string& s) {
    string even, odd;
    for (int i = 0; i < s.size(); i++) {
        if (i % 2 == 0) even += s[i];
        else odd += s[i];
    }
    return even + odd;
}