JavaScript实现列举数列中的所有排列
Xplorist Lv6
  2021-12-05 21:57:00 2021-12-05 21:57      

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

reference-site-list

steps

  • x

code

  • 问题：

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

  • 分析：

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

1
2
3
4
5
6
7
8
9
10
11
            | - C - | - D
    | - B - |
    |       | - D - | - C
    |
    |       | - B - | - D
A - | - C - |
    |       | - D - | - B
    |
    |       | - B - | - C 
    | - D - |
            | - C - | - B

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

  • 代码
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
<!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>

  • 本文标题：JavaScript实现列举数列中的所有排列
  • 本文作者：Xplorist
  • 创建时间：2021-12-05 21:57:00
  • 本文链接：https://xplorist.tech/2021/12/05/ca8bd563dceb/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
 评论
// variables $gt-color-main := #6190e8 $gt-color-sub := #a1a1a1 $gt-color-loader := #999999 $gt-color-error := #ff3860 $gt-color-hr := #e9e9e9 $gt-color-comment-txt := #333333 $gt-color-link-active := #333333 $gt-color-btn := #ffffff $gt-size-base := 16px // default font-size $gt-size-border-radius := 5px $gt-breakpoint-mobile := 479px $gt-mask-z-index := 9999 // functions & mixins clearfix() { &:before &:after { display table clear both content "" } } em($px, $base-size = $gt-size-base) { u = unit($px) if (u is 'px') { unit($px / $base-size, 'em') } else { unit($px, u) } } mobile() { @media (max-width $gt-breakpoint-mobile) { {block} } } // variables - calculated $gt-size-loader-dot := em(6px) $gt-size-loader := em(28px) $gt-size-avatar := em(50px) $gt-size-avatar-mobi := em(32px) // styles // Put everything under container to avoid style conflicts .comments-container { .gt-container { box-sizing border-box * { box-sizing border-box } font-size $gt-size-base // common a { color $gt-color-main &:hover { color lighten($gt-color-main, 20%) border-color lighten($gt-color-main, 20%) } &.is--active { color $gt-color-link-active cursor default !important &:hover { color $gt-color-link-active } } } .hide { display none !important } // icons .gt-svg { display inline-block width em(16px) height em(16px) vertical-align sub svg { width 100% height 100% fill $gt-color-main } } .gt-ico { display inline-block &-text { margin-left em(5px) } &-github { width 100% height 100% .gt-svg { width 100% height 100% } svg { fill inherit } } } // loader .gt-spinner { position relative &::before { position absolute top 3px box-sizing border-box width em(12px) height em(12px) margin-top em(-3px) margin-left em(-6px) border 1px solid $gt-color-btn border-top-color $gt-color-main border-radius 50% animation gt-kf-rotate 0.6s linear infinite content '' } } .gt-loader { position relative display inline-block width $gt-size-loader height $gt-size-loader font-style normal // font-size: $gt-size-loader line-height $gt-size-loader border 1px solid $gt-color-loader border-radius 50% animation ease gt-kf-rotate 1.5s infinite &:before { position absolute top 0 left 50% display block width $gt-size-loader-dot height $gt-size-loader-dot margin-top -($gt-size-loader-dot / 2) margin-left -($gt-size-loader-dot / 2) background-color $gt-color-loader border-radius 50% content '' } } // avatar .gt-avatar { display inline-block width $gt-size-avatar height $gt-size-avatar +mobile() { width $gt-size-avatar-mobi height $gt-size-avatar-mobi } img { width 100% height auto border-radius 3px } &-github { width $gt-size-avatar - em(2px) height $gt-size-avatar - em(2px) cursor pointer +mobile() { width $gt-size-avatar-mobi - em(2px) height $gt-size-avatar-mobi - em(2px) } } } // button .gt-btn { display inline-block padding em(12px) em(20px) color $gt-color-btn font-size em(12px) line-height 1 white-space nowrap text-decoration none background-color $gt-color-main border 1px solid $gt-color-main border-radius $gt-size-border-radius outline none cursor pointer &-text { font-weight 400 } &-loading { position relative display inline-block width em(12px) height em(16px) margin-left em(8px) vertical-align top } &.is--disable { cursor not-allowed opacity 0.5 } &-login { margin-right 0 } &-preview { color $gt-color-main background-color var(--background-color) &:hover { background-color var(--second-background-color) } } &-public { &:hover { background-color lighten($gt-color-main, 20%) border-color lighten($gt-color-main, 20%) } } } } &-loadmore // loadmore /* error */ .gt-error { margin em(10px) color $gt-color-error text-align center } // initing .gt-initing { padding em(20px) 0 text-align center &-text { margin em(10px) auto font-size 92% } } // no int .gt-no-init { padding em(20px) 0 text-align center } // link .gt-link { border-bottom 1px dotted $gt-color-main &-counts &-project { text-decoration none } } // meta .gt-meta { position relative z-index 10 margin em(20px) 0 padding em(16px) 0 font-size em(16px) border-bottom 1px solid $gt-color-hr clearfix() } .gt-counts { margin 0 em(10px) 0 0 color var(--default-text-color) } .gt-user { float right margin 0 font-size 92% &-pic { width 16px height 16px margin-right em(8px) vertical-align top } &-inner { display inline-block cursor pointer .gt-user-name { color var(--default-text-color) } } .gt-ico { margin 0 0 0 em(5px) svg { fill var(--default-text-color) } } .is--poping { .gt-ico { svg { fill $gt-color-main } } } } .gt-version { margin-left em(6px) color $gt-color-sub } .gt-copyright { margin 0 em(15px) em(8px) padding-top em(8px) border-top 1px solid var(--border-color) } // popup .gt-popup { position absolute top em(38px) right 0 display inline-block padding em(10px) 0 font-size em(14px) letter-spacing 0.5px background var(--background-color) border 1px solid var(--border-color) .gt-action { position relative display block margin em(8px) 0 padding 0 em(18px) text-decoration none cursor pointer &.is--active { &:before { position absolute top em(7px) left em(8px) width em(4px) height em(4px) background $gt-color-main content '' } } } } // header .gt-header { position relative display flex &-comment { flex 1 margin-left em(20px) +mobile() { margin-left em(14px) } } &-textarea { display block box-sizing border-box width 100% min-height em(82px) max-height em(240px) padding em(12px) color var(--default-text-color) font-size em(14px) word-wrap break-word background-color var(--fourth-text-color) border 1px solid var(--border-color) border-radius $gt-size-border-radius outline none transition all 0.25s ease resize vertical &:hover { background-color var(--background-color) } } &-preview { padding em(12px) background-color var(--background-color) border 1px solid var(--border-color) border-radius $gt-size-border-radius } &-controls { position relative margin em(12px) 0 0 clearfix() +mobile() { margin 0 } &-tip { color $gt-color-main font-size em(14px) text-decoration none vertical-align sub +mobile() { display none } } .gt-btn { float right margin-left em(20px) +mobile() { float none width 100% margin em(12px) 0 0 } } } } &:after { position fixed top 0 right 0 bottom 100% left 0 opacity 0 content '' } &.gt-input-focused { position relative &:after { position fixed top 0 right 0 bottom 0 left 0 z-index $gt-mask-z-index background #000 opacity 0.6 transition opacity 0.3s, bottom 0s content '' } .gt-header-comment { z-index $gt-mask-z-index + 1 } } // comments .gt-comments { padding-top em(20px) &-null { text-align center } &-controls { margin em(20px) 0 text-align center } } // comment .gt-comment { position relative display flex padding em(10px) 0 &-content { flex 1 margin-left em(20px) padding em(12px) em(16px) overflow auto background-color var(--second-background-color) transition all ease 0.25s +mobile() { margin-left em(14px) padding em(10px) em(12px) } } &-header { position relative margin-bottom em(8px) font-size em(14px) } &-block-1 { float right width em(32px) height em(22px) } &-block-2 { float right width em(64px) height em(22px) } &-username { color $gt-color-main font-weight 500 text-decoration none &:hover { text-decoration underline } } &-text { margin-left em(8px) color $gt-color-sub } &-date { margin-left em(8px) color $gt-color-sub } &-like &-edit &-reply { position absolute height em(22px) &:hover { cursor pointer } } &-like { top 0 right em(32px) } &-edit &-reply { top 0 right 0 } &-body { // color: $gt-color-comment-txt !important color var(--second-text-color) !important .email-hidden-toggle a { display inline-block height 12px padding 0 9px color #444d56 font-weight 600 font-size 12px line-height 6px text-decoration none vertical-align middle background #dfe2e5 border-radius 1px &:hover { background-color #c6cbd1 } } .email-hidden-reply { display none white-space pre-wrap .email-signature-reply { margin 15px 0 padding 0 15px color #586069 border-left 4px solid #dfe2e5 } } .email-hidden-reply.expanded { display block } } &-admin { .gt-comment-content { background-color var(--fourth-text-color) } } } @keyframes gt-kf-rotate { 0% { transform rotate(0) } 100% { transform rotate(360deg) } } }