用C++求全排列的几种方法

交换法

交换法的优点：不需要额外的标记数组，空间复杂度更低，代码更简洁。需要注意的是，这个方式生成的全排列并非是字典序。

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

int arr[10] = {0, 1, 2, 3, 4};

void dfs(int x) {
    if (x > 4) {
        for (int i = 1; i <= 4; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
        return;
    }

    for (int i = x; i <= 4; i++) {
        swap(arr[x], arr[i]);    // 交换当前位置和后续位置
        dfs(x + 1);              // 递归处理下一个位置
        swap(arr[x], arr[i]);    // 回溯，交换回来
    }
}

int main() {
    dfs(1);
    return 0;
}

标记数组法

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

int res[10],arr[10] = {0, 1, 2, 3, 4};
bool used[10];

void dfs(int x){
    if(x>4){
        for(int i=1;i<=4;i++)cout << res[i] << " ";
        cout << endl;
        return;
    }
    for(int i=1;i<=4;i++){
        if(!used[i]){
            used[i]=true;
            res[x]=arr[i];
            dfs(x+1);
            used[i]=false;
        }
    }
}

int main(){
    dfs(1);
}

结果对比

全排列的STL标准库实现

std::next_permutation 是 C++ 标准库 <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 );

参数说明

first, last: 要生成排列的序列的起始和末尾迭代器（通常用 begin(), end()）。
comp: 自定义的比较函数对象，用于定义“小于”的概念。

返回值

true: 如果成功生成下一个更大的排列。
false: 如果当前序列已经是最大的排列（即降序排列）。此时，函数会将序列重置为最小的排列（即升序排列）。

核心特性

会修改原序列：该函数是原地操作的，会直接改变传入的容器。
需要序列有序：为了生成所有排列，通常需要先对序列进行升序排序。
重复元素：函数能够正确处理序列中的重复元素，不会生成重复的排列。

应用于vector：

#include <iostream>
#include <vector>
#include <algorithm> // 包含 next_permutation

using namespace std;

int main() {
    vector<int> vec = {1, 2, 3};

    // 重要：先排序以确保从最小排列开始
    // sort(vec.begin(), vec.end()); 
    // 本例中 {1,2,3} 已经是最小排列，所以可省略排序

    cout << "All permutations of {1, 2, 3}:\n";
    
    do {
        for (int num : vec) {
            cout << num << " ";
        }
        cout << endl;
    } while (next_permutation(vec.begin(), vec.end())); 
    // 当 next_permutation 返回 false 时循环结束

    return 0;
}

应用于字符串：

#include <iostream>
#include <algorithm> // 包含 next_permutation
#include <string>

using namespace std;

int main() {
    string str = "abc";

    // 同样，如果需要所有排列，应先排序
    // sort(str.begin(), str.end());
    
    cout << "All permutations of \"abc\":\n";
    do {
        cout << str << endl;
    } while (next_permutation(str.begin(), str.end()));

    return 0;
}

处理有重复元素的序列

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> vec = {1, 1, 2};

    // 必须先排序！
    sort(vec.begin(), vec.end());

    cout << "All permutations of {1, 1, 2}:\n";
    do {
        for (int num : vec) {
            cout << num << " ";
        }
        cout << endl;
    } while (next_permutation(vec.begin(), vec.end()));

    return 0;
}

遍历所有排列：

#include <algorithm>
#include <vector>

std::vector<int> data = {3, 1, 4, 1, 5}; // 未排序的序列

// 1. 首先必须排序！
std::sort(data.begin(), data.end());

// 2. 使用 do-while 循环
do {
    // 处理当前的排列，例如打印它
    // for (auto x : data) { ... }
} while (std::next_permutation(data.begin(), data.end()));