排列组合（一）全排列

本文主要是介绍排列组合（一）全排列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

输出一个字符数组元素的全排列
如

输入：'a','b','c'
结果：a,b,cb,a,cc,b,aa,c,bb,c,ac,a,b6

---

解决思路

这个问题是一个全排列问题，数学计算为A（n，n）。数学思路为，n个元素，第一位可以为n种可能，第二位可以有n-1种可能，以此类推所以全排列的种类一共有n！个。
以此为思路，我们可以从初始化顺序开始，

1. 首先确定第一位，第一位一共有n种可能性，第一位分别和第1~n位进行交换，产生了n种排列方式，即这代表了第一位分别放置了n个不同元素；
2. 放置第二位的元素，第一位放置完产生的n种可能顺序中，每种顺序的第二位只能有放置n-1种元素的可能性，第二位的元素只能在剩下的元素中选取，即从2~n位中选取一个元素作为第二位，用交换第2位到第n位产生第二位的n-1种放置方式；
3. 放置第三位元素，和第二位类似，第三位元素的放置一共有n-2种可能性，在前两位放置完的基础上，每种放置顺序的第三位进行n-3种可能的放置。
4. 依次类推，一直放置到最后一位，即到第n位，只有一种放置方式。这样就得到所有的排列。

---

代码实现

方式一：自己实现的非递归方式

    public static Queue<char[]> array2(char[] ch){// 新建一个队列Queue<char[]> queue = new LinkedList<>();// 将初始排列顺序入队queue.offer(ch);for(int i=0;i<ch.length;i++){// 辅助队列Queue<char[]> queue2 = new LinkedList<>();// 将队列中每种顺序分别出队进行下一位置所有可能的排列while(!queue.isEmpty()){// 将队列中的每种顺序出队char[] poll = queue.poll();// 当前位置一共有n-i种放置可能for(int j=i;j<ch.length;j++){// 对当前位置i进行n-i种可能放置，并将结果序列存储在辅助队列中queue2.offer(swap2(poll, i, j));}}// 将辅助队列中的结果存入原队列中queue = queue2;}return queue;}// 返回对输入的ch产生交换m与n位置后的新序列public static char[] swap2(char[] ch,int m,int n){// 新建新顺序数组char[] c = new char[ch.length];// 进行数组拷贝for(int i=0;i<ch.length;i++){c[i] = ch[i];}// 新数组交换位置c[m] = ch[n];c[n] = ch[m];return c;}

方式二：参考网上的代码递归实现

    // 记录个数static int count=0;// 交换ch中m和n位置public static void swap(char[] ch ,int m,int n){char t = ch[m];ch[m] = ch[n];ch[n] = t;}// 递归函数,ch为当前序列，current为当前位置public static void array(char[] ch,int current){// 当前位置为序列的最后一位时，输出该顺序if(current == ch.length-1){count++;System.out.println(Arrays.toString(ch));}else{// 关键代码for(int i=current;i<ch.length;i++){swap(ch, current, i);array(ch, current+1);swap(ch, current, i);}}}

递归方式关键在else中的部分，稍微有点难理解，但仔细看其实原理和上边一样

这篇关于排列组合（一）全排列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---