无重复的笛卡尔积

Question

我正在使用一个笛卡尔积函数，给定[1]，[1,2,3]，[1,2,3]返回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中是否有一种好的方法来解决这个问题？有没有一种有效的方法来比较所有可能的配对或者去重后的笛卡尔积算法？

- ilyo

---

它被称为多重集合。 - Isaac Kleinman

为什么[[2, 2, 2], [2, 2, 3], [2, 3, 3], [3, 3, 3]]不应该被包含？ - rici

@rici 这些结果即使在正常的笛卡尔积中也不是有效的。根据输入，所有集合都将以“1”开始。 - musicin3d

啊，好的。你需要一个可以适用于任何集合的算法吗？例如：[1]，[1, 2, 4]，[2, 3, 4]？ - rici

有一种方法可以避免在第一次生成时产生重复，但这很复杂。 - David Eisenstat

只需避免在示例中使用降序，例如1,1,3可以，1,3,1不行。1,2,3可以，1,3,2不行。 - user unknown

Answer 1

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

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

然后将这些已排序的数组收集到一个集合中，这样就可以消除重复项。

当然，您可以在构建笛卡尔积时进行此操作，而不是之后再处理。

- aka.nice

Answer 2

JavaScript有Set和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 + 现代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"));

- Tamas Hegedus

Answer 3

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

这样一来，您就无法将对象第二次添加到集合中。

- Isaac Kleinman