Java下实现无重字符串的全排列（递归和回溯方法）算法

给定一个无重复字符的字符串数组，实现它的全排列
一、采用递归实现全排列
思想是从第一个字符开始排，一直排到只有一个字符那么就说明一个排列完成了。否则就交换当前第k个字符和第i个字符（这里的第i个字符指的是k后面所有字符的其中一个，例如abcd，当a固定，对bcd排列，那就要将b和c、b和d依次交换），再对k+1到m进行排列。当返回成功后就再将第k个字符和第i个字符再交换回来。
递归的终止条件就是k=m
k 为起始下标，m为结束下标，下面的函数用于返回从k到m的全排列
list[]用于存储待排列的字符串

public static void perm(char list[], int k, int m) { if(k == m) { System.out.println(list); } else { for(int i = k; i <= m; i++) { //交换第k个字符和第i个字符，因为java是按值传递，所以我就没用函数交换 char temp; temp = list[k]; list[k] = list [i]; list[i] = temp; //再对k后面的字符串进行全排列 perm(list, k+1, m); //排列完后再换回来继续下一层循环 temp = list[k]; list[k] = list [i]; list[i] = temp; } } }

【Java下实现无重字符串的全排列（递归和回溯方法）】二、采用回溯实现全排列
思想是深度优先搜索，比如要找12345的全排列的一种排列12345
第一层，有五种选择，1、2、3、4、5，五个元素都标记没被使用过
第二层，1下面有四种2、3、4、5， 1被标记使用过
第三层，2下面有三种3、4、5， 1、2被标记使用过
第四层，3下面有两种4、5， 1、2、3被标记使用过
第五层，4下面就只能排5了，1、2、3、4被标记使用过
这时就找到了一种排列12345，然后将5标记为没被使用过，返回到上一层4，将4也标记为没使用过，但5可以选，然后再选4，这样就实现了回溯，就可以得到所有解了。
具体代码如下：
参数n表示第几层，list是一个char型的数组，存放了待全排列的字符串
used[]是一个bool型的数组，具体下标对应的真假值判断那个下标的字符有没有被使用过，vector[]是一个整型数组，用于存放一个排列的解，amount用于计数，result函数用于将解向量输出成排列。

public static void perm(char list[], int k, int m) { if(k == m) { System.out.println(list); } else { for(int i = k; i <= m; i++) { //交换 char temp; temp = list[k]; list[k] = list [i]; list[i] = temp; //返回k之后的全排列 perm(list, k+1, m); //交换回来 temp = list[k]; list[k] = list [i]; list[i] = temp; } } }

完整的可以通过输入字符串（要保证无重复字符）来返回所有排列的测试代码如下：

import java.nio.file.attribute.AclEntryPermission; import java.util.Arrays; import java.util.Scanner; public class Generator { static boolean used[]; //存放字符是否被使用过 static char list[]; //存放字符串 static int vector[]; //存放当前排列的解向量 static int amount = 0; //用于计数 public static void main(String[] args) { // 用户输入字符串 String str; Scanner input = new Scanner(System.in); str = input.next(); list = str.toCharArray(); used = new boolean[str.length()]; vector = new int[str.length()]; //perm(list, 0, str.length()-1); //用递归实现全排列 Aperm(0); //用回溯实现全排列，从第0层开始 } public static void perm(char list[], int k, int m) { if(k == m) { System.out.println(list); } else { for(int i = k; i <= m; i++) { //交换 char temp; temp = list[k]; list[k] = list [i]; list[i] = temp; //返回k之后的全排列 perm(list, k+1, m); //交换回来 temp = list[k]; list[k] = list [i]; list[i] = temp; } } } public static void Aperm(int n) { //第0层有i.length种选择 for(int i = 0; i < list.length; i++) { if(!used[i]) { vector[n] = i; //记录当前解 used[i] = true; //当前元素被使用 if(n!= list.length - 1) Aperm(n+1); //若不是最后一层则返回下一层的 else//否则就是最后一层，那么就找到了一种排列，输出 System.out.println(amount++ +": "+ result(vector)); //很重要，返回到上一层就得取消标记 used[i] = false; } } } public static String result(int vector[]) { String string = ""; for(int i = 0; i < vector.length; i++) { string += list[vector[i]]; } return string; }}