JavaScript - 使用m個元素生成n個數組的組合

Question

我無法提供代碼來生成n個數組中具有m個元素的組合的代碼，使用JavaScript。我已經看到了其他語言的類似問題，但答案包含了我不確定如何翻譯的句法或庫魔術。

考慮這個數據：

[[0,1], [0,1,2,3], [0,1,2]] 

3陣列，具有不同數目的在其中元件。我想要做的是通過組合每個數組中的項目來獲取所有組合。

例如：

0,0,0 // item 0 from array 0, item 0 from array 1, item 0 from array 2 
0,0,1 
0,0,2 
0,1,0 
0,1,1 
0,1,2 
0,2,0 
0,2,1 
0,2,2 

等。

如果數組的數量是固定的，那麼很容易做出硬編碼的實現。但陣列數量可能有所不同：

[[0,1], [0,1]] 
[[0,1,3,4], [0,1], [0], [0,1]] 

任何幫助將不勝感激。

Answer 1

這是一個很簡單，很短一個使用遞歸的輔助功能：

function cartesian() { 
    var r = [], arg = arguments, max = arg.length-1; 
    function helper(arr, i) { 
     for (var j=0, l=arg[i].length; j<l; j++) { 
      var a = arr.slice(0); // clone arr 
      a.push(arg[i][j]); 
      if (i==max) 
       r.push(a); 
      else 
       helper(a, i+1); 
     } 
    } 
    helper([], 0); 
    return r; 
} 

用法：

cartesian([0,1], [0,1,2,3], [0,1,2]); 

要使函數獲得一組數組，請將簽名更改爲function cartesian(arg)，以便arg是一個參數而不是all arguments。

Answer 2

var f = function(arr){ 
    if(typeof arr !== 'object'){ 
     return false; 
    } 

    arr = arr.filter(function(elem){ return (elem !== null); }); // remove empty elements - make sure length is correct 
    var len = arr.length; 

    var nextPerm = function(){ // increase the counter(s) 
     var i = 0; 

     while(i < len) 
     { 
      arr[i].counter++; 

      if(arr[i].counter >= arr[i].length){ 
       arr[i].counter = 0; 
       i++; 
      }else{ 
       return false; 
      } 
     } 

     return true; 
    }; 

    var getPerm = function(){ // get the current permutation 
     var perm_arr = []; 

     for(var i = 0; i < len; i++) 
     { 
      perm_arr.push(arr[i][arr[i].counter]); 
     } 

     return perm_arr; 
    }; 

    var new_arr = []; 

    for(var i = 0; i < len; i++) // set up a counter property inside the arrays 
    { 
     arr[i].counter = 0; 
    } 

    while(true) 
    { 
     new_arr.push(getPerm()); // add current permutation to the new array 

     if(nextPerm() === true){ // get next permutation, if returns true, we got them all 
      break; 
     } 
    } 

    return new_arr; 
}; 

Answer 3

做了一些研究之後，我發現以前的相關的問題： Finding All Combinations of JavaScript array values

我已經適應了一些從那裏的代碼，以便它返回一個包含所有排列的數組的數組：

function(arraysToCombine) { 
    var divisors = []; 
    for (var i = arraysToCombine.length - 1; i >= 0; i--) { 
     divisors[i] = divisors[i + 1] ? divisors[i + 1] * arraysToCombine[i + 1].length : 1; 
    } 

    function getPermutation(n, arraysToCombine) { 
     var result = [], 
      curArray;  
     for (var i = 0; i < arraysToCombine.length; i++) { 
      curArray = arraysToCombine[i]; 
      result.push(curArray[Math.floor(n/divisors[i]) % curArray.length]); 
     }  
     return result; 
    } 

    var numPerms = arraysToCombine[0].length; 
    for(var i = 1; i < arraysToCombine.length; i++) { 
     numPerms *= arraysToCombine[i].length; 
    } 

    var combinations = []; 
    for(var i = 0; i < numPerms; i++) { 
     combinations.push(getPermutation(i, arraysToCombine)); 
    } 
    return combinations; 
} 

我已經把工作副本http://jsfiddle.net/7EakX/，把你前面給陣列（[0,1]，[0,1,2,3]，[0,1,2]）和將結果輸出到瀏覽器控制檯。

Answer 4

這是另一種方式。我將所有數組的索引視爲一個數字，它們的數字都是不同的基數（如時間和日期），使用數組長度作爲基數。

因此，使用您的第一組數據，第一位數字是基數2，第二位數字是基數4，第三位數字是基數3.計數器開始000，然後進入001，002，然後是010.數字對應到數組中的索引，並且由於順序被保留，所以這沒有問題。

，我與它小提琴在這裏工作：http://jsfiddle.net/Rykus0/DS9Ea/1/

這裏是代碼：

// Arbitrary base x number class 
var BaseX = function(initRadix){ 
    this.radix  = initRadix ? initRadix : 1;  
    this.value  = 0; 
    this.increment = function(){ 
     return((this.value = (this.value + 1) % this.radix) === 0); 
    } 
} 

function combinations(input){ 
    var output = [], // Array containing the resulting combinations 
     counters = [], // Array of counters corresponding to our input arrays 
     remainder = false, // Did adding one cause the previous digit to rollover? 
     temp;    // Holds one combination to be pushed into the output array 

    // Initialize the counters 
    for(var i = input.length-1; i >= 0; i--){ 
     counters.unshift(new BaseX(input[i].length)); 
    } 

    // Get all possible combinations 
    // Loop through until the first counter rolls over 
    while(!remainder){ 
     temp  = []; // Reset the temporary value collection array 
     remainder = true; // Always increment the last array counter 

     // Process each of the arrays 
     for(i = input.length-1; i >= 0; i--){ 
      temp.unshift(input[i][counters[i].value]); // Add this array's value to the result 

      // If the counter to the right rolled over, increment this one. 
      if(remainder){ 
       remainder = counters[i].increment(); 
      } 
     } 
     output.push(temp); // Collect the results. 
    } 

    return output; 
} 

// Input is an array of arrays 
console.log(combinations([[0,1], [0,1,2,3], [0,1,2]])); 

Answer 5

只是爲了好玩，這裏是我的第一個答案的解決方案的更多功能性的變體：

function cartesian() { 
    var r = [], args = Array.from(arguments); 
    args.reduceRight(function(cont, factor, i) { 
     return function(arr) { 
      for (var j=0, l=factor.length; j<l; j++) { 
       var a = arr.slice(); // clone arr 
       a[i] = factor[j]; 
       cont(a); 
      } 
     }; 
    }, Array.prototype.push.bind(r))(new Array(args.length)); 
    return r; 
} 

替代，全速我們可以動態編譯我們自己的循環：

function cartesian() { 
    return (cartesian.cache[arguments.length] || cartesian.compile(arguments.length)).apply(null, arguments); 
} 
cartesian.cache = []; 
cartesian.compile = function compile(n) { 
    var args = [], 
     indent = "", 
     up = "", 
     down = ""; 
    for (var i=0; i<n; i++) { 
     var arr = "$"+String.fromCharCode(97+i), 
      ind = String.fromCharCode(105+i); 
     args.push(arr); 
     up += indent+"for (var "+ind+"=0, l"+arr+"="+arr+".length; "+ind+"<l"+arr+"; "+ind+"++) {\n"; 
     down = indent+"}\n"+down; 
     indent += " "; 
     up += indent+"arr["+i+"] = "+arr+"["+ind+"];\n"; 
    } 
    var body = "var res=[],\n arr=[];\n"+up+indent+"res.push(arr.slice());\n"+down+"return res;"; 
    return cartesian.cache[n] = new Function(args, body); 
} 

Answer 6

我建議一個簡單的遞歸generator function：

// Generate all combinations of array elements: 
 
function* cartesian(head, ...tail) { 
 
    let remainder = tail.length ? cartesian(...tail) : [[]]; 
 
    for (let r of remainder) for (let h of head) yield [h, ...r]; 
 
} 
 

 

 
// Example: 
 
for (let c of cartesian([0,1], [0,1,2,3], [0,1,2])) { 
 
    console.log(...c); 
 
}

Answer 7

與ES6遞歸式的

Array.prototype.cartesian = function(a,...as){ 
 
    return a ? this.reduce((p,c) => (p.push(...a.cartesian(...as).map(e => as.length ? [c,...e] : [c,e])),p),[]) 
 
      : this; 
 
}; 
 

 
console.log(JSON.stringify([0,1].cartesian([0,1,2,3], [[0],[1],[2]])));

Answer 8

另一種實現你可以採取通過建立子陣列迭代方法。

var parts = [[0, 1], [0, 1, 2, 3], [0, 1, 2]], 
 
    result = parts.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), [])); 
 

 
console.log(result.map(a => a.join(', ')));

.as-console-wrapper { max-height: 100% !important; top: 0; }