C++ การเรียงสับเปลี่ยนของสตริงที่กำหนดด้วย STL

การเรียงสับเปลี่ยน (Permutation) ของสตริงเกิดขึ้นเมื่อตัวอักษรของสตริงที่กำหนดถูกจัดเรียงใหม่ในรูปแบบใดก็ได้ ในบทช่วยสอนนี้ เราจะอภิบัติวิธีพิมพ์การเรียงสับเปลี่ยนทั้งหมดของสตริงที่กำหนดโดยใช้ Standard Template Library (STL) ของ C++ เช่น

Input : s = "ADT" Output : "ADT", "ATD", "DAT", "DTA", "TAD", "TDA" Explanation : ในผลลัพธ์ที่ให้มา สตริงทั้งหมดประกอบด้วยตัวอักษร 3 ตัวเดียวกันในสตริงของเราและเพียงแค่จัดเรียงใหม่ จึงเข้าข่ายเป็นการเรียงสับเปลี่ยนของสตริง s และนี่คือการเรียงสับเปลี่ยนทั้งหมดที่เป็นไปได้ของสตริง s

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

Rotate()

วิธีแรกคือการใช้เมธอด rotate ในวิธีนี้ เราจะใช้ฟังก์ชัน rotate ของ STL ซึ่งใช้หมุนสตริงของเรา และเราจะใช้ Recursion (การเรียกซ้ำ) เพื่อพิมพ์การเรียงสับเปลี่ยน

ตัวอย่าง

โค้ด C++ สำหรับวิธีข้างต้น

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

void permutations(string s, string ans){ 
    if(s.size() == 0) { 
        cout << ans << "\n"; 
        return; 
    } 
    for(int i = 0; i < s.size(); i++){ 
        permutations(s.substr(1), ans + s[0]); 
        rotate(s.begin(), s.begin()+1, s.end()); 
    } 
} 

int main(){ 
    string s = "ADT"; 
    permutations(s, ""); 
    return 0; 
}

ผลลัพธ์

ADT ATD DTA DAT TAD TDA

Next_Permutation

ตอนนี้เราจะใช้ฟังก์ชัน STL อีกตัวหนึ่งชื่อ next_permutation ตามชื่อ ฟังก์ชันนี้คืนค่าว่ามีการเรียงสับเปลี่ยนถัดไปของสตริงนี้หรือไม่ ถ้าไม่มี จะคืนค่า false

เนื่องจากฟังก์ชันนี้ตรวจสอบการเรียงสับเปลี่ยนถัดไป เราจึงต้องจัดเรียงสตริงแบบ Lexicographical ก่อน เพื่อให้ได้การเรียงสับเปลี่ยนทั้งหมดที่เป็นไปได้

ตัวอย่าง

โค้ด C++ สำหรับวิธีข้างต้น

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

int main(){ 
    string s = "ADT"; 
    sort(s.begin(), s.end()); 
    do{ 
        cout << s << "\n"; 
    } while(next_permutation(s.begin(), s.end())); 
    return 0; 
}

ผลลัพธ์

ADT ATD DAT DTA TAD TDA

ในโปรแกรมข้างต้น เราจัดเรียงสตริงของเรา แล้วด้วยความช่วยเหลือของฟังก์ชัน next_permutation เราพิมพ์การเรียงสับเปลี่ยนทั้งหมดที่เป็นไปได้

สรุป

ในบทช่วยสอนนี้ เราพิมพ์การเรียงสับเปลี่ยนทั้งหมดที่เป็นไปได้ของสตริงที่กำหนดด้วยความช่วยเหลือของ STL ใน C++ เรายังได้เรียนรู้โปรแกรม C++ และฟังก์ชัน STL ที่สำคัญบางอย่างและการใช้งานของพวกเขา หวังว่าจะเป็นประโยชน์