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的方法就好了，如果还可能更多的数据，甚至数据数不定，这个其实要用递归或者分治算法（用来解决递归算法层数过多的问题），这个就比较复杂了。

---

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

1. 根据数组元素数量N，可以分成N段二进制数据位
2. 根据每个数据元素An,则N段二进制数位的值范围就可以得出（二进制位数），并有一个对应的最大值An-1
3. 所有的组合就和这个N段2进制位数（假设总共有M位），则0-2^M-1共2^M个数中滤除各段不符合情况后的数据，根据段分开后对应值的组合，即遍历0-这个二进制数范围内
4. 这样遍历一遍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);