Декартово произведение без дубликатов

Я использую декартову функцию произведения, которая с учетом [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 сделать это? Эффективный способ сравнить все возможные пары или алгоритм декартова произведения без дубликатов?
3 3
javascript arrays algorithm combinations cartesian-product

3 ответа:

Сортировать каждый массив декартова произведения 

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

Затем соберите эти отсортированные массивы в набор, который удалит дубликаты.

Конечно, вы можете сделать это во время построения декартова произведения, а не после него.
0

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>

Лодаш + современный 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"));
0

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

Таким образом, вы не сможете добавить объект во второй раз в набор.

-1