数的全排列 - 深度优先搜索

青旅半醒 2023-02-09 13:15 3阅读 0赞

#  数的全排列 - 深度优先搜索 #

## 1. 123 的全排列 (3! = 3 \* 2 \* 1 = 6) ##

123、132、213、231、312、321。

## 2. 1234 的全排列 (4! = 4 \* 3 \* 2 \* 1 = 24) ##

1234、1243、1324、1342、1423、1432，  
2134、2143、2314、2341、2413、2431，  
3124、3142、3214、3241、3412、3421，  
4123、4132、4213、4231、4312、4321。

## 3. 123 全排列，三重循环嵌套 ##

使用 `for a` 循环枚举第 1 位，使用 `for b` 循环枚举第 2 位，使用 `for c` 循环枚举第 3 位。`if` 语句进行判断，只有当 `a`、`b` 和 `c` 互不相等的时候才能输出。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]

## 4. 1234 全排列，四重循环嵌套 ##

使用 `for a` 循环枚举第 1 位，使用 `for b` 循环枚举第 2 位，使用 `for c` 循环枚举第 3 位，使用 `for d` 循环枚举第 4 位。`if` 语句进行判断，只有当 `a`、`b`、`c` 和 `d` 互不相等的时候才能输出。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]

## 5. 深度优先搜索 (不撞南墙不回头) ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 4]

每一个小盒子都可能放 1 号、2 号或者 3 号扑克牌，需要一一尝试，`for` 循环解决。

for (int i = 1; i <= N; i++)
    {
    	// 将 i 号扑克牌放入到第 step 个盒子中
    	a[step] = i;
    }

数组 `a` 是用来表示小盒子的，变量 `step` 表示当前正处在第 `step` 个小盒子面前。`a[step] = i;` 就是将第 `i` 号扑克牌放入到第 `step` 个盒子中。如果一张扑克牌已经放到别的小盒子中了，那么此时就不能再放入同样的扑克牌到当前小盒子中，因为此时手中已经没有这张扑克牌了。因此还需要一个数组 `book` 来标记哪些牌已经使用了。

for (int i = 1; i <= N; i++)
    {
    	// book[i] 等于 0 表示 i 号扑克牌仍然在手上
    	if (0 == book[i])
    	{
    		// 将 i 号扑克牌放入到第 step 个盒子中
    		a[step] = i;
    		// 将 book[i] 设为 1，表示 i 号扑克牌已经不在手上
    		book[i] = 1;
    	}
    }

现在已经处理完第 `step` 个小盒子了，接下来需要往下走一步，继续处理第 `step + 1` 个小盒子。处理方法其实和我们刚刚处理第 `step` 个小盒子的方法是相同的。把刚才的处理第 `step` 个小盒子的代码封装为一个函数，我们为这个函数起个名字，就叫做 `dfs`。

在处理完第 `step` 个小盒子之后，紧接着处理第 `step + 1` 个小盒子，处理第 `step + 1` 个小盒子的方法就是 `dfs(step + 1)`。

// step 表示现在站在第几个盒子面前
    void dfs(int step) 
    {
    	for (int i = 1; i <= N; i++)
    	{
    		// 判断扑克牌 i 是否还在手上，book[i] 等于 0 表示 i 号扑克牌仍然在手上
    		if (0 == book[i])
    		{
    			// 将 i 号扑克牌放入到第 step 个盒子中
    			a[step] = i;
    			// 将 book[i] 设为 1，表示 i 号扑克牌已经不在手上
    			book[i] = 1;
    			// 通过函数的递归调用来实现 (自己调用自己)
    			dfs(step + 1);
    			// 一定要将刚才尝试的扑克牌收回，才能进行下一次尝试
    			book[i] = 0;
    		}
    	}
    }

上面代码中的 `book[i] = 0` 非常重要，这句话的作用是将小盒子中的扑克牌收回。在一次摆放尝试结束返回的时候，如果不把刚才放入小盒子中的扑克牌收回，那将无法再进行下一次摆放。其实当我们处理到第 `N + 1` 个小盒子的时候 (即 `step` 等于 `N + 1`)，那么说明前 `N` 个盒子都已经放好扑克牌了，将 `1 ~ N` 个小盒子中的扑克牌编号打印出来就可以了。打印完毕一定要立即 `return`。

// step 表示现在站在第几个盒子面前
    void dfs(int step)
    {
    	// 如果站在第 N + 1 个盒子面前，则表示前 N 个盒子已经放好扑克牌
    	if ((N + 1) == step)
    	{
    		// 输出一种排列 (1~N 号盒子中的扑克牌编号)
    		for (int i = 1; i <= N; i++)
    		{
    			cout << a[i];
    		}
    		// 返回之前的一步 (最近一次调用 dfs 函数的地方)
    		return;
    	}
    
    	for (int i = 1; i <= N; i++)
    	{
    		// 判断扑克牌 i 是否还在手上，book[i] 等于 0 表示 i 号扑克牌仍然在手上
    		if (0 == book[i])
    		{
    			// 将 i 号扑克牌放入到第 step 个盒子中
    			a[step] = i;
    			// 将 book[i] 设为 1，表示 i 号扑克牌已经不在手上
    			book[i] = 1;
    			// 通过函数的递归调用来实现 (自己调用自己)
    			dfs(step + 1);
    			// 一定要将刚才尝试的扑克牌收回，才能进行下一次尝试
    			book[i] = 0;
    		}
    	}
    }

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    // 全局变量默认值为 0，不必再次赋初始值 0
    int a[10] = { 0 };
    int book[10] = { 0 };
    int N = 0;
    
    // step 表示现在站在第几个盒子面前
    void dfs(int step)
    {
    	// 如果站在第 n + 1 个盒子面前，则表示前 n 个盒子已经放好扑克牌
    	if ((N + 1) == step)
    	{
    		// 输出一种排列 (1~N 号盒子中的扑克牌编号)
    		for (int i = 1; i <= N; i++)
    		{
    			cout << a[i];
    		}
    		cout << endl;
    
    		// 返回之前的一步 (最近一次调用 dfs 函数的地方)
    		return;
    	}
    
    	// 按照 1, 2, 3, ...N 的顺序一一尝试
    	for (int i = 1; i <= N; i++)
    	{
    		// 判断扑克牌 i 是否还在手上，book[i] 等于 0 表示 i 号扑克牌仍然在手上
    		if (0 == book[i])
    		{
    			// 将 i 号扑克牌放入到第 step 个盒子中
    			a[step] = i;
    			// 将 book[i] 设为 1，表示 i 号扑克牌已经不在手上
    			book[i] = 1;
    			// 第 step 个盒子已经放好扑克牌，接下来走到下一个盒子面前
    			// 通过函数的递归调用来实现 (自己调用自己)
    			dfs(step + 1);
    			// 一定要将刚才尝试的扑克牌收回，才能进行下一次尝试
    			book[i] = 0;
    		}
    	}
    
    	return;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int start_num = 1;
    
    	// 输入 [1, 9] 之间的整数 N
    	cin >> N;
    
    	dfs(start_num);
    
    	end = clock();
    	printf("\nEnd of the program, end_t = %ld\n", end);
    	printf("End of the program, end_t = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 5]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 6]

上面的例子是深度优先搜索 (Depth First Search，DFS) 的基本模型，理解深度优先搜索的关键在于解决“当下该如何做”，至于“下一步如何做”则与“当下该如何做”是一样的，上面 `dfs(step)` 这个函数就是为了解决当你在第 `step` 个箱子面前的时候，你会怎么放扑克牌或者结束了投放操作，下一步也是这样的操作。如果要遍历所有的可能性，可以用 `for` 循环来遍历所有的可能性。当前的步骤 `step` 完成后就进入下一个 `step` (`step = step + 1`)，下一步的解决办法和当前的解决办法是一致的。

**将使用的数据作为函数参数传递，可以减少写代码时遗漏数据的情况，尽量将数据作为 DFS 的参数传递。**

void dfs(int step)
    {
    	STEP 1. 判断边界，返回
    
        STEP 2. 剪枝，减少计算量
    
    	STEP 3. 尝试每一种可能
    	for (int i = 1; i <= N; i++)
    	{
    		// 继续下一步 
    		// 标记
    		dfs(step + 1);
    		// 撤销标记
    	}
    
    	STEP 4. 返回
    }

每一种尝试就是一种扩展。每次站在一个盒子面前的时候，其实都有 `N` 种扩展方法，但是并不是每种扩展都能够扩展成功。

## 6. master ##

数的全排列，N 个数字全排列，组成 N! = N \* (N - 1) \* (N - 2) \* … \* 3 \* 2 \* 1。  
3! = 3 \* 2 \* 1 = 6  
4! = 4 \* 3 \* 2 \* 1 = 24

//============================================================================
    // Name        : Yongqiang Cheng
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2020 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    #ifndef _CRT_SECURE_NO_WARNINGS
    #define _CRT_SECURE_NO_WARNINGS
    #endif
    
    #include <iostream>
    
    const int MAX_NUM = 10;
    
    int book[MAX_NUM] = { 0 };  // init()
    int order_nums[MAX_NUM] = { 0 };  // init()
    
    void forward_dfs(int step, const int N, const int *nums, int *book, long long *psum, int *order_nums)
    {
    	// 0 1 2 ... N-1 N
    	if (step >= N)
    	{
    		long long number = 0;
    		for (int n = 0; n < N; ++n)
    		{
    			std::cout << order_nums[n] << " ";
    			number = number * 10 + order_nums[n];
    		}
    		std::cout << std::endl;
    
    		*psum += number;
    
    		return;
    	}
    
    	for (int i = 0; i < N; ++i)
    	{
    		if (0 == book[i])
    		{
    			order_nums[step] = nums[i];
    			book[i] = 1;
    			forward_dfs(step + 1, N, nums, book, psum, order_nums);
    			book[i] = 0;
    		}
    	}
    
    	return;
    }
    
    long long permutation_summation(const int N, const int *nums)
    {
    	int step = 0;
    	long long sum = 0;
    	for (int i = 0; i < MAX_NUM; ++i)
    	{
    		book[i] = 0;
    	}
    
    	forward_dfs(step, N, nums, book, &sum, order_nums);
    
    	return sum;
    }
    
    int main()
    {
    	long long summation;
    	int N = 3;
    	const int nums[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    
    	summation = permutation_summation(N, nums);
    
    	std::cout << "{ 1, 2, 3 } -> " << summation << std::endl;
    	std::cout << std::endl;
    
    	N = 2;
    
    	summation = permutation_summation(N, nums);
    
    	std::cout << "{ 1, 2 } sum = 12 + 21 = 33-> " << summation << std::endl;
    	std::cout << std::endl;
    
    	N = 1;
    
    	summation = permutation_summation(N, nums);
    
    	std::cout << "{ 1 } sum = 1 -> " << summation << std::endl;
    	std::cout << std::endl;
    
    	return 0;
    }

1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 1 2
    3 2 1
    { 1, 2, 3 } -> 1332
    
    1 2
    2 1
    { 1, 2 } sum = 12 + 21 = 33-> 33
    
    1
    { 1 } sum = 1 -> 1
    
    请按任意键继续. . .

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 7]

## References ##

《啊哈！算法》 - 啊哈磊

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200518224350509.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200518225454605.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200518230817669.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200518231309380.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20200518231528848.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20200519010315752.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20200519010356665.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/202103112348061.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center