以最佳方式找到数组的一些子集 [英] Find some subset of array in optimal way
问题描述
在这里，我发现了如下问题，但我进行了开发并提出了有关优化的新问题(需要当然有新的不同解决方案).我们有任意数量的元素数组-3d向量-例如:
Here I found question which was formulated as follows, but I develop it and ask new questions about optimization (which need of course new different solutions). We have array of arbitrary number of elements - 3d vectors - for example:
let a=[ [0,1,2], [1,0,2], [1,1,1], [1,2,0 ], [2,0,1 ], [2,1,0 ] ];
我们想从该列表中删除那些在第i个索引上与其他元素具有重复值的元素.这个问题可以有多个解决方案:
And we want to remove elements from that list, which have duplicate value on i-th index with other elements. This problem can have more than one solution:
- 包含3个元素的解决方案:
[0,1,2],[1,2,0],[2,0,1] - 具有2个元素的解决方案:
[1,0,2],[2,1,0]
- solution with 3 elements:
[0,1,2],[1,2,0],[2,0,1] - solution with 2 elements:
[1,0,2],[2,1,0]
如您所见，解决方案具有以下属性:每个解决方案元素在第i个索引上具有唯一值(第i个位置上的数字永远不会重复)，如果我们将数组a中的任何其他元素添加到该解决方案我们失去了这个财产.我已经创建了算法来找到一种解决方案
As you can see, the solution has this property that each solution element have unique value on i-th index (numbers on i-th position never duplicate) and if we add any other element from array a to that solution we loose this property. I already create algorithm to find one solution
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));
但是不知道如何创建非蛮力算法，该算法会发现:
But have no Idea how to create non-brute-force algorithm which will find:
- 最短的解决方案
- 最长的解决方案
如果您不使用js进行编码，则详细描述的算法也是可以接受的.
If you not code in js, the detail described algorithm is also acceptable.
正如 @btilly 回答所说，找到最长的解决方案是NP难题(类似于3d匹配).但是，关于算法找到最短解的问题仍然存在.下面的小图显示了问题和3d匹配之间的类比:
As @btilly answer says, the find longest solution is NP-hard problem (similar to 3d-matching). However the question about algorithm finding shortest solution is still open. Below little visualistation showing analogy between question and 3d-matching:
// 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>
我问了一个问题并得到了答案在这里，据此，找到最短解决方案的问题是NP-困难(而且甚至比找到最长的解决方案还难，因为在2D情况下，longes解决方案不是NP-hard，而是2D最小的解决方案是NP-hard).
I ask question and get answer here and according to it the problem of find the shortest solution is NP-hard (and it is even harder than finding longest solution because for 2D case the longes solution is NOT NP-hard but the smallest solution in 2D is NP-hard).
推荐答案
此问题的解决方案立即为 3维匹配问题，这是NP难题.
A solution to this problem immediately gives a solution to the 3 dimensional matching problem which is NP hard.
因此，不太可能有一个有效的算法.如果有的话，那就发现它超出了我的薪水等级. :-)
So it is unlikely that there is an efficient algorithm. And if there is, then finding it is beyond my pay grade. :-)
这篇关于以最佳方式找到数组的一些子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
