home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Lexicographically Next Permutation ใน C++: std::next_permutation

Lexicographically Next Permutation คือ Permutation (การเรียงสับเปลี่ยน) ที่มาถัดไปในลำดับ Dictionary Order (Lexicographical Order) ใน C++ มีฟังก์ชันสำเร็จรูป std::next_permutation ใน Header <algorithm>

ลายเซ็น

template <class BidirIt>
bool next_permutation(BidirIt first, BidirIt last);

template <class BidirIt, class Compare>
bool next_permutation(BidirIt first, BidirIt last, Compare comp);
  • คืน true หากมี Permutation ถัดไป (และแก้ไข Range ให้เป็น Permutation ถัดไป)
  • คืน false หากอยู่ที่ Permutation สุดท้ายแล้ว (Descending Order) และ Reset Range ให้เป็น Permutation แรก (Ascending Order)
  • ต้องการ Bidirectional Iterator (Array, Vector, List, String, Deque)

ตัวอย่างพื้นฐาน

#include <iostream>
#include <algorithm>
#include <string>

int main() {
    std::string s = "DBAC";
    
    std::cout << "All permutations of " << s << ":\n";
    // ต้อง Sort ก่อนเพื่อเริ่มจาก Permutation แรก
    std::sort(s.begin(), s.end()); // "ABCD"
    
    do {
        std::cout << s << '\n';
    } while (std::next_permutation(s.begin(), s.end()));
    
    return 0;
}

ผลลัพธ์

ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAB
CDBA
DABC
DACB
DBAC
DBCA
DCAB
DCBA

การใช้งานแบบไม่ Sort ก่อน (จากสถานะปัจจุบัน)

std::string s = "DBAC";
for (int i = 0; i < 5; ++i) {
    bool has_next = std::next_permutation(s.begin(), s.end());
    if (!has_next) {
        std::cout << "No next permutation (at: " << s << ")\n";
        break;
    }
    std::cout << "Next: " << s << '\n';
}
// Output:
// Next: DBCA
// Next: DCAB
// Next: DCBA
// No next permutation (at: ABCD) <- Reset ไปที่ First

อัลกอริทึมเบื้องหลัง (How it Works)

  1. หา Pivot: Index i สุดท้ายที่ s[i] < s[i+1] (Scan จากขวา)
  2. หา Successor: Index j สุดท้ายที่ s[j] > s[i]
  3. Swap s[i] และ s[j]
  4. Reverse Sub-range [i+1, end)

Complexity: O(N) Amortized

ฟังก์ชันคู่: prev_permutation

หา Permutation ก่อนหน้า (Previous) ทำงานกลับกัน

การประยุกต์ใช้

  • Generate All Permutations สำหรับ Brute-force Search
  • Combinatorial Algorithms (TSP, Scheduling)
  • Next Lexicographical String/Number
  • Testing: Generate Test Cases ทุก Combination

ข้อระวัง

  • ต้อง #include <algorithm>
  • Container ต้องรองรับ Bidirectional Iterator (ไม่รองรับ forward_list)
  • หากมี Duplicate Elements จะสร้าง Permutation ซ้ำ (ใช้ std::unique กรองได้)
  • สำหรับ String ต้องเป็น Mutable (Non-const)

สรุป

std::next_permutation เป็นเครื่องมือมาตรฐานที่มีประสิทธิภาพสำหรับการ Generate Permutation ตามลำดับ Lexicographical ใช้งานง่ายด้วย Iterator Pattern เข้าใจอัลกอริทึมเบื้องหลังช่วย Debug และประยุกต์ต่อได้