โปรแกรม C++ สำหรับการใช้งาน Next_Permutation ใน STL

next_permutation ใน STL ใช้สำหรับจัดเรียงใหม่ขององค์ประกอบในช่วง [first, last] ให้เป็นการเรียงลำดับแบบเล็กซิโคกราฟิก (lexicographically) ที่มากกว่าปัจจุบัน การเรียงแต่ละแบบ (permutation) เป็นหนึ่งใน N! แบบจัดเรียงที่เป็นไปได้

อัลกอริธึม

1. กำหนดอาร์เรย์จำนวนเต็ม elements[]
2. รับจำนวนข้อมูล e จากผู้ใช้
3. ใส่ค่าลงในอาร์เรย์ elements[] จำนวน e ค่า
4. เรียงลำดับอาร์เรย์ทั้งหมด (จากน้อยไปมาก - เริ่มจาก permutation แรก)
5. ทำซ้ำ:
   • แสดงเนื้อหาอาร์เรย์ปัจจุบัน
6. จนกว่า next_permutation(elements, elements + e) จะคืนค่า false

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

#include <iostream>
#include <algorithm>
using namespace std;

void show(int a[], int n) {
    for(int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

int main() {
    int e, i;
    cout << "Enter number of elements to be inserted: ";
    cin >> e;
    int elements[e];
    for (i = 0; i < e; i++) {
        cout << "Enter " << i + 1 << " element: ";
        cin >> elements[i];
    }
    sort(elements, elements + e);
    cout << "The " << e << "! possible permutations with " << e << " elements: " << endl;
    do {
        show(elements, e);
    } while (next_permutation(elements, elements + e));
    return 0;
}

ตัวอย่างผลลัพธ์

Enter number of elements to be inserted: 4
Enter 1 element: 7
Enter 2 element: 6
Enter 3 element: 2
Enter 4 element: 10
The 4! possible permutations with 4 elements:
2 6 7 10
2 6 10 7
2 7 6 10
2 7 10 6
2 10 6 7
2 10 7 6
6 2 7 10
6 2 10 7
6 7 2 10
6 7 10 2
6 10 2 7
6 10 7 2
7 2 6 10
7 2 10 6
7 6 2 10
7 6 10 2
7 10 2 6
7 10 6 2
10 2 6 7
10 2 7 6
10 6 2 7
10 6 7 2
10 7 2 6
10 7 6 2

สรุป: เริ่มจาก permutation แรก (เรียงน้อยไปมาก) แล้วเพิ่มขึ้นเรื่อยๆ จนถึง permutation สุดท้าย (เรียงมากไปน้อย) รวมทั้งหมด N! แบบ

ความแตกต่างจาก prev_permutation: next_permutation เริ่มจากน้อยไปมาก (sort แล้ว) ส่วน prev_permutation เริ่มจากมากไปน้อย (sort แล้ว reverse)