javascript 數(shù)組排列組合

如果你最多是3個數(shù)據(jù)，就是supreme的方法就好了，如果還可能更多的數(shù)據(jù)，甚至數(shù)據(jù)數(shù)不定，這個其實(shí)要用遞歸或者分治算法（用來解決遞歸算法層數(shù)過多的問題），這個就比較復(fù)雜了。

其實(shí)這個問題用位運(yùn)算是比較好算的，也可以結(jié)合分治來處理：

1. 根據(jù)數(shù)組元素?cái)?shù)量N，可以分成N段二進(jìn)制數(shù)據(jù)位
2. 根據(jù)每個數(shù)據(jù)元素An,則N段二進(jìn)制數(shù)位的值范圍就可以得出（二進(jìn)制位數(shù)），并有一個對應(yīng)的最大值A(chǔ)n-1
3. 所有的組合就和這個N段2進(jìn)制位數(shù)（假設(shè)總共有M位），則0-2^M-1共2^M個數(shù)中濾除各段不符合情況后的數(shù)據(jù)，根據(jù)段分開后對應(yīng)值的組合，即遍歷0-這個二進(jìn)制數(shù)范圍內(nèi)
4. 這樣遍歷一遍0-2^M，濾除各段不符合的情況就可以得出所有合適情況了。

以[2,2,3]為例來介紹，我們從低位開始作為處理
2,表示1,2 二種狀態(tài)，對應(yīng)1位二進(jìn)制，最大值2-1=1
2,表示1,2 二種狀態(tài)，對應(yīng)1位二進(jìn)制，最大值2-1=1
3，表示1,2,3 3種狀態(tài)，對應(yīng)2位二進(jìn)制，最大值3-1=2
這樣，需要1+1+2共4位二進(jìn)制數(shù)來表示所有組合，其中還需要濾除最高位的2個段的一些情況（2位2進(jìn)制數(shù)其實(shí)可以表示4種狀態(tài)的），后面注意是低位開始對應(yīng)
00 0 0，對應(yīng)1,1,1
00 0 1, 對應(yīng)2,1,1
00 1 0，對應(yīng)1,2,1
00 1 1，對應(yīng)2,2,1
01 0 0，對應(yīng)1,1,2
01 0 1，對應(yīng)2,1,2
01 1 0，對應(yīng)1,2,2
01 1 1，對應(yīng)2,2,2
10 0 0，對應(yīng)1,1,3
10 0 1，對應(yīng)2,1,3
10 1 0，對應(yīng)1,2,3
10 1 1，對應(yīng)2,2,3
11 0 0 位段超出不符合
11 0 1 位段超出不符合
11 1 0 位段超出不符合
11 1 1 位段超出不符合

算法思路就介紹到這里，實(shí)現(xiàn)其實(shí)不是太復(fù)雜，不過如果位數(shù)太多了（超出語言處理范圍）還是需要分治

這個問題如果真實(shí)的規(guī)模比較大，還需要考慮空間復(fù)雜度和時間復(fù)雜度問題，遞歸肯定是不行的，就是轉(zhuǎn)換遞歸為循環(huán)，空間復(fù)雜度也不一定好（當(dāng)然實(shí)際情況下也不該由javascript來處理這么大復(fù)雜度的問題，但仍需考慮不是）。

這里再給出一個循環(huán)的方式

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);

            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 ，然后檢查，是不是需要定位了， 定位的條件是 初始給的數(shù)組每個位的值。

  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)

應(yīng)該可以nlog(n) 時間復(fù)雜度,但是不會

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)

最后一種效率會高一點(diǎn)