hanyeah

之前学习过生成全排列的算法。

全排列-邻位对换法、全排列-递归法、生成全排列-递增进位制法

再来学习一下全组合的生成算法。

组合就是从n个数里边挑m个数。

算法之排列与组合算法 | 董的博客 (dongxicheng.org)

文章中介绍了3种方法。我实现了两种。

// 测试效率
var a = [1,2,3,4,5,6,7,8,9,0];
combine(a, 5);

// 测试正确性
// var a = [1, 2, 3, 4];
// combine(a, 2);

function combine(a, m){
	var M = [];
	console.time("递归法用时：");
	combine0(a, a.length - 1, m - 1, [], M);
	console.timeEnd("递归法用时：");
	console.log(M);

	console.time("二进制法用时：");
	M = combine1(a, m);
	console.timeEnd("二进制法用时：");
	console.log(M);
}

function combine0(a, n, m, b, M) {
	for(var i = n; i >= m; i--) {
		b[m] = a[i];
		if(m === 0) {
			M.push(b.concat());
		} else {
			combine0(a, i - 1, m - 1, b, M);
		}
	}
}

function combine1(a, m) {
	var M = [];
	var n = a.length;
	var max = 1 << n;
	for (var i = 0; i < max; i++) {
		var num = 0;
		var b = [];
		for(var j = 0; j < n; j++) {
			if((i >> j) & 1){
				num++;
				b.push(a[j]);
			}
		}
		if (num === m) {
			M.push(b);
		}
	}
	return M;
}

递归法比较快。

二进制转化法，即，将每个组合与一个二进制数对应起来，枚举二进制的同时，枚举每个组合。

如字符串：abcde 

 00000 <–> null 

 00001<–> e 

 00010 <–> d 

 … … 

 11111 <–> abcde