无重复的笛卡尔积

Question

我正在使用给定 [1], [1,2,3], [1,2,3] returns 9 种组合的笛卡尔积函数：

[ [ 1, 1, 1 ],
  [ 1, 2, 1 ],
  [ 1, 3, 1 ],
  [ 1, 1, 2 ],
  [ 1, 2, 2 ],
  [ 1, 3, 2 ],
  [ 1, 1, 3 ],
  [ 1, 2, 3 ],
  [ 1, 3, 3 ] ]

但我需要删除那些与顺序无关的相同项目，所以 [ 1, 3, 1 ] 和 [ 1, 1, 3 ] 对我来说是一样的。结果应包含 6 项：

[ [ 1, 1, 1 ],
  [ 1, 2, 1 ],
  [ 1, 3, 1 ],
  [ 1, 2, 2 ],
  [ 1, 3, 2 ],
  [ 1, 3, 3 ] ]

我可以编写一个函数，将所有可能的对与 _.xor 进行比较，但对于更大的数字，它可能效率很低。 Javascript 有什么好办法吗？比较所有可能对的有效方法或没有重复的笛卡尔积算法？

Answer 1

JavaScript 有 set 数据结构。

因此将您的结果存储在一个集合中，其中每个元素都是原始集合中的数字对以及该数字出现的次数的集合。

所以你的结果应该是这样的：

[ 
  {1:3},
  {1:2, 2: 1},
  { 1:2, 3:1},
  { 1:1, 2:2},
  { 1:1, 2:1, 3:1},
  { 1:1, 3:2 }  ]

这样，您将无法再次将对象添加到集合中。

Answer 2

对笛卡尔积的每个数组进行排序

[ 1, 2, 1 ] -> [1 , 1 , 2]
[ 1, 1, 2 ] -> [1 , 1 , 2]

然后将这些排序的数组收集到一个集合中，这将删除重复项。

当然，您可以在构造笛卡尔积时执行此操作，而不是事后执行。

Answer 3

JavaScript 有 Set and Map，但是它们通过引用而不是值比较对象和数组，因此您不能直接利用它。这个想法是使用一个关键函数，它在将项目放入集合之前对项目进行排序和 json 编码。

纯 ES5：

function product(sets) {
  if (sets.length > 0) {
    var head = sets[0];
    var tail = product(sets.slice(1));
    var result = [];
    head.forEach(function(x) {
      tail.forEach(function(xs) {
        var item = xs.slice(0);
        item.unshift(x);
        result.push(item);
      });
    });
    return result;
  } else {
    return [[]];
  }
}

function myKeyFn(item) {
  return JSON.stringify(item.slice(0).sort());
}

function uniqBy(items, keyFn) {
  var hasOwn = Object.prototype.hasOwnProperty, keyset = {};
  return items.filter(function(item) {
    var key = keyFn(item);
    if (hasOwn.call(keyset, key)) {
      return false;
    } else {
      keyset[key] = 1;
      return true;
    }
  });
}

function uniqProduct(sets) {
  return uniqBy(product(sets), myKeyFn);
}

function log(x) {
  console.log(x);
  var pre = document.createElement('pre');
  pre.appendChild(document.createTextNode(x));
  document.body.appendChild(pre);
}

log(uniqProduct([[1],[1,2,3],[1,2,3]]).map(JSON.stringify).join("\n"));

<pre></pre>

lodash + modern JavaScript:

// Note: This doesn't compile on current babel.io/repl due to a bug

function product(sets) {
  if (sets.length > 0) {
    const [x, ...xs] = sets;
    const products = product(xs);
    return _.flatMap(x, head => products.map(tail => [head, ...tail]));
  } else {
    return [[]];
  }
}

function uniqProduct(sets) {
  return _.uniqBy(product(sets), x => JSON.stringify(x.slice(0).sort()));
}

console.log(uniqProduct([[1],[1,2,3],[1,2,3]]).map(JSON.stringify).join("\n"));

无重复的笛卡尔积

Cartesian product without duplicates

javascript

arrays

algorithm

combinations

cartesian-product

纯 ES5：

lodash + modern JavaScript: