416-回溯算法-排列树

待我称王封你为后i 2022-09-05 01:39 186阅读 0赞

## 解空间-排列树的理论 ##

**原始序列的全排列。不同的排列方式。**  
比如说1234有很多排列方式，所有的排列方式中，可能只有其中几种排列方式才满足题目的要求。

**举个例子：**  
**我们现在想获取1,2，3,4的全排列**  
枚举法  
**就是每个元素在各个位置上都出现1遍！**  
![在这里插入图片描述][efe22611daa64981973909b871a4fe8b.png]  
**我们现在处理的是第一个位置上的元素，我们拿第一个位置上的元素和每个位置上的元素交换一下，如下图。**  
![在这里插入图片描述][b6f026c242024adabe55d80210d3bbc6.png]  
**也可以这么说：我们先处理第1个位置的元素，我拿第一个位置的元素和每个位置的元素交换一下，这样就可以把每一个元素都在我第一个位置都出现1遍！**  
**首先，我们从第1个位置开始。**  
**第一个位置可以放1，剩下的就是2, 3，4  
第一个位置还可以放2，剩下的就是1, 3，4  
第一个位置还可以放3，剩下的就是2, 1，4  
第一个位置还可以放4，剩下的就是2, 3，1**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]  
我们看根节点的左边第一个孩子的处理  
**现在相当于把第1个位置（元素1）处理完了。然后接下来看第2个位置。**  
**然后在1的位置基础上。拿2和2交换。拿2和3交换。拿2和4交换。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]  
**以此类推下去。** 我们看根节点的左边第二个孩子的处理。  
相当于是第一个位置是确定了，即元素2确定了，我们拿第二个位置的元素1和后面两个元素依次交换位置。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]  
**我们在最左的一个节点上，已经解决了前2位的交换。现在前2个固定下来，然后处理3,4位。3和3交换。3和4交换。然后处理第4个位置，4和4交换。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]  
**现在最下面这层是前3个元素都固定好了。剩下最后1个元素。就自己和自己交换了。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]  
一个叶子节点代表根节点的其中一个孩子（原序列的一种排列方式）的所有排列的可能。

**所有叶子节点的总和就是原序列的全部排列方式。**  
**这样，逻辑上构建出来的解空间树就是排列树了。**

**原始序列的元素个数是n个的话，有n！个叶子节点。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]  
**从上到下，依次少1叉！直到叶子节点是1叉。  
排列树的时间复杂度：O(n!)**

## 解空间-排列树的代码实现 ##

**我们考虑问题是考虑一层的，考虑的是水平的，递归负责的是垂直。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]

/*
    解空间-排列树代码
    */
    void swap(int arr[], int i, int j)//交换值
    {
        
    	int tmp = arr[i];
    	arr[i] = arr[j];
    	arr[j] = tmp;
    }
    void func(int arr[], int i, int length)
    {
        
    	if (i == length)//跑到一个叶子节点上了
    	{
        
    		for (int j = 0; j < length; ++j)
    		{
        
    			cout << arr[j] << " ";
    		}
    		cout << endl;
    	}
    	else
    	{
        
    		//生成当前i节点的所有孩子节点
    		for (int k = i; k < length; ++k)
    		{
        
    			swap(arr, i, k);//当前i位置的元素和后边所有元素交换
    			func(arr, i + 1, length);//遍历i的一个孩子
    			swap(arr, i, k);
    			//回溯到父节点，一定要再交换回来，因为生成新的孩子是基于父节点进行元素的交换
    		}
    	}
    }
    int main()
    {
        
    	int arr[] = {
         1,2,3,4 };
    	int length = sizeof(arr) / sizeof(arr[0]);
    	func(arr, 0, length);
    
    	return 0;
    }

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

[efe22611daa64981973909b871a4fe8b.png]: /images/20220829/a02d98d03b4f4cfcab43dfddf714e4dc.png
[b6f026c242024adabe55d80210d3bbc6.png]: /images/20220829/6f1e8076620b4252b442baa9bb9ce036.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/fdadbffe0347431895258597f23fb24d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/da0a98bb861f4aa488c8a577a9933fb5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 2]: /images/20220829/67729d2069fa43b8a20d712554c5de84.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 3]: /images/20220829/c326dd926cac4b4ab168d2b8e7889f64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 4]: /images/20220829/01a8cc88054f4e289677a6c1f155f7bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 5]: /images/20220829/13a2dc8a37d84568870cfae3a0fe8a9a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/ae7c2619e7344ec784eb4e73ceda2bfa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 6]: /images/20220829/cbc0ac7660bf4fb491016574e0064940.png