深入了解next_permutation()

一、函數介紹

next_permutation()是C++ STL中的一個函數，其作用是將一個排列變成其下一個排列，如果當前排列為最後一個排列，則將其變成第一個排列。

    bool next_permutation(first, last, cmp);

其中，first和last是迭代器，即需要排序的區間；cmp是函數對象，用於比較元素的大小。

二、函數原理

我們以”123″進行舉例，其全排列為”123″, “132”, “213”, “231”, “312”, “321”。

next_permutation()首先從最後一個元素開始向前找，找到第一個降序的元素，即找到”2″。然後再從後往前找到第一個比這個數字大的數字，即找到”3″。然後將兩個數字交換，得到”1332″。最後再將”2331″反轉得到”2313″。

    1 2 3 -> 1 3 2 -> 2 1 3 -> 2 3 1 -> 3 1 2 -> 3 2 1
          -> 1 2 3    -> 1 2 3   -> 1 2 3   -> 1 2 3

三、代碼示例

下面是一個使用next_permutation()的示例代碼，對數組進行全排列並輸出。

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

int main() {
    int arr[] = {1, 2, 3};
    sort(arr, arr+3);  // 需要先將數組排序
    do {
        for (int i = 0; i < 3; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    } while (next_permutation(arr, arr+3));
    return 0;
}

四、使用自定義比較函數

在上述示例中，使用了默認的less作為函數對象進行比較。實際上，我們可以使用自定義的比較函數進行元素的排序。

比如我們想要按照方案的總和從小到大進行排序。

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

struct Plan {
    int id;
    int sum;
    bool operator < (const Plan& p) const {
        return sum < p.sum;
    }
} plans[] = {{1, 100}, {2, 120}, {3, 90}};

int main() {
    sort(plans, plans+3);
    do {
        for (int i = 0; i < 3; i++) {
            cout << plans[i].id << " ";
        }
        cout << endl;
    } while (next_permutation(plans, plans+3));
    return 0;
}

五、使用next_permutation()進行字符串的排列組合

除了數組的全排列，next_permutation()同樣適用於字符串的排列組合。

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

int main() {
    string str = "abc";
    sort(str.begin(), str.end());
    do {
        cout << str << endl;
    } while (next_permutation(str.begin(), str.end()));
    return 0;
}

輸出結果：

abc
acb
bac
bca
cab
cba

六、總結

本文主要介紹了next_permutation()函數的使用以及原理。通過使用該函數，可以很方便地對一個數組、字符串進行全排列、排列組合等操作。