算法笔记---全排列算法

题目

全排列算法，在笔试中是非常常见的。如：

打印出给出的String字符串的全排列, 如 abc 的全排列: abc, acb, bca, dac, cab, cba

全排列的递归形式

算法思想：

简单地说：就是第一个位置的字符分别和面的字符进行交换。

E．g：E = （a , b , c） 则 prem（E）= a.perm（b,c）+ b.perm（a,c）+ c.perm（a,b） 然后a.perm（b,c）= ab.perm（c）+ ac.perm（b）= abc + acb.依次递归进行.

代码实现

//利用集合Set的特性筛选出现的重复字符串 public static Set<String> set = new HashSet<>(); public static void permutations(String s) { char[] ch = s.toCharArray(); Perm(ch, 0, ch.length - 1); for (String ss : set) { System.out.println(ss); } } private static void Perm(char[] ch, int n, int m) { String s = String.valueOf(ch); if (n == m) { set.add(s); } else { //第一个位置开始要也与自己交换一次 //第i个数分别与它后面的数字交换就能得到新的排列 for (int i = n; i <= m; i++) { ch = swap(ch, n, i); Perm(ch, n + 1, m); ch = swap(ch, n, i); } } } //指定位置字符交换 private static char[] swap(char[] ch, int n, int i) { char s = ch[n]; ch[n] = ch[i]; ch[i] = s; return ch; }

测试 s= “abbc”

参考

http://www.cnblogs.com/bakari/archive/2012/08/02/2620826.html