JavaScript实现列举数列中的所有排列

reference-site-list

steps

code

问题：

给定ABCD四个字母，用JavaScript代码实现列举出这几个数字的所有排列情况。

分析：

从初中的数学知识中可以知道，列举排列的所有情况都会以树的形式展示，如下图所示，列举了以A作为根节点的一颗树

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

要用代码列举出所有的排列，就需要生成4棵树，然后遍历4棵树中的值，将结果转换为二维数组

代码

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>align</title>
</head>
<body>
<button onclick="btnClick()">click</button>
</body>
<script>
    function btnClick() {
        var arr = ['A', 'B', 'C', 'D'];
        var result = listAlign(arr);
        window.console.log(result);
    }

    // 列举排列
    function listAlign(arr) {
        var trees = [];
        // 生成4棵树
        for (var i = 0; i < arr.length; i++) {
            var num = arr[i];
            var tree = {
                val: num,
                parent: null,
                children: []
            };
            generateTree(arr, num, tree);
            trees.push(tree);
        }

        // 树转数组
        var result = [];
        for (var i = 0; i < trees.length; i++) {
            var tree = trees[i];
            var arr = [];
            recurseTree(tree, arr, result);
        }
        return result;
    }

    // 使用递归生成树
    function generateTree(arr, num, tree) {
        var temp = arr.slice(); // 浅拷贝
        // 移除数组中该数字，获得该节点的子节点数
        for (var i = 0; i < temp.length; i++) {
            if (temp[i] === num) {
                temp.splice(i, 1);
                i--;
            }
        }
        // 使用数组中剩下的数，生成该数的子节点
        for (var i = 0; i < temp.length; i++) {
            var item = {
                val: temp[i],
                parent: num,
                children: []
            };
            tree.children.push(item);
            generateTree(temp, temp[i], item);
        }
    }

    // 使用递归遍历树
    function recurseTree(node, arr, result) {
        var temp = arr.slice();
        temp.push(node.val); // 缓存到该级时，已经经历过的数字
        if (node.children.length === 0) {
            result.push(temp); // 叶子节点，已经是完整的一个排列，加入结果
        } else {
            var children = node.children;
            for (var i = 0; i < children.length; i++) {
                var child = children[i];
                recurseTree(child, temp, result);
            }
        }
    }
</script>
</html>