递归分治思想实现：全排列详解(改进:排重)-题解（C/C++/Java版）

解题思路:

例如：1234

        从1开始枚举到4，输出1234，然后回溯到2，再继续枚举后两位，再输出1243，然后回溯到1再继续枚举到1324，

以此类推1342，1423，1432，然后回溯到s=0则从2开始枚举。。。。

        我们还可以理解为层层循环、层层递归来实现深度优先搜索，

先从0开始->for循环->DFS(1)->for循环->DFS(2)->for循环->DFS(3)->DFS(4){打印1234}->(回溯到)DFS(3){第四位清0}->DFS(2){第三位清0;for循环到第四位{把第四位放入3(也就是当前参数2加1放入answer)}}->DFS(3){for循环出第三位是0则放入4(也就是当前参数3加1放入answer)}->DFS(4){打印1243}->........以此类推；

        核心要素就是以局部规则来推动整个分治的递归调用。

        建议将算法思想和代码结合来理解，更深刻。

注意事项:

        从DFS(i)穿入i=0就是第i+1层（也就是枚举第一位数）;

        我们要界定好for()循环枚举的每一个过程,以及递归调用的位置放在哪里能够逐层回溯再递归调用.

参考代码:

#include      //#inlucde相当于#inlucde#define MAX 12          //宏定义 
using namespace std;

/*全局变量:*/ 
int n;			//全排列的长度
int answer[MAX];	//最后输出的答案
bool visit[MAX];	//储存每个数是否用过,true用过,false没用过

/*深度优先搜索*/
void DFS(int s)                                    //搜索,s是当前枚举的位数(因为数组是从0开始的所以s调用的时候需要+1),表示的是到此为止,已经确定的全部排列的数的个数
{
    if (s == n)//判断是否已经枚举完了,若枚举完，就输出
    {
        for (int i = 1; i <= n; i++)               //输出第i个数
        {
            printf("%d", answer[i]);               //输出，若用cpp形式：cout<<answer[i];
        }
        puts("");//相当于printf("\n");             //换行
    }
    else
    {
        for (int i = 1; i <= n; i++)	//枚举,看到此为止有哪些数没用过
        {
            if (!visit[i])		//判断这个数是否被用过
            {
                visit[i] = true;	//标记这个数用过了
                answer[s + 1] = i;      //标记第s + 1个数是多少
                DFS(s + 1);		//进行下一层搜索
                answer[s + 1] = 0;	//取消标记(回溯)
                visit[i] = false;	//取消标记(回溯)
            }
        }
    }
    return;//若打印完就直接回溯，若for枚举完就直接回溯
}

int main()
{
    scanf("%d", &n);    //输入
    DFS(0);             //调用深搜
    return 0;
}

其实，更简单的就是直接调用C++库函数next_permutation就完事了！

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int a[4]={1,2,3,4};
	do{
		cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<endl;
	}
	while(next_permutation(a,a+4));
	system("pause");
}

上面这段代码意思为求1,2,3,4的全排列。

上面以C/C++代码实现的回溯算法,下面再推荐一种以Java来实现的递归交换的算法(老师常讲的方法):

import java.util.Arrays;

public class Full_permutation {
	public static void main(String[] args)
	{
		int[] arr = {1,2,3};//设定
		permutation(arr,arr.length,0);
	}
	public static void permutation(int[] arr,int size,int n)
	{
		if(n == size)
		{
			System.out.println(Arrays.toString(arr));
		}
		else
		{
			for(int i = n;i < size;i ++)
			{
				swap(arr,i,n);
				permutation(arr,size,n+1);
				swap(arr,i,n);
			}
		}
	}
	public static void swap(int[] arr,int i,int j)
	{
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}	
}

但是,当我们要排列的数(如:1,2,3,3),就会出现重复打印现象,所以我们稍微改进一下程序就更完美了!

Java改进后:

import java.util.Arrays;

public class Full_permutation {
	public static void main(String[] args)
	{
		int[] arr = {1,2,3,3};//设定
		permutation(arr,arr.length,0);
	}
	public static void permutation(int[] arr,int size,int n)
	{
		if(n == size)
		{
			System.out.println(Arrays.toString(arr));
		}
		else
		{
			for(int i = n;i < size;i ++)
			{
			    if(arr[i] != arr[n] || i == n)//两值不相等或要执行的是它本身,则需要交换
			    {
			    	swap(arr,i,n);
				permutation(arr,size,n+1);
				swap(arr,i,n);
			    }
			}
		}
	}
	public static void swap(int[] arr,int i,int j)
	{
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}	
}

全排列问题经常基于字典序的方法来搞,所以可以在函数中含有交换循环之前加入排序算法(如冒泡、快速排序...)

注意：全排列问题不能只停留于代码层面，需要大家申请思路，才能看懂代码包括上面写的java实现方法，尤其需要看懂其中的递归和回溯看懂一个过程就能看懂整个过程