查找JavaScript数组值的所有组合

Question

如何在N个可变长度的JavaScript数组中生成所有值的组合？

假设我有N个JavaScript数组,例如

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

(在这个例子中有三个数组,但它有N个数组用于解决问题.)

我想输出它们的所有值的组合,以产生

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

---

编辑:这是我工作的版本,使用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

这不是排列,请参阅维基百科的排列定义.

但是你可以通过递归来实现这个目的:

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

我建议一个简单的递归生成器函数如下:

// Generate cartesian product of given iterables:
function* cartesian(head, ...tail) {
  let remainder = tail.length ? cartesian(...tail) : [[]];
  for (let r of remainder) for (let h of head) yield [h, ...r];
}

// Example:
const first  = ['a', 'b', 'c', 'd'];
const second = ['e'];
const third  = ['f', 'g', 'h', 'i', 'j'];

console.log(...cartesian(first, second, third));

Answer 3

您不需要递归或重度嵌套循环,甚至不需要在内存中生成/存储整个排列数组.

由于排列的数量是每个数组长度的乘积(调用this numPerms),因此您可以创建一个函数getPermutation(n),该函数返回索引之间的唯一排列,0并numPerms - 1通过计算从中检索其字符所需的索引(基于)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.

示例代码如下:

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 4

提供的答案对我来说太难了.所以我的解决方案是:

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 5

您可以使用典型的回溯:

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 6

le_m的副本答案直接采用数组的数组:

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

找到组合的最简单方法

const arr1= [ 'a', 'b', 'c', 'd' ];
const arr2= [ '1', '2', '3' ];
const arr3= [ 'x', 'y', ];

const all = [arr1, arr2, arr3];

const output = all.reduce((acc, cu) => { 
    let ret = [];
      acc.map(obj => {
        cu.map(obj_1 => {
          ret.push(obj + '-' + obj_1) 
        });
      });
      return ret;
   })

console.log(output);

Answer 8

您可以通过生成笛卡尔积来采用单行方法。

result = items.reduce(
    (a, b) => a.reduce(
        (r, v) => r.concat(b.map(w => [].concat(v, w))),
        []
    )
);

result = items.reduce(
    (a, b) => a.reduce(
        (r, v) => r.concat(b.map(w => [].concat(v, w))),
        []
    )
);

var items = [['a', 'b', 'c', 'd'], ['e'], ['f', 'g', 'h', 'i', 'j']],
    result = items.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []));
	
console.log(result.map(a => a.join(' ')));