73

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

どんな助けでも大歓迎です。

4

10 に答える 10

145

これは、再帰ヘルパー関数を使用した非常に単純で短いものです。

function cartesian(...args) {
    var r = [], max = args.length-1;
    function helper(arr, i) {
        for (var j=0, l=args[i].length; j<l; j++) {
            var a = arr.slice(0); // clone arr
            a.push(args[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(args)RESTパラメーター構文を使用する代わりに署名をに変更するだけです。

于 2013-03-09T11:18:13.697 に答える
5

少し調査を行った後、以前の関連する質問を発見しました: JavaScript 配列値のすべての組み合わせを見つける

すべての順列を含む配列の配列を返すように、そこからいくつかのコードを調整しました。

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

以前に指定した配列 ([[0,1]、[0,1,2,3]、[0,1,2]) を取得する作業コピーをhttp://jsfiddle.net/7EakX/に配置しました。 ]) を実行し、結果をブラウザ コンソールに出力します。

于 2013-03-08T18:39:37.763 に答える
3

const charSet = [["A", "B"],["C", "D", "E"],["F", "G", "H", "I"]];
console.log(charSet.reduce((a,b)=>a.flatMap(x=>b.map(y=>x+y)),['']))

于 2020-05-19T12:08:55.493 に答える
2

これを行う別の方法があります。すべての配列のインデックスを、配列の長さを基数として使用して、数字がすべて異なる基数(時刻や日付など)である数値のように扱います。

したがって、最初のデータセットを使用すると、最初の桁は基数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]]));
于 2013-03-09T07:03:17.327 に答える
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;
};
于 2013-03-08T18:01:46.953 に答える