经典算法之——解决全排列问题以及详解

墨蓝 2023-09-27 23:38 83阅读 0赞

#### 文章目录 ####

*  全排列解析
 *  一、回溯法
 *  二、字典序法
 *  三、相邻对换法

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

## 全排列解析 ##

**1.这里就举例array=\{1,2,3,4,5\}的全排列；首先根据字典的排序以小到大，将整个问题分解为子集合解决（整个感觉有点像树的结果，根分到叶子），我们现在要先固定第一位，然后变成了array1=\{2,3,4,5\}的全排列，然后就一直进行分解直到array2=\{3,4,5\}(`固定前两位`),array3=\{4,5\}(`固定前三位`)，array4=\{5\}(`固定前四位`)，到这时这里的第一次全排列，就分解到只有一个数的子集合，就算一种情况；  
2.接下来就返回到上一种情况，也就是array3的子集合，因为刚刚只是排了最后一个子集合（`array4`），所以array3子集合就要变成\{5,4\},这里算一种，到这里array3的所有可能已经完了，再接下来会回到上一个集合array2的可能`{3,4,5},{3,5,4}`都已经排过了，所以`3`开头就不能要了,就会变成array2=\{ `4`,3,5\}，再把这个array2进行分解子集合再排，`然后就是一直延续下去，排完整个大的集合。`**

`这里就只介绍这几种方法：`  
**1.回溯法**  
**2. 字典序法**  
**3. 邻位对换法**

## 一、回溯法 ##

> “回溯”指的是“状态重置”，可以理解为“恢复现场”，是在编码的过程中，是为了节约空间而使用的，而在递归或者深度优先中根据需要的场合来配合回溯法可以进一步对自己的代码进行优化。

![大概就是一个树形的结构][20a75de121f1483f99e637a5612550eb.png]

> 回溯的基本模板

#include<iostream>
    #include<algorithm>
    using namespace std;
    const int N=10;
    bool st[N];//用来判断1~n这n个数是否被选。true代表已经被选了，false反之
    int p[N];//用来记录1~n个位置选的是哪个数
    int n;
    void dfs(int u){
        
        if(u>n){
        //当n个位置都确定之后就打印
            for(int i=1;i<=n;i++){
        
                cout<<p[i]<<" ";
            }
            cout<<endl;
            return;
        }
        for(int i=1;i<=n;i++){
        //第u个位置开始选数
            if(!st[i]){
        //如果这个数没有被选
                st[i]=true;//选择这个数打上标记
                p[u]=i;//记录
                dfs(u+1);//开始枚举下一个位置
                st[i]=false;//恢复现场
            }
        }
    }
    int main()
    {
        
        cin>>n;
        dfs(1);//从第一个位置开始遍历
        return 0;
    }

## 二、字典序法 ##

> 首先字典序法在数学中就是字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法  
> 这也就是前面所解释说明的那样，以数组 \[1, 2, 3\] 的全排列为例。

以 1 开头的全排列为\[1, 2, 3\], \[1, 3, 2\]；  
以 2 开头的全排列为\[2, 1, 3\], \[2, 3, 1\]；  
最后以 3 开头的全排列为\[3, 1, 2\], \[3, 2, 1\]；  
从上面的全排列可以看出来，开头固定数是从左往右依次增大的，对这就是字典序法

> 这里找了一张图  
> ![在这里插入图片描述][ee057728255b413ab567038e7ef0df12.png]

> 代码如下（示例）：

/**
    list就是集合R
    k 表示list中的开始位置
    m 表示list中的结束位置
    */
    	static int[] list={
        1,2,3};
    	public static void main(String[] args) {
        
    	 perm(list, 0, list.length-1);
    	}
    	 public static void perm(int[] list,int k,int m){
        
    	     //产生list中第k到m位置上元素的全排列
    		if(k==m){
        //只剩一个元素的情况下的全排列，也是递归出口
    			for(int i=0; i<=m; i++){
        
    				System.out.print(list[i]);
    			}
    			System.out.println();
                return;
    		}else{
        
    			for(int i=k; i<=m; i++){
               
    				swap(list,k,i);//将第i个元素和该子序列中的第一个元素进行交换
    				perm(list,k+1,m);//求解规模为n-1的子问题
    				swap(list,k,i);//将它换回
    			}
    		}
    	}
    	public static void swap(int[] list,int k,int i){
         //进行交换
    		int temp = list[k];
    		list[k] = list[i];
    		list[i] = temp;
    	}

## 三、相邻对换法 ##

> 邻位对换法是全排列生成算法中的其中一种，它的换位是双向的，通过保存数字的“方向性”来快速得到下一个排列

`说明:`  
1、 每个数有一个移动方向，向左或向右。如果数x的移动方向上最靠近它的数比它要小，那么x是可移动的。初始时序列为\{1, 2, 3, …, n-1, n\}，方向都为向左。  
2、 移动最大数n，直到不能移动为止，每改变一次位置输出一个序列（此时n在最左边或最右边）。  
3、 找当前可移动的最大数m。若能找到，移动m，把所有比m大的数的方向置反，返回第2步；若不能找到，算法停止。

以array=\{1,2,3,4\}的全排列为举例，当我们其中子集合\{1，2，3\}的全排列为：

这6个数，那么将4排入其中,则过程为这样  
![在这里插入图片描述][6a77b9e534474d8aaa3ae3b1b4917800.png]

> 代码部分

import java.util.ArrayList;
    
    public class Permutation {
        
    
        public static void main( String[] args ) {
        
            String[] result = permutation( "12345" );
            // System.out.println( result.length + "\r\n" );
            for ( String s : result ) {
        
                System.out.println( s );
            }
        }
    
        public static String[] permutation( String str ) {
        
    
            ArrayList<String> charList = new ArrayList<String>();
                    char[] arrChars = str.toCharArray();
                    long  times= 1;
                    int  k= arrChars.length - 2;
                    0int  inc= -1;
    
            for ( int i = 1; i < arrChars.length + 1; i++ ) {
        
                times *= i;
            }
    
            for ( int i = 1; i < times; i++ ) {
        
    
                swap( arrChars, k, k + 1 );
                charList.add( new String( arrChars ) );
                k += inc;
    
                if ( k == -1 ) {
        
                    inc = 1;
                    k = 0;
                    swap( arrChars, arrChars.length - 2, arrChars.length - 1 );
                    charList.add( new String( arrChars ) );
                    i++;
                }
    
                if ( k == arrChars.length - 1 ) {
        
                    inc = -1;
                    k = arrChars.length - 2;
                    swap( arrChars, 0, 1 );
                    charList.add( new String( arrChars ) );
                    i++;
                }
            }
    
            return charList.toArray( new String[0] );
        }
    
        private static void swap( char[] arr, int k1, int k2 ) {
        
            char tmp = arr[k1];
            arr[k1] = arr[k2];
            arr[k2] = tmp;
        }
    }

`在排列组合中，有几个重要的数学公式：`![在这里插入图片描述][2d4fa0d3028f46d7a7eb2f7b51d06f39.png]  
![在这里插入图片描述][5b7ccdcce1344e5a94147d6eaf9efd3c.png]

> 全排列问题大概到这里，后续有什么补充的我再添加

[20a75de121f1483f99e637a5612550eb.png]: https://img-blog.csdnimg.cn/20a75de121f1483f99e637a5612550eb.png
[ee057728255b413ab567038e7ef0df12.png]: https://img-blog.csdnimg.cn/ee057728255b413ab567038e7ef0df12.png
[6a77b9e534474d8aaa3ae3b1b4917800.png]: https://img-blog.csdnimg.cn/6a77b9e534474d8aaa3ae3b1b4917800.png
[2d4fa0d3028f46d7a7eb2f7b51d06f39.png]: https://img-blog.csdnimg.cn/2d4fa0d3028f46d7a7eb2f7b51d06f39.png
[5b7ccdcce1344e5a94147d6eaf9efd3c.png]: https://img-blog.csdnimg.cn/5b7ccdcce1344e5a94147d6eaf9efd3c.png