js中获取数组的全部子集数组和特定长度子集数组

发表于 |

小伙伴最近在做一个数据处理分析的东东，中间有一个需要获取数组全部子集数组列表的需求，虽然ES6中增加了一种新的数据类型语法糖Set，不过还是没有提供获取集合子集的方法，所以，就自己写了一个，这里特别做一次记录，以方便下次自己使用。
如给定数组arr = [1,2,3],返回全部子集数组为[[1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]],如果返回长度为2的子集数组则返回值[[1,2], [1,3], [2,3]].
整体思路上，可以先获取特定长度子集的数组，然后对个长度子集列表做一个归并即可，示例代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
var arr = [1,2,3,4,5,6,7,8,9,10];

//保存最后的子集列表
var arr_list = [];

//从start_index索引开始，取出长度为sub_len的子集，并与前置子集部分forehead_arr做归并，得到结果存入全局变量arr_list中
function get_sub(arr,forehead_arr = [],start_index,sub_len) {
    var i = start_index;
    for(; i < arr.length; i++) {
        var cur_sub_len = sub_len;  //记录子集筛选开始索引
        var tmp_arr = arr_clone(forehead_arr);
        tmp_arr.push(arr[i]);
        // 当自己长度大于1时需要递归处理
        if(--cur_sub_len > 0) {
            get_sub(arr,arr_clone(tmp_arr),i+1,cur_sub_len)
        } else {
            arr_list.push(tmp_arr);//结束后放入二维数组
        }
    }
}

//对原数组进行深拷贝
function arr_clone(arr) {
    var new_arr = [];
    for(item of arr) {
        new_arr.push(item);
    }
    return new_arr;
}

// 获取数组全部子集
function get_all(arr) {
    for(var i = 0; i < arr.length; i++) {
        get_sub(arr,[],0,i+1);
    }
}


// get_sub(arr,[],0, 3);  从arr[0]开始，获取数组长度为3的子集列表
get_all(arr)
console.log(arr_list);

另一个只能获取全部子集列表，无法获取特定长度子集列表的版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var arr = [1,2,3];

function subSet(set){
    if(set.length == 0){
        return []
    }
    var temp = set.shift()
    return add(subSet(set),temp)   
}

function add(list,temp){
    for(var i=0,len=list.length;i<len;i++){
        var item = list[i]
        var new_item = clone(item)
        new_item.push(temp)
        list.push(new_item)
    }
    list.push([temp]) 
    return list
}

function clone(data){
    return data.map(item=>item)
}

console.log(subSet(arr))

ps:
对于数组所有子集遍历， 还可以有另外一个思路， 比如数组有3个元素， 就构造一个9未的二进制数，每位表示一个元素，那么所有的子集就是000，001， 010，011，100，101，110，111这几种组合了， 和bitmap的类似的思维，依次对应一下就可以了。