Java排列组合算法

 

import java.util.ArrayList;
/**
 * 全排列算法
 * 
 */
public class Arrange {

	private int total = 0;
	private ArrayList<string></string> arrangeList = new ArrayList<string></string>();

	public Arrange() {
	}

	private void swap(String list[], int k, int i) {
		String c3 = list[k];
		list[k] = list[i];
		list[i] = c3;
	}

	public void perm(String list[], int k, int m) {
		if (k > m) {
			StringBuffer sb = new StringBuffer();
			for (int i = 0; i <= m; i++) {
				sb.append(list[i]).append(",");
			}
			if (sb.length()>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<string></string> getArrangeList() {
		return arrangeList;
	}

	public static void main(String args[]) {
		String list[] = { "1", "2", "3", "4", "5" };
		Arrange ts = new Arrange();
		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;
/** 组合算法 */

public class Combination {
	
	private ArrayList<string></string> combList= new ArrayList<string></string>();

	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)
			if (bs.get(++start))
				break;
		if (start >= m)
			return false;

		int end = start;
		while (end < m)
			if (!bs.get(++end))
				break;
		if (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();
		for (int i = 0; i < array.length; i++)
			if (bs.get(i)) {
				sb.append(array[i]).append(',');
			}
		sb.setLength(sb.length() - 1);
		combList.add(sb.toString());
	}
	
	public ArrayList<string></string> getCombList() {
		return combList;
	}

	public static void main(String[] args) throws Exception {
		Combination comb = new Combination();
		comb.mn(new String[]{"1","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<string></string> getArrangeOrCombine(String[] args,int n, boolean isArrange) throws Exception{
		if (args.length<=0) {
			throw new Exception("array.length<=0");
		}
		if (n>args.length) {
			throw new Exception(" n>array.length");
		}
		Combination comb = new Combination();
		comb.mn(args, n);
		if (!isArrange) {
			return comb.getCombList();
		}
		ArrayList<string></string> arrangeList = new ArrayList<string></string>();
		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;
	}
	
	public static void main(String[] args) {
		try {
			ArrayList<string></string> arrangeOrCombine = ArrangeCombine.getArrangeOrCombine(new String[]{"1","2","3","4","5","6"}, 3, false);
			ArrayList<string></string> arrangeOrCombine2 = ArrangeCombine.getArrangeOrCombine(new String[]{"1","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.out.println("=============================");
			for (int i = 0; i < arrangeOrCombine2.size(); i++) {
				System.out.println(arrangeOrCombine2.get(i));
			}
			System.out.println("Total:"+arrangeOrCombine2.size());
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

}