查找 JavaScript 数组值的所有组合（笛卡尔积）

IT技术 javascript algorithm
2021-01-29 17:26:32

如何生成 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 results = allPossibleCases(allArrays);
 //outputs ["acd", "bcd", "azd", "bzd", "ace", "bce", "aze", "bze", "acf", "bcf", "azf", "bzf"]
6个回答

这不是排列，请参阅维基百科中的排列定义。

但是您可以通过递归实现这一点：

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

}

console.log(allPossibleCases(allArrays))

您也可以使用循环来实现，但这会有点棘手，并且需要实现您自己的堆栈模拟。

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

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

美丽的。如何修改以满足这个需要单、双等字符串排列的版本
2021-03-17 17:26:32
@Andrew 为什么.apply而不是将论据泼到笛卡尔？const product = [...cartesian(...unknownNumberOfInputs)];
2021-03-25 17:26:32
这确实很美。对于那些想要使用未知数量的输入并将结果存储在数组中的人，您可以这样做： const product = [...cartesian.apply(this, [first, second,third,fourth, etc]) ];
2021-03-29 17:26:32

您不需要递归或大量嵌套的循环，甚至不需要在内存中生成/存储整个排列数组。

由于排列数是每个数组长度的乘积（称为 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;
}
@Box9：此函数适用于 1 个数组吗？不是 (n*n) - (n-1) 吗？
2021-03-21 17:26:32
@Gary，感谢您选择它。除数的顺序很重要，因为第一个取决于第二个，第二个取决于第三个，等等......所以通过向后循环我可以更容易地建立它。
2021-03-23 17:26:32
@epitaph，它应该仍然适用于 1 个数组。divisors将只有一个元素: [1]，因此它总是除以 1，然后除以数组长度——实际上，什么都不做。
2021-04-01 17:26:32
非常好。不过这里有一个错字，results应该显示result——我注意到你在计算除数时向后循环，我假设除数在数组中的位置很重要？
2021-04-05 17:26:32
如果它适用于 1 个数组并且结果 (n*n)-(n-1) 我可以用它来制作成本矩阵吗？例如旅行商问题？
2021-04-09 17:26:32

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

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

你好。如何修改它以返回数组数组而不是字符串数组？因此，而不是 ["acd","ace","acf" ...] 返回 [["a","c",d"], ["a","c","e"] .. ..]
2021-04-07 17:26:32

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

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(' ')));
.as-console-wrapper { max-height: 100% !important; top: 0; }

如何使用来回答这个问题
2021-03-16 17:26:32
其它你可能感兴趣的问题
上一篇有没有比 setTimeout 更准确的方法来创建 Javascript 计时器？ 下一篇jQuery 中的“this”是什么意思？