JavaScript - m個の要素を持つn個の配列から組み合わせを生成する

Question

JavaScriptでm個の要素を持つn個の配列から組み合わせを生成するコードが出てきています。これについて他の言語でも同様の質問がありましたが、答えに構文やライブラリの魔法が組み込まれているため、翻訳方法がわかりません。

[[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]] 

何か助けが大いに評価されるでしょう。それは順列のすべてを含む配列の配列を返すように、私はそこからコードの一部を適応してきた Finding All Combinations of JavaScript array values

：

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

関数に配列の配列を渡すには、の代わりにargがパラメータになるように、署名をfunction cartesian(arg)に変更します。楽しみのためだけに、ここでのソリューションの多くの機能的変異体は、私の最初の答えに

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

は少し研究を行った後、私は、以前の関連する質問を発見し

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、2番目はベース4、3番目はベース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); 
 
}

ES6再帰的なスタイルで

Answer 7

別の実施

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