Java实现排列组合算法.docx

Java实现排列组合算法第一部分：java实现排列算法具体的代码.?import java.util.ArrayList; /* * java实现排列算法 * */public class ArrangeTest private int total = 0; private ArrayList arrangeList = new ArrayList(); public Arrange() /* * 交换方法的实现 */private void swap(String list, int k, int i) String c3 = listk; listk = listi; listi = c3; /* * perm方法的实现 */public void perm(String list, int k, int m) if (k m) StringBuffer sb = new StringBuffer(); for (int i = 0; i 0) sb.setLength(sb.length()-1); arrangeList.add(sb.toString(); total+; else for (int i = k; i = m; i+) swap(list, k, i); perm(list, k + 1, m); swap(list, k, i); /* * 获得总数 */public int getTotal() return total; public ArrayList getArrangeList() return arrangeList; /* * main方法的实现 */public static void main(String args) String list = 1, 2, 3, 4, 5 ; ArrangeTest ts = new ArrangeTest (); ts.perm(list, 0, list.length-1); for (int i = 0; i ts.getArrangeList().size(); i+) System.out.println(ts.getArrangeList().get(i); System.out.println(total: + ts.total); 第二部分、组合算法的实现?import java.util.ArrayList; import java.util.BitSet; /* * java组合算法的实现 * */public class Combination private ArrayList combList= new ArrayList(); /* *mn方法的实现 * */public void mn(String array, int n) int m = array.length; if (m n) throw new IllegalArgumentException(Error m n); BitSet bs = new BitSet(m); for (int i = 0; i n; i+) bs.set(i, true); do printAll(array, bs); while (moveNext(bs, m); /*说明 这个方法不太容易理解，也是组合的核心算法,下面进行简单的讲解. * 1、start是从第一个true片段作为起始位，end作为截止位 * 2、第一个true片段都设置成false * 3、数组从0下标起始到以第一个true片段元素数量减一为下标的位置都置true * 4、把第一个true片段end截止位置true * * param bs 数组是否显示的标志位 * param m 数组长度 * return boolean 是否还有其他组合 */private boolean moveNext(BitSet bs, int m) int start = -1; while (start = m) return false; int end = start; while (end = m) return false; for (int i = start; i end; i+) bs.set(i, false); for (int i = 0; i end - start - 1; i+) bs.set(i); bs.set(end); return true; /* * 输出打印结果 * * param array 数组 * param bs 数组元素是否显示的标志位集合 */private void printAll(String array, BitSet bs) StringBuffer sb = new StringBuffer(); /拼接StringBuffer，这个地方一定要用StringBuffer，不要直接使用String 的+ for (int i = 0; i array.length; i+) if (bs.get(i) sb.append(arrayi).append(,); sb.setLength(sb.length() - 1); combList.add(sb.toString(); public ArrayList getCombList() return combList; /* * 主方法测试 * */public static void main(String args) throws Exception Combination comb = new Combination(); comb.mn(new String1,2,3,4,5,6, 3); for (int i = 0; i comb.getCombList().size(); i+) System.out.println(comb.getCombList().get(i); String list = comb.getCombList().get(i).split(,); Arrange ts = new Arrange(); ts.perm(list, 0, list.length-1); for (int j = 0; j ts.getArrangeList().size(); j+) System.out.println(u0009+ts.getArrangeList().get(j); 第三部分、实现排列组合算法调用的工具类?import java.util.ArrayList; /* * 调用组合算法的工具类 * */public class ArrangeCombine public static ArrayList getArrangeOrCombine(String args,int n, boolean isArrange) throws Exception if (args.length=0) throw new Exception(array.lengthargs.length) throw new Exception( narray.length); Combination comb = new Combination(); comb.mn(args, n); if (!isArrange) return comb.getCombList(); ArrayList arrangeList = new ArrayList(); for (int i = 0; i comb.getCombList().size(); i+) String list = comb.getCombList().get(i).split(,); Arrange ts = new Arrange(); ts.perm(list, 0, list.length-1); for (int j = 0; j ts.getArrangeList().size(); j+) arrangeList.add(ts.getArrangeList().get(j); return arrangeList; /main方法的实现 public static void main(String args) try ArrayList arrangeOrCombine = ArrangeCombine.getArrangeOrCombine(new String1,2,3,4,5,6, 3, false); ArrayList arrangeOrCombine2 = ArrangeCombine.getArrangeOrCombine(new String1,2,3,4,5,6, 3, true); for (int i = 0; i arrangeOrCombine.size(); i+) System.out.println(arrangeOrCombine.get(i); System.out.println(Total:+arrangeOrCombine.size(); System.o