实现某数组的组合算法有很多种,其中以递归为最多,而且网上不乏高效率的示例,这里只演示一种实现方式.
代码
1
/*
*
2 * 递归组合
3 * 从 arr[1
n] 中任选 num(0 < num <= n) 个数的所有组合
4 */
5 function combine(arr, num) {
6 var r = [];
7 ( function f(t, a, n) {
8 if (n == 0 ) return r.push(t);
9 for ( var i = 0 , l = a.length; i <= l - n; i ++ ) {
10 f(t.concat(a[i]), a.slice(i + 1 ), n - 1 );
11 }
12 })([], arr, num);
13 return r;
14 }
15
16 /* * 测试代码 * */
17 combine([ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ], 3 );
2 * 递归组合
3 * 从 arr[1
n] 中任选 num(0 < num <= n) 个数的所有组合4 */
5 function combine(arr, num) {
6 var r = [];
7 ( function f(t, a, n) {
8 if (n == 0 ) return r.push(t);
9 for ( var i = 0 , l = a.length; i <= l - n; i ++ ) {
10 f(t.concat(a[i]), a.slice(i + 1 ), n - 1 );
11 }
12 })([], arr, num);
13 return r;
14 }
15
16 /* * 测试代码 * */
17 combine([ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ], 3 );
然而,事情并不是都这么简单,现在遇到一个新问题,我定义了一个新的数组
var arr = [[1,2,3],
[1,2,3,4,5],
[2,4,6,8],
[3,5,7,9]];
要求是从数组arr的每个元素中任意取一个值出来,组成一个长度为4(即arr.length)的组合,求有多少种组合方式.这个时候,如果想要再次利用上面的递归,就需要改造一下了.主要变化就是在每次传入匿名函数的参数上,以保证每次要循环的数组是arr的下一个元素而不是当前元素本身.
代码
1
function
combine_ex(arr) {
2 var r = [];
3 ( function f(t, a, n) {
4 if (n == 0 ) return r.push(t);
5 for ( var i = 0 ; i < a[n - 1 ].length; i ++ ) {
6 f(t.concat(a[n - 1 ][i]), a, n - 1 );
7 }
8 })([], arr, arr.length);
9 return r;
10 }
2 var r = [];
3 ( function f(t, a, n) {
4 if (n == 0 ) return r.push(t);
5 for ( var i = 0 ; i < a[n - 1 ].length; i ++ ) {
6 f(t.concat(a[n - 1 ][i]), a, n - 1 );
7 }
8 })([], arr, arr.length);
9 return r;
10 }
接着就有新问题了,如果要对上面变长的二维数组,要求是从数组arr的每个元素中任意取一个值出来,组成一个长度为指定任意值的组合怎么办?要说办法也就在这里了,无非就是将前面两种函数一起使用,先求出最长组合的集合,然后对每一个元素求指定长度的组合.
总归,组合算法的需求是多样的,不管怎么变,都能从最基本的算法进行衍变,派生出复合的算法出来.