打印全排列（DFS）

超、凢脫俗 2023-03-01 08:38 76阅读 0赞

> 前言：OJ上一道简单算法题，打印全排列。用深度优先搜索（DFS）来实现，顺便记录一下基础DFS模板。

#### 题目描述 ####

给定一个正整数n，取出前n小的正整数，即 1~n 这n个数字，将他们全排列，一共有 n！中排列方案，要求输出全部的排列方案。  
输入一个n（2 <= n <= 7），输出 n！个排列方案

#### 算法思路 ####

使用深度优先搜索打印排列数，深度优先搜索基本模型如下：

void dfs(int step)
    {
        
        1.判断边界条件
        2.尝试每一种可能
        for(int i = 1; i <=n; i++) {
        
            3.继续下一步
            dfs(step + 1);
        }
        4.返回
    }

#### 代码实现 ####

下面就结合深度优先搜索的模板，来实现具体的全排列打印，如下：

/* @Author Caso_卡索
     * @Date   2020/7/22
     * @Func   打印全排列（DFS）
     */
    #include <iostream>
    using namespace std;
    #define NUMSIZE 8
    
    class Permutation
    {
        
    public:
        Permutation(int input)
        {
        
            this -> n = input;
        }
        void dfs(int position)
        {
        
    	    // 当排列到 n + 1 位置时，完成一次排列，打印
    	    if(position == n+ 1) {
        
    	        for(int i = 1; i <= n; i++) {
        
    	            cout << instance[i] << " ";
    	        }
    	        cout << endl;
    	    }
    	    for(int i = 1; i <= n; i++) {
        
    	        if(status[i] == 0) {
        
    	            instance[position] = i;
    	            status[i] = 1;        // 说明 i 刚被排列
    	            dfs(position + 1);    // 下探，继续排列下一个位置的数字
    	            status[i] = 0;        // 恢复 i 的状态，下次排列使用
    	        }
    	    }
        }
        ~Permutation(){
        }
    private:
        /* @Param n: 输入一个正整数
         * @Param instance: 存储一个排列数
         * @Param status: 保存每次排入数字的状态值
         */
    	int n;
    	int instance[NUMSIZE] = {
        0};
    	int status[NUMSIZE] = {
        0};
    };
    
    int main()
    {
        
        int N;
        cin >> N;
        if(N < 1 || N > 7) {
        
            cout << "Input 1~7 !" << endl;
            return 0;
        }
        Permutation permutate(N);
        permutate.dfs(1);    // 从第一个数字开始排列
        return 0;
    }

程序运行结果如下：  
![结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9tYV8yMDE4_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9tYV8yMDE4_size_16_color_FFFFFF_t_70]: /images/20230209/91bfece39c504cc2a4c81539931a45a8.png