javascript - 以最佳方式找到数组的某个子集

Question

Here我发现问题的表述如下，但我开发了它并提出了有关优化的新问题(当然需要新的不同解决方案)。我们有任意数量元素的数组 - 3d 向量 - 例如:

let a=[ [0,1,2], [1,0,2], [1,1,1], [1,2,0 ], [2,0,1 ], [2,1,0 ] ];

我们想从该列表中删除元素，这些元素在第 i 个索引上与其他元素具有重复值。这个问题可以有不止一种解决方案:

• 包含 3 个元素的解决方案:[0,1,2],[1,2,0],[2,0,1]
• 具有 2 个元素的解决方案:[1,0,2],[2,1,0]

如您所见，解决方案具有此属性，即每个解决方案元素在第 i 个索引上都有唯一值(第 i 个位置上的数字永远不会重复)并且如果我们从数组 a 添加任何其他元素对于那个解决方案，我们失去了这个属性。我已经创建了算法来找到一个解决方案

let a=[[ 0, 1, 2 ],  [ 1, 0, 2 ], [ 1, 1, 1 ], [ 1, 2, 0 ], [ 2, 0, 1 ], [ 2, 1, 0 ] ,];

let t=[{},{},{}];

let d= a.filter(e => 
  !e.reduce((g,h,i)=> g||(e[i] in t[i]),false) && e.map((x,i) => t[i][x]=x)
);

console.log(JSON.stringify(d));

但不知道如何创建会发现的非暴力算法:

• 最短的解决方案
• 最长的解决方案

如果不是js代码，详细描述算法也可以。

更新

作为@btilly回答说，找到最长的解决方案是 NP-hard 问题(类似于 3d 匹配)。然而，关于算法寻找最短解的问题仍然悬而未决。下面的小可视化显示了问题和 3d 匹配之间的类比:

// matching = [[1,2,3], [2,3,4]]; // numbers shod be integers
function draw(divSelector, matching) {

  let c = '';
  let r = 10,
    marginLeft = 40,
    marginTop = 40;
  let spaceX = 100,
    spaceY = 100,
    mSizeMin = 10,
    mSizeMax = 20;
  let max = Math.max(...matching.flat());
  let min = Math.min(...matching.flat());

  ['X', 'Y', 'Z'].forEach((e, i) => {
    c += `<text class="text"><tspan x="${marginLeft+i*spaceX}" y="${marginTop-20}">${e}</tspan></text>`
  });

  if (matching.length > 0) {
    [...Array(25)].map((_, i) => i + min).forEach((e, i) => {
      c += `<text class="text"><tspan x="${marginLeft-20}" y="${marginTop+i*spaceY}">${min+i}</tspan></text>`
    });
  }


  // matching  
  matching.forEach((e, j) => {
    let x0 = marginLeft + 0 * spaceX,
      y0 = marginTop + (e[0] - min) * spaceY;
    let x1 = marginLeft + 1 * spaceX,
      y1 = marginTop + (e[1] - min) * spaceY;
    let x2 = marginLeft + 2 * spaceX,
      y2 = marginTop + (e[2] - min) * spaceY;
    let st = mSizeMin + (mSizeMax - mSizeMin) * (1 - j / (matching.length - 1)); // matching size
    let sc = 127 + (128 * j / (matching.length)) | 0;
    sc = `rgb(${sc},${sc},${sc})` // color
    let mF = `<path class="matF" d="M ${x0},${y0} L ${x1},${y1} L ${x2},${y2}" style="stroke-width:${st}; stroke:${sc}"/>`
    let mB = `<path class="matB" d="M ${x0},${y0} L ${x1},${y1} L ${x2},${y2}" style="stroke-width:${st+2}"/>`

    c += mB + mF;
  });

  // points
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j <= max - min; j++) {
      let x = marginLeft + i * spaceX,
        y = marginTop + j * spaceY;
      let p = `<path class="point point_${i}" d="M ${x+r/2},${y} A 1,1 0 1 1 ${x-r/2},${y} A 1,1 0 1 1 ${x+r/2},${y} z"/>`;
      c += p;
    }
  }

  let s = `<svg height=${2*marginTop+spaceY*(max-min)} width=${2*marginLeft+spaceX*2} xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">${c}</svg>`;

  document.querySelector(divSelector).innerHTML = s;
}

function showList(list) {
  let s = ''
  list.forEach((x, i) => {
    s += `<div class="listItem" onclick="removeElement(${i})">[ ${x} ] del</div>`
  })
  document.getElementById('list').innerHTML = s;
}

let list = [
  [0, 1, 2],
  [1, 0, 2],
  [1, 1, 1],
  [1, 2, 0],
  [2, 0, 1],
  [2, 1, 0]
];

function update() {
  let v = document.querySelector('#vec').value
  if (!/^ *\d*, *\d*, *\d*$/.test(v)) {
    alert('Write 3 separated by comma e.g.: 1,2,3');
    return;
  }
  document.querySelector('#vec').value = '';
  nv = v.split(',').map(x => +x);
  list.push(nv);
  list = list.filter((t = {}, e => !(t[e] = e in t))) //unique
  draw('#container', list);
  showList(list);
}

function removeElement(i) {
  list.splice(i, 1)
  refresh(list);
}

function clearAll() {
  list = [];
  refresh(list);
}

function refresh(list) {
  draw('#container', list);
  showList(list);
}

refresh(list);

.point {
  opacity: 1;
  fill: #d40000;
  fill-opacity: 1;
  fill-rule: evenodd;
  stroke: #000000;
  stroke-width: 2;
  stroke-linecap: butt;
  stroke-linejoin: miter;
  marker: none;
  marker-start: none;
  marker-mid: none;
  marker-end: none;
  stroke-miterlimit: 4;
  stroke-dasharray: none;
  stroke-dashoffset: 0;
  stroke-opacity: 1;
  visibility: visible;
  display: inline;
  overflow: visible;
  enable-background: accumulate
}

.point_0 {
  fill: #d40000
}

.point_1 {
  fill: #00d400
}

.point_2 {
  fill: #0000d4
}

.matF {
  opacity: 1;
  fill: none;
  fill-opacity: 1;
  fill-rule: evenodd;
  stroke: #e6e6e6;
  stroke-width: 22;
  stroke-linecap: round;
  stroke-linejoin: round;
  marker: none;
  marker-start: none;
  marker-mid: none;
  marker-end: none;
  stroke-miterlimit: 4;
  stroke-dasharray: none;
  stroke-dashoffset: 0;
  stroke-opacity: 1;
  visibility: visible;
  display: inline;
  overflow: visible;
  enable-background: accumulate
}

.matB {
  opacity: 1;
  fill: none;
  fill-opacity: 1;
  fill-rule: evenodd;
  stroke: #000000;
  stroke-width: 24;
  stroke-linecap: round;
  stroke-linejoin: round;
  marker: none;
  marker-start: none;
  marker-mid: none;
  marker-end: none;
  stroke-miterlimit: 4;
  stroke-dasharray: none;
  stroke-dashoffset: 0;
  stroke-opacity: 1;
  visibility: visible;
  display: inline;
  overflow: visible;
  enable-background: accumulate
}

.content {
  display: flex;
}

.listItem {
  cursor: pointer
}

.text {
  font-size: 16px;
  font-style: italic;
  font-variant: normal;
  font-weight: normal;
  font-stretch: normal;
  text-align: center;
  text-anchor: middle;
  fill: #000000;
  fill-opacity: 1;
  stroke: none;
  stroke-width: 1px;
  stroke-linecap: butt;
  stroke-linejoin: miter;
  stroke-opacity: 1;
  font-family: Sans;
  -inkscape-font-specification: Sans Italic
}

Type 3d vector with (positive integer numbers e.g. 1,2,3)<br>
<input id="vec" value="1,2,3">
<button onclick="update()">add</button>
<button onclick="clearAll()">clear all</button>

<div class="content">
  <div id='container'>

  </div>
  <div id='list'>
  </div>
</div>

更新2

我提出问题并得到答案 here根据它，找到最短解决方案的问题是 NP-hard(它比找到最长解决方案更难，因为对于 2D 情况，longes 解决方案不是 NP-hard，但 2D 中的最小解决方案是 NP-hard)。

Answer 1

这个问题的解决方案立即给出了3 dimensional matching problem的解决方案这是 NP 难的。

所以不太可能有一个高效的算法。如果有，那么发现它超出了我的薪酬等级。 :-)