พิมพ์ Permutation ทั้งหมดของสตริง (Print All Permutations of String)

บทนำ

การพิมพ์ Permutation (การเรียงสับเปลี่ยน) ทั้งหมดของสตริงที่กำหนดเป็นตัวอย่างของปัญหา Backtracking เราจะลดขนาดของ Substring เพื่อแก้ Sub-problems แล้ว Backtrack กลับมาเพื่อหา Permutation อื่นจากส่วนนั้น

ตัวอย่าง: ถ้าสตริงคือ ABC, Permutation ทั้งหมดคือ ABC, ACB, BAC, BCA, CAB, CBA

Complexity ของอัลกอริทึมนี้คือ O(n!) เป็น Complexity สูงมาก เมื่อขนาดสตริงเพิ่มขึ้น จะใช้เวลานานมากในการทำงาน

อินพุตและเอาต์พุต

Input: สตริง "ABC"
Output: All permutations of ABC is: ABC ACB BAC BCA CBA CAB

อัลกอริทึม

stringPermutation(str, left, right)
Input: สตริง และ left และ right index ของตัวอักษร
Output: พิมพ์ Permutation ทั้งหมดของสตริง

Begin
    if left = right, then
        display str
    else
        for i := left to right, do
            swap str[left] และ str[i]
            stringPermutation(str, left+1, right)
            swap str[left] และ str[i]  // สำหรับ backtrack
        done
End

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

#include <iostream>
using namespace std;

void stringPermutation(string str, int left, int right) {
    if (left == right)
        cout << str << endl;
    else {
        for (int i = left; i <= right; i++) {
            swap(str[left], str[i]);
            stringPermutation(str, left + 1, right);
            swap(str[left], str[i]);  // swap กลับเพื่อ backtracking
        }
    }
}

int main() {
    string str = "ABC";
    cout << "All permutations of " << str << " is: " << endl << endl;
    stringPermutation(str, 0, str.size()-1);
}

ผลลัพธ์

All permutations of ABC is:
ABC
ACB
BAC
BCA
CBA
CAB