javascript 数组排列组合

Question

现在要实现一个，类似于排列组合的方法，给定一个数组(数组内全部是数字)，变化数组内每个值的，形成不同的组合。就像下面这样。例如：[2,2,3] 排列出 223 = 12个不同组合[[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3]]注:[2,2,3] 是不定的数字与数据长度，听起来有点可怕(这要遍历多少次啊)，可实际需求就是这样补充: 如果是固定数组长度，@superme已经给出答案，现在的问题是：未知数组长度与数字大小，目前我能想到的方式是，使用 eval 来处理未知数，加上superme的方法遍历，这样比递归稍简单一些。请问大家还有什么好的方法吗？如果大家有好的办法，或实现方案，由于本人理解能力偏低，大神们请尽量上一个实现函数，在下感激不尽。

Answer 1

 var arr = [2, 2, 3];

  var p = []

  for (var i = 1; i <= arr[0]; i++) {

    for (var j = 1; j <= arr[1]; j++) {

      for (var k = 1; k <= arr[2]; k++) {

        p.push([i, j, k])

      }

    }

  }

  console.log(p);

    let arr = [2,4,2,3];

    var _arr = [];

    for (var i = 0; i < arr.length; i++) {

      var s = [];

      for (var j = 1; j <= arr[i]; j++) {

        s.push(j);

      }

      _arr.push(s);

    }

   var p =  _arr.reduce(function (pre, cur) {

      var a = [];

      for (var i = 0; i < pre.length; i++) {

        for (var j = 0; j < cur.length; j++) {

          a.push([].concat(pre[i], cur[j]))

        }

      }

     return a;

    })

    console.log(p)

应该可以nlog(n) 时间复杂度,但是不会

let arr = [23,35,23,36,5];

var _arr = [];

for (var i = 0; i < arr.length; i++) {

  var s = [];

  for (var j = 1; j <= arr[i]; j++) {

    s.push(j);

  }

  _arr.push(s);

}

var p = [];

function f(arr) {

  var len = arr.length;

  if (len < 2) {

    return arr[0];

  }

  var mid = Math.ceil(len / 2),

    left = arr.slice(0, mid),

    right = arr.slice(mid);

  return z(f(left), f(right));

}

function z(left, right) {

  var a = [];

  for (var i = 0; i < left.length; i++) {

    for (var j = 0; j < right.length; j++) {

      a.push([].concat(left[i], right[j]))

    }

  }

  return p.concat(a);

}

console.log(p)

最后一种效率会高一点

Answer 2

   var arr = [2, 2, 3,2];

            var curr=[];

            for(var i=1;i<=arr.length;i++){

                curr.push(1)

            }

            var result=[];

            result.push(curr.concat());

            var len=arr.length;

            

            fk:while(true){

                var a=curr[len-1]++;

                for(var i=len-1;i>=0;i--){

                    if(curr[i]>arr[i]){

                        if(i>=1){

                                curr[i-1]++;

                                curr[i]=1;

                        }else{

                            break fk;

                        }

                        

                    

                        

                    }

                    

                }

                var t=curr.concat();

                result.push(t);

            }

            console.log(result);

和一楼的做法不一样， 这个思路是，每次最后一位 +1 ，然后检查，是不是需要定位了， 定位的条件是 初始给的数组每个位的值。

Answer 3

如果你最多是3个数据，就是supreme的方法就好了，如果还可能更多的数据，甚至数据数不定，这个其实要用递归或者分治算法（用来解决递归算法层数过多的问题），这个就比较复杂了。

其实这个问题用位运算是比较好算的，也可以结合分治来处理：

根据数组元素数量N，可以分成N段二进制数据位

根据每个数据元素An,则N段二进制数位的值范围就可以得出（二进制位数），并有一个对应的最大值An-1

所有的组合就和这个N段2进制位数（假设总共有M位），则0-2^M-1共2^M个数中滤除各段不符合情况后的数据，根据段分开后对应值的组合，即遍历0-这个二进制数范围内

这样遍历一遍0-2^M，滤除各段不符合的情况就可以得出所有合适情况了。

以[2,2,3]为例来介绍，我们从低位开始作为处理

2,表示1,2 二种状态，对应1位二进制，最大值2-1=1

2,表示1,2 二种状态，对应1位二进制，最大值2-1=1

3，表示1,2,3 3种状态，对应2位二进制，最大值3-1=2

这样，需要1+1+2共4位二进制数来表示所有组合，其中还需要滤除最高位的2个段的一些情况（2位2进制数其实可以表示4种状态的），后面注意是低位开始对应

00 0 0，对应1,1,1

00 0 1, 对应2,1,1

00 1 0，对应1,2,1

00 1 1，对应2,2,1

01 0 0，对应1,1,2

01 0 1，对应2,1,2

01 1 0，对应1,2,2

01 1 1，对应2,2,2

10 0 0，对应1,1,3

10 0 1，对应2,1,3

10 1 0，对应1,2,3

10 1 1，对应2,2,3

11 0 0 位段超出不符合

11 0 1 位段超出不符合

11 1 0 位段超出不符合

11 1 1 位段超出不符合

算法思路就介绍到这里，实现其实不是太复杂，不过如果位数太多了（超出语言处理范围）还是需要分治

这个问题如果真实的规模比较大，还需要考虑空间复杂度和时间复杂度问题，递归肯定是不行的，就是转换递归为循环，空间复杂度也不一定好（当然实际情况下也不该由javascript来处理这么大复杂度的问题，但仍需考虑不是）。

这里再给出一个循环的方式

var arr = [2,2,3,2,5];           

function MC(inarr,n){

    var rt=[];

    for(var i=0;i<inarr.length;i++){

       for(var j=1;j<=n;j++){

           var t=inarr[i].concat();

           t.push(j);

           rt.push(t)

       }

    }

    return rt;

}

var mrt=[[]];

for(var i=0;i<arr.length;i++){

    mrt=MC(mrt,arr[i]);

}

console.log(mrt);