昨天一位网友问我全排列的写法，记得以前看过一篇用“旋转法”进行排列的算法。久没碰这些东西了，早已是忘得一干二净。只好用以前用C写过的算法来了。
在C中用数组实现，为求编码速度，用字符串代替，并有很大的局限性，比如串中的字符要求两两不等。
算法其实很简单，求n位的，其实就是在n中任取一位，其后跟上剩下(n-1)位的全排列。
代码如下：
public class Main {
// 要排列的数组
private static String str1 = "0123456789";
// 计数器
private static int count = 0;
/**
* main函数
*/
public static void main(String[] args) {
permutation("", str1);
System.out.println(count);
}
/**
*
* 递归求全排列
* 算法描述：
* 以8位为例，求8位数的全排列，其实是8位中任取一位
* 在后加上其余7位的全排列
* 7位：任取一位，其后跟剩下6位的全排列
* ……
* 这样就有两部分，一部分为前面的已经取出来的串，另一部分为后面即将进行的全排列的串
*
* 参数pre即为前面已经取出来的串
* 参数str即为将要进行排列的串
*
*/
public static void permutation(String pre, String str) {
// 如果要排列的串长度为1，则返回
if (str.length() == 1) {
System.out.println(pre + str);
count++;
return;
}
// for循环即是取出待排列的串的任一位
for (int i = 0; i < str.length(); i++) {
// 递归，将取出的字符并入已经取出的串
// 那么剩下的串即为待排列的串
permutation(pre + str.charAt(i), deleteMiddle(str, i));
}
}
/**
*
* 去掉数组str第index位，比如传入("12345",1)则返回"1345"
*
*/
public static String deleteMiddle(String str, int index) {
return str.substring(0, index) + str.substring(index + 1, str.length());
}
}
在C中用数组实现，为求编码速度，用字符串代替，并有很大的局限性，比如串中的字符要求两两不等。
算法其实很简单，求n位的，其实就是在n中任取一位，其后跟上剩下(n-1)位的全排列。
代码如下：
public class Main {
// 要排列的数组 private static String str1 = "0123456789"; // 计数器 private static int count = 0; /**
* main函数 */ public static void main(String[] args) { permutation("", str1); System.out.println(count); } /** * * 递归求全排列 * 算法描述： * 以8位为例，求8位数的全排列，其实是8位中任取一位 * 在后加上其余7位的全排列 * 7位：任取一位，其后跟剩下6位的全排列 * …… * 这样就有两部分，一部分为前面的已经取出来的串，另一部分为后面即将进行的全排列的串 * * 参数pre即为前面已经取出来的串 * 参数str即为将要进行排列的串 * */ public static void permutation(String pre, String str) { // 如果要排列的串长度为1，则返回 if (str.length() == 1) { System.out.println(pre + str); count++; return; } // for循环即是取出待排列的串的任一位 for (int i = 0; i < str.length(); i++) { // 递归，将取出的字符并入已经取出的串 // 那么剩下的串即为待排列的串 permutation(pre + str.charAt(i), deleteMiddle(str, i)); } } /** * * 去掉数组str第index位，比如传入("12345",1)则返回"1345" * */ public static String deleteMiddle(String str, int index) { return str.substring(0, index) + str.substring(index + 1, str.length()); }}