โปรแกรม C พิมพ์การเรียงสับเปลี่ยนทั้งหมดของสตริงที่กำหนด

ในปัญหานี้ เราได้รับสตริง งานคือสร้างโปรแกรม C เพื่อพิมพ์การเรียงสับเปลี่ยนทั้งหมดของสตริงที่กำหนด

โปรแกรมนี้จะหาการจัดเรียงที่เป็นไปได้ทั้งหมดของสตริงที่กำหนดและพิมพ์ออกมา

การเรียงสับเปลี่ยน (Permutation) คือการจัดเรียงทุกส่วนของวัตถุในทุกคำสั่งการจัดเรียงที่เป็นไปได้

ตัวอย่างเพื่อเข้าใจปัญหา

อินพุต

xyz

เอาต์พุต

xyz, xzy, yxz, yzx, zxy, zyx

คำอธิบาย

นี่คือการเรียงสับเปลี่ยนทั้งหมดตามลำดับ

เพื่อแก้ปัญหานี้ เราจะใช้การย้อนกลับ (backtracking) คือนำแต่ละตัวอักษรของสตริงมาเป็นตัวอักษรแรกของการเรียงสับเปลี่ยน และจากนั้นเลือกตัวอักษรที่เหลือของสตริงทีละตัวตามลำดับ และดังนั้นพิมพ์การเรียงสับเปลี่ยนทั้งหมดของสตริง

โปรแกรมพิมพ์การเรียงสับเปลี่ยนทั้งหมดของสตริงที่กำหนด

// โปรแกรมพิมพ์การเรียงสับเปลี่ยนทั้งหมดของสตริงที่กำหนด

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

void findPermutations(string str, int l, int r) {
    if (l == r)
        cout << str << " ";
    else {
        for (int i = l; i <= r; i++) {
            swap(str[l], str[i]);
            findPermutations(str, l + 1, r);
            swap(str[l], str[i]);
        }
    }
}

int main() {
    string str = "WXYZ";
    int n = str.size();
    findPermutations(str, 0, n - 1);
    return 0;
}

ผลลัพธ์

WXYZ WXZY WYXZ WYZX WZYX WZXY XWYZ XWZY XYWZ XYZW XZYW XZWY YXWZ YXZW YWXZ YWZX YZWX YZXW ZXYW ZXWY ZYXW ZYWX ZWYX ZWXY