Java 组合数算法

今天工作中遇到一个问题需要一个组合数算法。google了一会，没有找到合适的，于是就自己写了一个。主要是用了一个递归算法。发出来分享一下，有用的着的就拿去，觉得写得不好的就拍点砖，提点建议。

 

import java.util.*;

public class Combination
{
	public static void main(String[] args)
	{
		Vector testData = new Vector(Arrays.asList(1, 2, 3, 4, 5, 6));
		Vector results = getAllCombinations(testData);
		for(int i=0; i<results.size(); i++)
			System.out.println(results.elementAt(i));
	}

	public static Vector getAllCombinations(Vector data)
	{
		Vector allCombinations = new Vector();
		for(int i=1; i<=data.size(); i++)
		{
			Vector initialCombination = new Vector();
			allCombinations.addAll(getAllCombinations(data, i));
		}

		return allCombinations;
	}

	public static Vector getAllCombinations(Vector data, int length)
	{
		Vector allCombinations = new Vector();
		Vector initialCombination = new Vector();
		combination(allCombinations, data, initialCombination, length);
		return allCombinations;
	}

	private static void combination(Vector allCombinations, Vector data, 
		Vector initialCombination, int length)
	{
		if(length == 1)
		{
			for(int i=0; i<data.size(); i++)
			{
				Vector newCombination = new Vector(initialCombination);
				newCombination.add(data.elementAt(i));
				allCombinations.add(newCombination);
			}
		}

		if(length > 1)
		{
			for(int i=0; i<data.size(); i++)
			{
				Vector newCombination = new Vector(initialCombination);
				newCombination.add(data.elementAt(i));

				Vector newData = new Vector(data);
				for(int j=0; j<=i; j++)
					newData.remove(data.elementAt(j));

				combination(allCombinations, newData, newCombination, length - 1);
			}
		}
	}
}

 

测试结果：

[1]
[2]
[3]
[4]
[5]
[6]
[1, 2]
[1, 3]
[1, 4]
[1, 5]
[1, 6]
[2, 3]
[2, 4]
[2, 5]
[2, 6]
[3, 4]
[3, 5]
[3, 6]
[4, 5]
[4, 6]
[5, 6]
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 2, 6]
[1, 3, 4]
[1, 3, 5]
[1, 3, 6]
[1, 4, 5]
[1, 4, 6]
[1, 5, 6]
[2, 3, 4]
[2, 3, 5]
[2, 3, 6]
[2, 4, 5]
[2, 4, 6]
[2, 5, 6]
[3, 4, 5]
[3, 4, 6]
[3, 5, 6]
[4, 5, 6]
[1, 2, 3, 4]
[1, 2, 3, 5]
[1, 2, 3, 6]
[1, 2, 4, 5]
[1, 2, 4, 6]
[1, 2, 5, 6]
[1, 3, 4, 5]
[1, 3, 4, 6]
[1, 3, 5, 6]
[1, 4, 5, 6]
[2, 3, 4, 5]
[2, 3, 4, 6]
[2, 3, 5, 6]
[2, 4, 5, 6]
[3, 4, 5, 6]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 6]
[1, 2, 3, 5, 6]
[1, 2, 4, 5, 6]
[1, 3, 4, 5, 6]
[2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]

评论

3 楼 chaos.wql 2009-03-06  

递归算法........
个人觉得学习尚可，工作中没什么使用价值

2 楼 yangyi 2009-03-05  

var arr = [1,2,3];
globalArray = [];
function cal(array){
	if(array.length == 0)
		return;
	if(globalArray.contains(array.join())){
		return;
	}else{
		globalArray.push(array.join());
	}
	for(var i=0;i<array.length;i++){
		cal(array.except(i));
	}
}

cal(arr);
globalArray.sort();
var str = "";
for(var i=0;i<globalArray.length;i++){
	str += globalArray[i] + "<br/>";
}
document.write(str);

Array.prototype.except = function(i){
	var re = [];
	for(var j=0;j<this.length;j++){
		if(j != i){
			re.push(this[j]);
		}
	}
	return re;
}
Array.prototype.contains = function(o){
	for(var j=0;j<this.length;j++){
		if(this[j] == o){
			return true;
		}
	}
	return false;
}

1 楼 bill.end 2009-03-05  

http://bill-end.iteye.com/admin/blogs/112681