时间戳

首页 > 解决方案 > 从数组创建组合并将其转换为 javascript 中的多维排列？

javascript - 从数组创建组合并将其转换为 javascript 中的多维排列？

问题描述

源数组：

var arr1 = ["a", "b"];
var arr2 = ["c"];
var arr3 = ["d", "e", "f"];

我可以做排列：（不重复）

["a", "c", "d"], 
["b", "c", "d"], 
["b", "c", "e"],
["b", "c", "f"],
["a", "c", "e"],
["a", "c", "f"]

但是我怎样才能得到结果排列呢？

["a", "c"],
["a", "d"], 
["a", "e"],
["a", "f"],
["b", "c"],
["b", "d"],
["b", "e"],
["b", "f"],
["c", "d"],
["c", "e"],
["c", "f"]

我在这里只得到了我的单个数组排列片段

var arr3 = ['d', 'e', 'f'];

function permutation (list, n) {
    var results = []
    function _perm (list, n, res, start) {
        if (res.length === n) {
            return results.push(res.join(','))
        }
        if (start === list.length) { return }
        _perm(list, n, res.slice(), start + 1)
        res.push(list[start])
        _perm(list, n, res, start + 1)
    }
    _perm(list, n, [], 0)
    return results
}
console.log(permutation(arr3, 2)) // print ["e,f", "d,f", "d,e"]

由于源数组可能是无限的，我需要同时组合和排列它们。 我想知道像这样最好的实现是什么：

var arr1 = ['a', 'b'];
var arr2 = ['c'];
var arr3 = ['d', 'e', 'f'];
...
var arrN = ['x', 'y', 'z'];

permutation([arr1, arr2, arr3, arr4], 2)
permutation([arr1, arr2, arr3, arr4], 3)
permutation([arr1, arr2, arr3, arr4], 4)

我真的很感激任何帮助。

标签： javascriptarrayssubsetcombinations

解决方案

您正在寻找从您选择的数组中获取长度为 N的子集，然后创建每个子集的笛卡尔积。

// returns power set of arr filtered by length
function powerset(arr, len, pref=[]) {
    if (len == 0) return [pref];
    if (len > arr.length) return [];
    if (len == arr.length) return [pref.concat(arr)]; // premature optimisation
    const next = arr.slice(1);
    return powerset(next, len-1, [...pref, arr[0]]).concat(powerset(next, len, pref));
}
// returns cartesian product of the arrays in the argument
function cartesian(arg) {
    var r = [], 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;
}

var arrays = [
  ['a', 'b'],
  ['c'],
  ['d', 'e', 'f'],
  ['x', 'y', 'z']
];
console.log(powerset(arrays, 2).flatMap(cartesian));
console.log(powerset(arrays, 3).flatMap(cartesian));
console.log(powerset(arrays, 4).flatMap(cartesian));

推荐阅读