关于全排列的递归算法

全排列的⼏种算法全排列，我们⾼中时就学过，数学上很简单，可是⽤计算机的算法实现还是有点味道的，今天我将我碰到的⼏种算法如数奉上，欢迎交流！第⼀种：递归最常见的也是最好理解的⽅法：简单点：⽐如"a" ,"b","c"全排列，可以看做事"a" +"b","c"的全排列及"b"+ "a","c"的全排列及"c" + "a","b"的全排列也就是说，遍历原数组中的每个元素，让剩余的元素全排列，这样就找到规律了。

代码如下：public static void main(String[] args) {char buf[]={'a','b','c','d'};perm(buf,0,buf.length-1);}public static void perm(char[] buf,int start,int end){if(start==end){//当只要求对数组中⼀个字母进⾏全排列时，只要就按该数组输出即可（特殊情况）for(int i=0;i<=end;i++){System.out.print(buf[i]);}System.out.println();}else{//多个字母全排列（普遍情况）for(int i=start;i<=end;i++){//（让指针start分别指向每⼀个数）char temp=buf[start];//交换数组第⼀个元素与后续的元素buf[start]=buf[i];buf[i]=temp;perm(buf,start+1,end);//后续元素递归全排列temp=buf[start];//将交换后的数组还原buf[start]=buf[i];buf[i]=temp;}}}第⼆中⽅法：也是递归，但是和第⼀种有所区别，算法：将数据分为两部分，递归将数据从左侧移右侧实现全排列⽐较抽象，如list abcd，遍历每⼀个数，将每个数放到⼀个新的list中,并将该元素从原list删除，然后将剩下的元素继续遍历每个元素继续放到新的list ⾥，这样，当list的长度为原list长度，或者原list长度为0时打印结果！下⾯是简单的⽰意图：// abcd//bcd a//cd ab//d abc//abcd//c abd//abdc//bd ac//d acb//acbd//b acd//acdb//bc ad ...//acd b ...//abd c ...//abc d ...源代码如下：private static void sort(List datas, List target) {//System.out.println("size="+datas.size());if (datas.size()==0) {for (Object obj : target)System.out.print(obj+" ");System.out.print(" ");return;}for (int i = 0; i < datas.size(); i++) {List newDatas = new ArrayList(datas);List newTarget = new ArrayList(target);newTarget.add(newDatas.get(i));newDatas.remove(i);sort(newDatas, newTarget);}}public static void main(String[] args) {List list = new ArrayList();for(int i=0;i<5;i++){list.add(i+1);}sort(list, new ArrayList());}第三种⽅法：⾮递归直接上代码：public static void main(String[] args) {int[] arr = new int[]{1,2,3,4,5,6};for(int i :arr){System.out.print(i + " ");}System.out.println();int totalnum = 1;while(NextNumber(arr,arr.length)){for(int i :arr){System.out.print(i + " ");}System.out.println();totalnum ++;}System.out.println("Total Num: " + totalnum);}private static Boolean NextNumber(int[] arr, int n){//数组最后⼀个元素位置int lastIndex = n-1;//从右向左确定第⼀个数字（前⾯的数字⽐它⼩）int firstIndex = lastIndex;for(;arr[firstIndex-1]>arr[firstIndex];firstIndex--){if(firstIndex == 1){//已经轮询完毕,此数已经是最⼤的那个数return false;}}//从右向左确定⼀个交换数（此数⽐arr[firstIndex]⼩且⽐arr[firstIndex-1]⼤）int swapIndex = lastIndex;for(;swapIndex > firstIndex;swapIndex--){if(arr[swapIndex] < arr[firstIndex] && arr[swapIndex] > arr[firstIndex-1]){break;}}//交换数字swap(arr,firstIndex-1,swapIndex);//将firstIndex右边的数字排序for(;firstIndex < lastIndex;firstIndex++,lastIndex--){if(arr[firstIndex] > arr[lastIndex]){swap(arr,firstIndex,lastIndex);}}return true;}private static void swap(int[] arr,int i, int j){int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}如果此⽂对你有帮助，请留个⾔，新⼈需要打架的⽀持和⿎励！。

列举常见的递归问题因为今天我重新看了递归的教学视频，但发现好像很多都很容易忘，所以我想把所有常见的递归算法题给整理⼀下。

1.全排列输⼊:"aac"输出:[aac,aac , aca, aca,caa]思路就是可以选择每个下标的字母作为开头。

public static List<String> getAll(String str) {if(str.equals("") || str == null){return null;}List<String> list = new ArrayList<>();ArrayList<Character> set = new ArrayList<Character>();for (Character character : str.toCharArray()) {set.add(character);}process(set,"",list);return list;}public static void process(ArrayList<Character> set, String path, List<String> list){if(set.isEmpty()){list.add(path);return;}for (int index = 0; index < set.size(); index++) {String pick = path+set.get(index);ArrayList<Character> next = new ArrayList<>(set);next.remove(index);process2(next, pick, list);}}}2.全排列，不要有重复这⾥要注意判断是否选过的HashSet<Character> picks，这个点我想了好久才想通，因为在for循环⾥⾯，其实是在循环每个位置作为开头，所以在循环的时候，⽐如当我们选了‘a’之后，我们就不能再选‘a’作为开头字母了，所以我觉得从循环这个点去理解HashSet<Character> picks会⽐较好。

Fibonacci数列、集合全排列和整数划分问题Fibonacci数列Fibonacci数列是一个由0和1开始，每个后续数字等于前两个数字之和的数列。

以下是Fibonacci数列的递归算法实现：// 递归实现Fibonacci数列function fibonacci(n) { if (n <= 1){ return n; } return fibonacci(n - 1) + fibonacci(n - 2);}集合全排列集合全排列问题是指给定一个集合，求该集合中元素的全排列。

以下是集合全排列的递归算法实现：// 递归实现集合全排列function permute(arr, start = 0) { if (start === arr.length) { console.log(arr); // 输出当前排列 } for (let i = start; i < arr.length; i++) { // 交换当前元素与起始位置元素 [arr[start], arr[i]] = [arr[i], arr[start]]; permute(arr, start + 1); // 递归调用下一次排列 [arr[start],arr[i]] = [arr[i], arr[start]]; // 恢复当前元素与起始位置元素的交换 }}整数划分整数划分问题是指将一个整数拆分成多个正整数的和，求所有的划分方式。

以下是整数划分的递归算法实现：// 递归实现整数划分function partition(n, max, prefix = []) { if (n === 0) { console.log(prefix); // 输出当前划分 } for (let i = Math.min(max, n); i >= 1; i--) { partition(n - i, i, [...prefix, i]); // 递归调用下一次划分 }}。

全排列递归算法c语言
全排列是一种将一组元素进行排列得到所有可能的组合的算法。

递归是一种重复调用函数本身的方法，可以用来实现全排列算法。

以下是一个使用递归算法实现全排列的C语言代码示例：// 交换数组中两个元素的位置
// 递归生成全排列
// 将第i个元素与第start个元素交换位置 // 递归生成剩余元素的全排列
// 恢复数组的原始顺序
这段代码使用了递归的方式生成数组 `arr` 的全排列。

`permute` 函数接受一个数组、起始位置 `start` 和结束位置`end` 作为参数。

在每一次递归调用中，它将当前位置的元素与后续位置的元素依次交换，并递归生成剩余元素的全排列。

当`start` 等于 `end` 时，表示已经完成了一种排列，将其打印出来。

运行上述代码，将会输出以下结果：
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
```
这些结果是给定数组 `[1, 2, 3]` 的所有全排列。