排列组合算法实现【学习】

一个从M个数字里面取N个数字的组合
没用到递归的实现，将选取的位置标记为1没选取的标记为0
返回的是数组的形式。

版本1

public class CombineUtil {

	private static int[] copy(int[] bs){
		int[] result = new int[bs.length];
		for(int i=0;i<bs.length;i++){
			result[i] = bs[i];
		}
		return result ;
	}


	public static void print(List<int[]> l){
		for(int i=0;i<l.size();i++){
			int[] a = (int[])l.get(i);
			for(int j=0;j<a.length;j++){
				System.out.print(a[j]+"\t");
			}
			System.out.println();
		}
	}

	public static void print(int[] a){
		for(int j=0;j<a.length;j++){
			System.out.print(a[j]+"\t");
		}
		System.out.println();
	}

	/**
	 * 从m里选n个数字
	 * @param m
	 * @param n
	 * @return
	 */
	public static List<int[]> combineEx(int m, int n) {
		if (m < n) {
			return null;
		}

		List<int[]> list = new ArrayList<int[]>();
		int[] cn = new int[m];
		for (int i = 0; i < cn.length; i++) {
			if (i < n) {
				cn[i] = 1;
			} else {
				cn[i] = 0;
			}
		}

		boolean flag = true;

		do {
			int pos = 0;
			int sum = 0;
			boolean tempFlag = true;

			list.add(copy(cn));
			if (m == n || m == 0) {
				return list;
			}

			for (int i = 0; i < m - 1; i++) {
				if (cn[i]==1 && cn[i+1]==0) {
					cn[i]=0;
					cn[i+1]=1;
					pos = i;
					break;
				}
			}

			for (int i = 0; i < pos; i++) {
				if (cn[i] == 1) {
					sum ++;
				}
			}

			for (int i = 0; i < pos; i++) {
				if (i < sum) {
					cn[i] = 1;
				} else {
					cn[i] = 0;
				}
			}

			for (int i = m-n; i < cn.length; i++) {
				if (cn[i] == 0) {
					tempFlag = false;
					break;
				}
			}

			flag = !tempFlag;
		} while (flag);
		list.add(copy(cn));

		return list;
	}

	public static void main(String[] args) {

		try {
			CombineUtil.print(combineEx(3, 3));

		} catch (Exception e) {
			e.printStackTrace();
		}  

	}

版本二

public class CombinationEx {

	private List<String> list = new ArrayList<String>();

	private void mn(int m, int n) {
		if ( m < n) {
			throw new IllegalArgumentException("参数异常"); 
		}

		BitSet bs = new BitSet(m);
		for (int i = 0; i < n; i++) {
			bs.set(i, true);
		}

		do {
			printAll(m, bs);
		} while(moveNext(bs, m)); 
	}

	private void printAll(int m, BitSet bs) {
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < m; i++) {
			if (bs.get(i)) {
				sb.append("1").append(",");
			} else {
				sb.append("0").append(",");
			}
		}
		sb.setLength(sb.length() - 1);
		list.add(sb.toString());
	}

	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 = 0; i < end; i++) {
			bs.set(i, false);
		}

		for (int i = 0; i < end - start - 1; i++) {
			bs.set(i);
		}

		bs.set(end);
		return true;
	}

	private List<String> getList() {
		return list;
	}

	public static void main(String[] args) {
		CombinationEx co = new CombinationEx();
		co.mn(5, 3);
		for (int i = 0; i < co.getList().size(); i++) {
			System.out.println(co.getList().get(i));
		}
	}
}

下面介绍全排列的算法

public class Arrange {
	private int total = 0;
	private ArrayList<String> arrangeList = new ArrayList<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> getArrangeList() {
		return arrangeList;
	}

	public static void main(String args[]) {
		// String list[] = { "1", "2", "3", "4", "5" };
		String list[] = { "1", "2", "3" };
		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);
	}
}