一起学习交流~

全排列

算法 laomuji 9个月前 (12-23) 545次浏览 已收录 0个评论

一、什么是全排列

全排列有两种情况,无重复和有重复
全排列一般使用DFS 时间复杂度很高为n!
建议先看全子集,搞定后再写这个会很简单

1 2 3
结果如下
[123]
[132]
[213]
[231]
[312]
[321]
不会造成死循环
比如有三层
第一层生成第二层
第二层生成第三层
第三层加入数据
1->2->3
1->3->2
2->1->3
2->3->1
3->1->2
3->2->1
但时间复杂度会很高

二、全排列具体实现

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void permutationsDFS(vector<vector<int>>& results, vector<int>& nums, vector<bool>& select, vector<int> result = vector<int>()) {
    if (result.size() == nums.size()) {
        results.push_back(result);//长度相等表示可以加入了
        return;
    }
    for (size_t i = 0; i < nums.size(); i++)
    {

        //若当前数字已经被选中了(此时该数字一定在result数组里)
        if (select[i] == 1) continue;

        //去除重复情况,如果不需要去重复,可以把这行代码去掉
        //select[i - 1]==0或者select[i - 1]==1的情况任取其一,都是正确答案
        //我没选,上一个也没选,那就表示我们是同一层的,同一层相同,那就是重复
        if (i != 0 && nums[i] == nums[i - 1] && select[i - 1]==0) {
            continue;
        }

        //此时是当前数字不在result数组的情况
        //需要把该数字放入数组,然后进行递归
        select[i] = 1;//标记选中
        result.push_back(nums[i]);//把当前数字加入结果数组
        permutationsDFS(results, nums, select, result);
        result.pop_back();//递归完毕移除当前数组
        select[i] = 0;//恢复未选中
    }
    return;
}
vector<vector<int>>permutations(vector<int>&nums) {
    vector<vector<int>>results;
    if (nums.size() == 0) {
        //空排列有一个空排列
        results.push_back(vector<int>());
        return results;
    }
    sort(nums.begin(), nums.end());
    vector<bool>select;
    for (size_t i = 0; i < nums.size(); i++)select.push_back(0);
    permutationsDFS(results, nums, select);
    return results;
}
int main() {
    vector<int>nums = { 1,2,3 };
    auto results = permutations(nums);
    for (size_t i = 0; i < results.size(); i++)
    {
        cout << "[";
        for (size_t j = 0; j < results[i].size(); j++)
        {
            cout << results[i][j];
        }
        cout << "]" << endl;
    }
    return 0;
}
喜欢 (1)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论