递归实现js数组全排列

作者: GDUF_XRT | 来源:发表于2017-09-20 17:31 被阅读1976次

    规律

    当n = 1时, 数组arr = [A],全排列结果为

    [A];

    当n = 2时, 数组arr = [A, B],全排列结果为

    [A, B]
    [B, A];

    当n = 3时, 数组arr = [A, B, C],全排列结果为

    [A, B, C]
    [A, C, B]
    [B, A, C]
    [B, C, A]
    [C, A, B]
    [C, B, A]

    到n = 3时可以看出全排列有以下规律

    1. 固定第一个元素,将剩下的元素进行全排列处理;
    2. 将第一个元素与依次与第i(1<i<=arr.length)个元素互换,将剩下的元素进行全排列处理;
    3. 结束

    很适合使用递归解决。只要写一个全排列函数permutation,能固定一个下标为i的元素,剩下元素再进行全排列即可。

    js实现

    在ES5中使用闭包将全排列函数封装。

    // 数组全排列
    function Permutation(arr) {
        this.len = 0;    // 存储全排列次数
        this.arr = arr.concat();   // 传入的数组
        this.result = [];    // 存储全排列结果
    
        // 首次创建对象时初始化方法
        if (typeof Permutation.run == 'undefined') {
            Permutation.prototype.start = function() {
                this.run(0);
            }
    
            // 递归函数(核心方法),index为数组下标
            Permutation.prototype.run = function(index) {
                // 单遍历到数组末端时,将结果储存在result数组中,全排列次数加1
                if (index == this.arr.length - 1) {
                    this.result.push(this.arr.slice());
                    this.len++;
                    return;
                }
    
                for(let i = index; i < this.arr.length; i++) {
                    this.swap(this.arr, index, i);      // 与下标为i的元素交换位置
                    this.run(index + 1);                // 剩下元素全排列
                    this.swap(this.arr, index, i);      // 复原数组
                }
            }
    
            // 交换位置
            Permutation.prototype.swap = function(array, i, j) {
                var t;
                t = array[i];
                array[i] = array[j]; 
                array[j] = t;
            }
        }
    }
    
    var per = new Permutation(['A', 'B', 'C']);
    per.start();
    console.log(per.result);
    console.log(per.len);
    // [ [ 'A', 'B', 'C' ],
    //   [ 'A', 'C', 'B' ],
    //   [ 'B', 'A', 'C' ],
    //   [ 'B', 'C', 'A' ],
    //   [ 'C', 'B', 'A' ],
    //   [ 'C', 'A', 'B' ] ]
    // 6
    

    ES5代码使用动态原型模式创建对象,主要是想让函数封装的尽量像一个类。在ES6中有class,语法可以更加简洁高效。

      // ES6
      class Permutation {
        constructor(arr) {
            this.arr = Array.from(arr);
            this.result = [];
            this.len = 0;
            this.run(0);
        }
    
        run(index) {
            if (index == this.arr.length - 1) {
                this.result.push(Array.from(this.arr));
                this.len++;
                return;
            }
            for(let i = index; i < this.arr.length; i++) {
                [this.arr[index], this.arr[i]] = [this.arr[i], this.arr[index]];
                this.run(index + 1);
                [this.arr[index], this.arr[i]] = [this.arr[i], this.arr[index]];
            }
        }
      }
    
      let p = new Permutation(["A", "B", "C"]);
      console.log(p.result);
      console.log(p.len);
      // [ [ 'A', 'B', 'C' ],
      //   [ 'A', 'C', 'B' ],
      //   [ 'B', 'A', 'C' ],
      //   [ 'B', 'C', 'A' ],
      //   [ 'C', 'B', 'A' ],
      //   [ 'C', 'A', 'B' ] ]
      // 6
    

    以上就是全排列的js实现。
    代码地址:github

    相关文章

      网友评论

        本文标题:递归实现js数组全排列

        本文链接:https://www.haomeiwen.com/subject/bqbnrxtx.html