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

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

อัลกอริธึม

1. กำหนดอาร์เรย์จำนวนเต็ม elements[]
2. รับจำนวนข้อมูล e จากผู้ใช้
3. ใส่ค่าลงในอาร์เรย์ elements[] จำนวน e ค่า
4. เรียงลำดับอาร์เรย์ทั้งหมด (จากน้อยไปมาก)
5. กลับลำดับอาร์เรย์ (กลายเป็นจากมากไปน้อย - เริ่มจาก permutation สุดท้าย)
6. ทำซ้ำ:
   • แสดงเนื้อหาอาร์เรย์ปัจจุบัน
7. จนกว่า prev_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);
    reverse(elements, elements + e);
    cout << "The " << e << "! possible permutations with " << e << " elements: " << endl;
    do {
        show(elements, e);
    } while (prev_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: 10
Enter 4 element: 2
The 4! possible permutations with 4 elements:
10 7 6 2
10 7 2 6
10 6 7 2
10 6 2 7
10 2 7 6
10 2 6 7
7 10 6 2
7 10 2 6
7 6 10 2
7 6 2 10
7 2 10 6
7 2 6 10
6 10 7 2
6 10 2 7
6 7 10 2
6 7 2 10
6 2 10 7
6 2 7 10
2 10 7 6
2 10 6 7
2 7 10 6
2 7 6 10
2 6 10 7
2 6 7 10

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