全排列（蓝桥必备）

十二.

发布于 2025-10-22 14:44:49

850

全排列是蓝桥杯中的高频考点之一，接下来为我的学习历程：

先练习基本的全排列 -> 熟练应用后套用stl函数库->进阶练习

3、C++模板函数套用

1、全排列 - 基础练习

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

// 本题格式是，力扣的独有格式。
// 本题通过递归进行,全排列
class Solution {

    // 各处存数据的数组
    vector<vector<int>> res;
    vector<int> cur;
    void generate(vector<int>& nums, vector<bool>& userd){
        
        if(cur.size()==nums.size()){
            res.push_back(cur);
            return;
        }    
        for(int i=0; i<userd.size(); ++i){
            if(!userd[i]){ // 如果未被使用过
                userd[i] = true;
                cur.push_back(nums[i]);
                generate(nums,userd);
                cur.pop_back();
                userd[i] = false;
            }
        }
    }

public:
    vector<vector<int>> permute(vector<int>& nums) {
        res.clear();
        cur.clear();
        vector<bool> userd(nums.size(),false);
        generate(nums,userd);
        return res;
    }

};

2、全排列II - 基础练习

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

class Solution {
public:
    vector<vector<int>> res;
    vector<int> cur;
    void generate(vector<int>& nums, vector<bool>& used){
        if(cur.size()==nums.size()){
            res.push_back(cur);
            return;
        }
        for(int i = 0; i<nums.size(); i++){
            if(!used[i]){
                if(i>0&&!used[i-1]&&nums[i]==nums[i-1]) continue; // 跳过是精华核心，每次递归到同一档次的时候，就直接跳过。
                used[i]=true;
                cur.push_back(nums[i]);
                generate(nums,used);
                cur.pop_back();
                used[i]=false;
            }
        }

    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        res.clear();
        cur.clear();
        sort(nums.begin(),nums.end()); // 排序是本题基础
        vector<bool> used(nums.size(),false);
        generate(nums,used);
        return res;
    }
};

3、C++模板函数套用

在竞赛中，如果使用dfs进行全排列的话，确实非常麻烦。固，可引用tls库中的内容。

共两种用法，主要：

1、next_permutation(vec.begin(), vec.end());

2、prev_permutation(vec.begin(), vec.end());

#include "bits/stdc++.h"
using namespace std;

vector<vector<int>> res;
vector<int> cur;

void generate(vector<int>& vec, vector<bool>& used){
    if(cur.size()==vec.size()){
        res.push_back(cur);
        return;
    }

    for(int i=0; i<vec.size(); ++i){
        if(!used[i]){
            used[i]= true;
            cur.push_back(vec[i]);
            generate(vec,used);
            cur.pop_back();
            used[i]=false;
        }
    }
}


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

    // 全排列
    cout<<"------------ 以下是next_permutation生成与输出 ------------------"<<endl;

    do{
        for(int num : vec){
            cout<<num<<" ";
        }
        cout<<endl;
    }while(next_permutation(vec.begin(),vec.end()));

    cout<<"------------ 以下为手写DFS函数的输出 ------------------"<<endl;

    vector<bool> used(vec.size(), false);
    generate(vec,used);

    for(vector<int>& v : res){
        for(int num : v){
            cout<<num<<" ";
        }
        cout<<endl;
    }

    return 0;
}

下方为输出函数：

------------ 以下是next_permutation生成与输出 ------------------
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 
------------ 以下为手写DFS函数的输出 ------------------
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

4、排列序数（蓝桥真题）

题目描述

如果用 a b c d 这 4 个字母组成一个串，有 4!=24 种，如果把它们排个序，每个串都对应一个序号：

abcd 0

abdc 1

acbd 2

acdb 3

adbc 4

adcb 5

bacd 6

badc 7

bcad 8

bcda 9

bdac 10

bdca 11

cabd 12

cadb 13

cbad 14

cbda 15

cdab 16

cdba 17

⋯⋯

现在有不多于 10 个两两不同的小写字母，给出它们组成的串，你能求出该串在所有排列中的序号吗？

输入描述

输入一行，一个串。

输出描述

输出一行，一个整数，表示该串在其字母所有排列生成的串中的序号。注意：最小的序号是 0。

输入输出样例

示例

输入

bdca

输出

运行限制

最大运行时间：1s
最大运行内存: 256M

#include "bits/stdc++.h"
using namespace std;
int main(){
    string str,strx;
    cin>>str;
    strx=str;
    sort(str.begin(),str.end());

    int ans=0;
    do {
        if(strx==str){
            break;
        }
        ans++;
    }while(next_permutation(str.begin(),str.end()));
    cout<<ans<<endl;
    return 0;

----------------- 以下为本题拓展 -----------------

  1、sort 能遍历快速模板
使用了内省排序，内省排序结合了快速排序（Quicksort）、堆排序（Heapsort）
和插入排序（Insertion sort）的优点。它以快速排序为基础，在递归深度达到一定
阈值（通常是 ， 为元素数量）时，为避免快速排序在最坏情况下（ 时间复杂度）的
性能问题，会切换到堆排序；在处理小规模数据（通常是元素数量少于 16 个）时，会
使用插入排序，因为插入排序在处理小规模数据时效率较高。

  2、sort 能够排列 数组{sort(arr,arr+size)}、自定义容器、vector、deque等

5、带分数 - 真题（蓝桥真题）

带分数

题目描述

100 可以表示为带分数的形式：100 = 3 + 69258 / 714

还可以表示为：100 = 82 + 3546 / 197

注意特征：带分数中，数字 1~9 分别出现且只出现一次（不包含 0 ）。

类似这样的带分数，100 有 11 种表示法。

输入描述

从标准输入读入一个正整数 N (N<1000×1000)N (N<1000×1000)。

输出描述

程序输出该数字用数码 1~9 不重复不遗漏地组成带分数表示的全部种数。

注意：不要求输出每个表示，只统计有多少表示法！

输入输出样例

示例

输入

输出

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

int generate(const vector<int>& vec, int st, int en){
    int sum = 0;
    for(int i = st; i<=en; i++){ // 求和
        sum = sum*10 + vec[i];
    }
    return sum;
}

int main(){

    int num;
    cin >> num;
    vector<int> vec{
            1,2,3,4,5,6,7,8,9
    };

    // 排列是什么
    // 分成三个点，分别对每个点
    vector<int> num1;
    vector<int> num2;
    vector<int> num3;
    int n1,n2,n3;
    int flag = 0;
    do{ // 直接套三个循环会极其不合理。
        for(int i=0; i<vec.size()-2; ++i){
            n1 = generate(vec,0,i);
            for(int j=i+1; j<vec.size()-1; ++j){
                n2 = generate(vec,i+1,j);
                n3 = generate(vec,j+1,8);
                if(num*n3==n1*n3+n2) flag++; // 如果这里用，num == n1 + n3/n3; 是不对的，因为这样会造成精度损失
            }
        }

    }while(next_permutation(vec.begin(), vec.end()));
    cout<<flag<<endl;


    // 请在此输入您的代码
    return 0;
}

--------------------------------------------------------
     原本错误的写法，用了三重循环，这样是不合理的
--------------------------------------------------------
/*
  vector<int> num1;
  vector<int> num2;
  vector<int> num3;
  int n1,n2,n3;
  int flag = 0;
  do{
    for(int i=0; i<num.size()-2; ++i){
      num1.push_back(vec[i]);
      n1 = generate(num1);
      num2.clear();
      for(int j=i+1; j<num.size()-1; ++j){
        num2.push_back(vec[j]);
        num2 = generate(num2);
        num3.clear();
        for(int z=j+1; z<num.size(); ++z){
          num3.push_back(vec[z]);
          n3 = generate(num3);
        }
      if(n1>num) break;
      if((n1+n2/n3==num) flag++;
      }
    }

  }while(next_permutation(vec.begin(), vec.end()));
*/

--------------------------------------------------------

按照以上可基本掌握基础的全排列，方便进阶学习。

如有错误，私信我，定及时更改。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-14，如有侵权请联系 cloudcommunity@tencent.com 删除

函数