JavaScript配列の値のすべての組み合わせを見つける

Question

可変長のN個のJavaScript配列の値のすべてをどのようにして生成できますか？

たとえば、N個のJavaScript配列があるとします。

aef 
aeg 
aeh 
aei 
aej 
bef 
beg 
.... 
dej 

---

を生成する

var first = ['a', 'b', 'c', 'd']; 
var second = ['e']; 
var third = ['f', 'g', 'h', 'i', 'j']; 

（この例では3つの配列が、問題のための配列のそのN数。）

そして私は、出力したいそれらの値のすべての組み合わせ、

EDIT：ここで私が働いているバージョンは、ffriendの受け入れられた答えを基にしています。

var allArrays = [['a', 'b'], ['c', 'z'], ['d', 'e', 'f']]; 

function allPossibleCases(arr) { 
    if (arr.length === 0) { 
    return []; 
    } 
else if (arr.length ===1){ 
return arr[0]; 
} 
else { 
    var result = []; 
    var allCasesOfRest = allPossibleCases(arr.slice(1)); // recur with the rest of array 
    for (var c in allCasesOfRest) { 
     for (var i = 0; i < arr[0].length; i++) { 
     result.push(arr[0][i] + allCasesOfRest[c]); 
     } 
    } 
    return result; 
    } 

} 
var r=allPossibleCases(allArrays); 
//outputs ["acd", "bcd", "azd", "bzd", "ace", "bce", "aze", "bze", "acf", "bcf", "azf", "bzf"] 

Answer 1

これは並べ替えではありません.Wikipediaのpermutations definitionsを参照してください。

しかし、あなたは再帰でこれを達成することができます：あなたはまた、ループでそれを作ることができますが、それは少しトリッキーになり、スタックの独自のアナログを実装する必要があります

var allArrays = [['a', 'b'], ['c'], ['d', 'e', 'f']] 

function allPossibleCases(arr) { 
    if (arr.length == 1) { 
    return arr[0]; 
    } else { 
    var result = []; 
    var allCasesOfRest = allPossibleCases(arr.slice(1)); // recur with the rest of array 
    for (var i = 0; i < allCasesOfRest.length; i++) { 
     for (var j = 0; j < arr[0].length; j++) { 
     result.push(arr[0][j] + allCasesOfRest[i]); 
     } 
    } 
    return result; 
    } 

} 

。

Answer 2

あなたは再帰、または重く入れ子にされたループを必要とせず、メモリ内の並べ替えの配列全体を生成/保存する必要もありません。

順列の数（このnumPermsを呼び出す）アレイのそれぞれの長さの積であるので、あなたは、インデックスを計算することにより指標0とnumPerms - 1間ユニーク順列を返す関数getPermutation(n)を作成することができ、それは取得する必要がありますその文字はから、nに基づいています。

これはどのように行われますか？ [0,1,2、... 9]の配列を持つ配列について順列を作成すると思うなら、それは非常に簡単です... 245番目の置換（n = 245）は直感的には "245"、つまり：

arrayHundreds[Math.floor(n/100) % 10] 
+ arrayTens[Math.floor(n/10) % 10] 
+ arrayOnes[Math.floor(n/1) % 10] 

問題の複雑さは、配列のサイズが異なることです。 n/100,n/10などを他の除数に置き換えることで、この問題を回避できます。私たちは簡単にこの目的のために除数の配列を事前に計算することができます。上記の例では、100の除数はarrayTens.length * arrayOnes.lengthに等しかった。したがって、与えられた配列の除数を残りの配列の長さの積として計算することができます。最後の配列は常に1の除数を持ちます。また、10でmodするのではなく、現在の配列の長さでmodを設定します。

例のコードは以下の通りです：

var allArrays = [first, second, third, ...]; 

// Pre-calculate divisors 
var divisors = []; 
for (var i = allArrays.length - 1; i >= 0; i--) { 
    divisors[i] = divisors[i + 1] ? divisors[i + 1] * allArrays[i + 1].length : 1; 
} 

function getPermutation(n) { 
    var result = "", curArray; 

    for (var i = 0; i < allArrays.length; i++) { 
     curArray = allArrays[i]; 
     result += curArray[Math.floor(n/divisors[i]) % curArray.length]; 
    } 

    return result; 
} 

Answer 3

提供答えは私にとってあまりにも困難になります。だから私のソリューションです：

var allArrays = new Array(['a', 'b'], ['c', 'z'], ['d', 'e', 'f']); 

function getPermutation(array, prefix) { 
    prefix = prefix || ''; 
    if (!array.length) { 
     return prefix; 
    } 

    var result = array[0].reduce(function (result, value) { 
     return result.concat(getPermutation(array.slice(1), prefix + value)); 
    }, []); 
    return result; 
} 

console.log(getPermutation(allArrays)); 

Answer 4

あなたは典型的なバックトラックを使用することができます。

function cartesianProductConcatenate(arr) { 
    var data = new Array(arr.length); 
    return (function* recursive(pos) { 
    if(pos === arr.length) yield data.join(''); 
    else for(var i=0; i<arr[pos].length; ++i) { 
     data[pos] = arr[pos][i]; 
     yield* recursive(pos+1); 
    } 
    })(0); 
} 

私は同時にすべての結果を割り当てる避けるために、発電機の機能を使用しますが、あなたがしたい場合は、

[...cartesianProductConcatenate([['a', 'b'], ['c', 'z'], ['d', 'e', 'f']])]; 
// ["acd","ace","acf","azd","aze","azf","bcd","bce","bcf","bzd","bze","bzf"] 

Answer 5

をすることができます

私は次のように単純な再帰的なgenerator functionを提案します：

0直接配列の配列を取るためにle_mの回答の

Answer 6

コピー：

function *combinations(arrOfArr) { 
    let [head, ...tail] = arrOfArr 
    let remainder = tail.length ? combinations(tail) : [[]]; 
    for (let r of remainder) for (let h of head) yield [h, ...r]; 
} 

それが誰かの時間を節約できます願っています。

Answer 7

ここではOPで指定された順序で結果を生成し、代わりに配列の文字列を返します回答の上記のカップル、から適応バージョンです：あなたはflow-を探しているなら

function *cartesianProduct(...arrays) { 
    if (!arrays.length) yield []; 
    else { 
    const [tail, ...head] = arrays.reverse(); 
    const beginning = cartesianProduct(...head.reverse()); 
    for (let b of beginning) for (let t of tail) yield b + t; 
    } 
} 

const first = ['a', 'b', 'c', 'd']; 
const second = ['e']; 
const third = ['f', 'g', 'h', 'i', 'j']; 
console.log([...cartesianProduct(first, second, third)]) 

Answer 8

は、任意のアイテムタイプの2次元配列を扱うことができる互換関数です。以下の関数を使用することができます。

const getUniqueCombinations = <T>(items : Array<Array<T>>, prepend : Array<T> = []) : Array<Array<T>> => { 
    if(!items || items.length === 0) return [prepend]; 

    let out = []; 

    for(let i = 0; i < items[0].length; i++){ 
     out = [...out, ...getUniqueCombinations(items.slice(1), [...prepend, items[0][i]])]; 
    } 

    return out; 
} 

操作の可視化：

[ 
    [Obj1, Obj2, Obj3], 
    [Obj4, Obj5], 
    [Obj6, Obj7] 
] 

アウト：で

[ 
    [Obj1, Obj4, Obj6 ], 
    [Obj1, Obj4, Obj7 ], 
    [Obj1, Obj5, Obj6 ], 
    [Obj1, Obj5, Obj7 ], 
    [Obj2, Obj4, Obj6 ], 
    [Obj2, Obj4, Obj7 ], 
    [Obj2, Obj5, Obj6 ], 
    [Obj2, Obj5, Obj7 ], 
    [Obj3, Obj4, Obj6 ], 
    [Obj3, Obj4, Obj7 ], 
    [Obj3, Obj5, Obj6 ], 
    [Obj3, Obj5, Obj7 ] 
]