JavaScript实现列举某集合中指定长度的子集

reference-site-list

[] ()

steps

问题

用JavaScript实现找 {A, B, C, D, E} 这个集合中所有长度为4的子集

分析：

这个问题其实就是列举出ABCDE中所有长度为4的组合，属于数学的排列组合中的组合问题。首先要将找规律，找到存储组合的数据结构，之前已经做过全排列的问题了，用树去存储。
简单分析一下，其实也是用树去存储组合。根据高中的知识可以知道，排列的列举，组合的列举，用树的模型去展示，思路就非常清晰了。

                  |- D
           |- C - |
           |      |- E
    |- B - |          
    |      |
    |      |- D - |- E
A - |
    |
    |- C - |- D - |- E


B - |- C - |- D - |- E

用树展示出来，思路一下子就来了，但是要用代码把思路写出来，其实还不算简单，自己分析了很久，总算用了一个上午把代码完成了。

第一步：生成根节点数组，根据树的总深度来算根节点数组的起始位置，很明显，要满足深度，数组最大的值为arr.length - deep, 所以知道了根节点的范围是给定数组的[0, arr.length - deep]这个闭区间范围

第二步：从根节点出发生成深度为deep的树，树的生成和遍历，很明显会用到递归。

在生成树的时候，要确定该节点的子节点的范围，这里是难点，起点很简单就是当前节点在数组中的位置往后移动一位，所以知道了我们的数据用单独的数字是不行的，必须是一个链表节点对象，保存在数组中的位置(index)和数据值(val)。
确定树的子节点的终点位置，这又是一个需要认真思考的点，先说结论是：arr.length - (deep - cur), deep是树的最大深度，cur是该节点的当前深度，如果要用语言描述去理解的话，是这样的，arr.length - deep是整个数组保证deep深度的最远位置，但是当前已经在cur深度了，起点往后移动了cur，要保存deep，不能再减deep，deep这个值要变小cur,所以要减去cur。这个是我后来自己想的解释，之前写代码的时候真的是靠灵感去把这个范围写出来的，没有明确的逻辑，脑子里灵光一闪，应该就是它，然后去验证，最后自己来找合理的解释，所以我这里表述的时候，是先说答案，再说解释，不得不说，写代码比做数学题简单，可以靠灵感去猜然后去验证结果，就好像物理一样做实验去验证理论猜想，我觉得计算机可以看作是偏物理应用的数学分支。
还有一个比较重要的点，在控制递归生成树的深度的时候，要做好判断，cur是从1开始的，只有当当前深度小于最大深度（不能等于最大深度）时，才能够生成子节点，其实从arr.length - (deep - cur)这个范围也可以看出cur必须要小于deep,不能等于，等于的话就数组下标越界了。从树的角度来看，如果等于deep的话，相当于叶子节点下又去生成子节点了，这很明显深度超过deep了。
最后树的遍历和之前全排列那里是一样的思路，关键还是在每一层进行深拷贝缓存根节点到该层节点之间经历过的所有节点，叶子节点去push到结果数组中。

code

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Combo</title>
</head>
<body>
<button onclick="btnClick()">click</button>
</body>
<script>
    function btnClick() {
        var arr = ['A', 'B', 'C', 'D', 'E'];
        var deep = 4;
        var linkArr = [];
        for (var i = 0; i < arr.length; i++) {
            var item = {
                index: i,
                val: arr[i]
            }; // 因为生成树中的子节点的范围要用到在arr中的位置，所以这里这样构建包含index和val的对象很关键
            linkArr.push(item);
        }

        var rootArr = [];
        var treeArr = [];
        generateRootArr(linkArr, deep, rootArr, treeArr);
        window.console.log("treeArr", treeArr);

        if (deep > 1) {
            var resultArr = [];
            for (var i = 0; i < treeArr.length; i++) {
                var tree = treeArr[i];
                var temp = [];
                loopTree(tree, temp, resultArr);
            }
            window.console.log('resultArr: ', resultArr);
        }
    }

    // 生成根节点数组, deep >= 1
    function generateRootArr(linkArr, deep, rootArr, treeArr) {
        for (var i = 0; i < linkArr.length - deep + 1; i++) {
            rootArr.push(linkArr[i]);
        }
        if (deep > 1) {
            for (var i = 0; i < rootArr.length; i++) {
                var root = rootArr[i];
                var tree = {
                    val: root,
                    parent: null,
                    children: []
                };
                generateTree(tree, linkArr, 1, deep);
                treeArr.push(tree);
            }
        }
    }

    // 使用递归，根据根节点数组生成树, cur代表树的当前深度，deep代表树的最大深度
    function generateTree(tree, linkArr, cur, deep) {
        var node = tree.val;
        var index = node.index;
        // 在[index + 1, linkArr.length - (deep - cur)]闭区间内建立子节点
        if (cur < deep && index + 1 < linkArr.length) { // 关键判断 cur < deep
            for (var i = index + 1; i <= linkArr.length - (deep - cur); i++) {
                var item = {
                    val: linkArr[i],
                    parent: node,
                    children: []
                };
                tree.children.push(item);
                generateTree(item, linkArr, cur + 1, deep);
            }
        }
    }

    // 使用递归，遍历树生成数组
    function loopTree(tree, path, arr) {
        var temp = path.slice(); // 深拷贝，缓存根节点到当前层级节点的经历的路径数组
        temp.push(tree.val.val);
        var children = tree.children;
        if (children.length > 0) {
            for (var i = 0; i < children.length; i++) {
                var item = children[i];
                loopTree(item, temp, arr);
            }
        } else {
            // 叶子节点
            arr.push(temp);
        }
    }
</script>
</html>