พิมพ์พีชคณิตทั้งหมดของสตริงที่กำหนด

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

ตัวอย่างเช่น หากสตริงเป็น ABC การเรียงสับเปลี่ยนทั้งหมดจะเป็น ABC, ACB, BAC, BCA, CAB, CBA

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

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

Input:
A string “ABC”
Output:
All permutations of ABC is:
ABC
ACB
BAC
BCA
CBA
CAB

อัลกอริทึม

stringPermutation(str, left, right)

ป้อนข้อมูล: สตริงและดัชนีซ้ายและขวาของอักขระ

ผลลัพธ์: พิมพ์พีชคณิตทั้งหมดของสตริง

Begin
   if left = right, then
      display str
   else
      for i := left to right, do
         swap str[left] and str[i]
         stringPermutation(str, left+1, right)
         swap str[left] and str[i]             //for backtrack
      done
End

ตัวอย่าง

#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 back for 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