java实现排列组合

这里就直接贴代码了

package com.lh.common.util.permutation;

import java.util.ArrayList;
import java.util.List;

import com.rd.ifaes.common.exception.BussinessException;

/**
 * 统计任三出现的最多的几率的组合
 * 
 * @author lh
 * @date 2016-8-12
 */
public class Copy2OfStatisAnyThree {
	// 组合算法
	// 本程序的思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标
	// 代表的数被选中，为0则没选中。
	// 首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。
	// 然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为
	// “01”组合，同时将其左边的所有“1”全部移动到数组的最左端。
	// 当第一个“1”移动到数组的m-n的位置，即n个“1”全部移动到最右端时，就得
	// 到了最后一个组合。
	// 例如求5中选3的组合：
	// 1 1 1 0 0 //1,2,3
	// 1 1 0 1 0 //1,2,4
	// 1 0 1 1 0 //1,3,4
	// 0 1 1 1 0 //2,3,4
	// 1 1 0 0 1 //1,2,5
	// 1 0 1 0 1 //1,3,5
	// 0 1 1 0 1 //2,3,5
	// 1 0 0 1 1 //1,4,5
	// 0 1 0 1 1 //2,4,5
	// 0 0 1 1 1 //3,4,5
	public static void main(String[] args) {
		Copy2OfStatisAnyThree s = new Copy2OfStatisAnyThree();
		s.printAnyThree();
	}

	/**
	 * 
	 */
	public void printAnyThree() {
		int[] num = new int[] {0, 1, 2, 3, 4, 5 };//, 
		print(combine(num, 4));
	}

	/**
	 * 从n个数字中选择m个数字
	 * 
	 * @param a
	 * @param m
	 * @return
	 */
	public List combine(int[] a, int m) {
		int n = a.length;
		if (m > n) {
			throw new BussinessException("错误！数组a中只有" + n + "个元素。" + m + "大于" + 2 + "!!!");
		}

		List result = new ArrayList();

		int[] bs = new int[n];
		for (int i = 0; i < n; i++) {
			bs[i] = 0;
		}
		// 初始化
		for (int i = 0; i < m; i++) {
			bs[i] = 1;
		}
		boolean flag = true;
		boolean tempFlag = false;
		int pos = 0;
		int sum = 0;
		// 首先找到第一个10组合，然后变成01，同时将左边所有的1移动到数组的最左边
		do {
			sum = 0;
			pos = 0;
			tempFlag = true;
			result.add(print(bs, a, m));

			for (int i = 0; i < n - 1; i++) {
				if (bs[i] == 1 && bs[i + 1] == 0) {
					bs[i] = 0;
					bs[i + 1] = 1;
					pos = i;
					break;
				}
			}
			// 将左边的1全部移动到数组的最左边

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

			// 检查是否所有的1都移动到了最右边
			for (int i = n - m; i < n; i++) {
				if (bs[i] == 0) {
					tempFlag = false;
					break;
				}
			}
			if (tempFlag == false) {
				flag = true;
			} else {
				flag = false;
			}

		} while (flag);
		result.add(print(bs, a, m));

		return result;
	}

	private int[] print(int[] bs, int[] a, int m) {
		int[] result = new int[m];
		int pos = 0;
		for (int i = 0; i < bs.length; i++) {
			if (bs[i] == 1) {
				result[pos] = a[i];
				pos++;
			}
		}
		return result;
	}

	private void print(List 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();
		}
	}
}

 

package com.lh.common.util.permutation;

import java.util.ArrayList;
import java.util.List;

import com.rd.ifaes.common.exception.BussinessException;

/**
 * 排列组合工具类
 * @version 3.0
 * @author lh
 * @date 2016年8月12日
 */
public class PermutationUtils {
	
	static final int [] NUM_1 = {1};
	static final int [] NUM_2 = {1, 2};
	static final int [] NUM_3 = {1, 2, 3};
	static final int [] NUM_4 = {1, 2, 3, 4};
	static final int [] NUM_5 = {1, 2, 3, 4, 5};
	static final int [] NUM_6 = {1, 2, 3, 4, 5, 6};
	static final int [] NUM_7 = {1, 2, 3, 4, 5, 6, 7};
	static final int [] NUM_8 = {1, 2, 3, 4, 5, 6, 7, 8};
	static final int [] NUM_9 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
	
	
	/**
	 * 排列组合计算
	 * @author lh
	 * @date 2016年8月12日
	 * @param count	组合元素数量
	 * @return
	 */
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static List calculate(int count){
		if(count > 9){
			throw new BussinessException("Currently does not support large digits");
		}
		int [] numdefault = getNumDefault(count);
		
		int [] numarray = new int[count];
		switch (count) {
		case 1:
			numarray = NUM_1;
			break;
		case 2:
			numarray = NUM_2;
			break;
		case 3:
			numarray = NUM_3;
			break;
		case 4:
			numarray = NUM_4;
			break;
		case 5:
			numarray = NUM_5;
			break;
		case 6:
			numarray = NUM_6;
			break;
		case 7:
			numarray = NUM_7;
			break;
		case 8:
			numarray = NUM_8;
			break;
		case 9:
			numarray = NUM_9;
			break;
		default:
			break;
		}
		Copy2OfStatisAnyThree s = new Copy2OfStatisAnyThree();
		List list = new ArrayList();
		list.add(numdefault);
		for (int i = 1; i < count; i++) {
			list.addAll( reset(s.combine(numarray, i), count));			
		}
		list.add(numarray);
		return list;
	}
	
	/**
	 * 重新归位
	 * @author lh
	 * @date 2016年8月12日
	 * @param l
	 * @param numdefault
	 * @param len
	 * @return
	 */
	@SuppressWarnings({ "rawtypes", "unchecked" })
	private static List reset(List l, int len) {
		List list = new ArrayList();
		for (int i = 0; i < l.size(); i++) {
			int[] b = getNumDefault(len);
			// 填充值
			int[] a = (int[]) l.get(i);
			for (int j : a) {
				b[j - 1] = j;
			}
			list.add(b);
		}
		return list;
	}
	
	/**
	 * 给定数组默认值
	 * @author lh
	 * @date 2016年8月12日
	 * @param count
	 * @return
	 */
	public static int[] getNumDefault(int count){
		int[] b = new int [count];
		for (int k = 0; k < b.length; k++) {
			b[k] = 0;
		}
		return b;
	}

}

 测试用例如下：

package com.lh.common.util.permutation;

import java.util.List;

import org.junit.Test;

public class PermutationUtilsTest {
	
	/**
	 * 排列组合
	 * 
	 * @author LH
	 * @date 2016年8月12日
	 */
	@SuppressWarnings("rawtypes")
	@Test
	public void testPermutation() {
		int count = 4;
		System.out.println(Math.pow(2d, Double.valueOf(count)));
		List list = PermutationUtils.calculate(count);
		System.out.println("list.size=" + list.size());
		print(list);
	}

	@SuppressWarnings("rawtypes")
	private static void print(List 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();
		}
	}

}

 

The end!