We have array of arbitrary number of elements - 3d vectors with positive integers components - for example
let a=[ [0,1,2], [1,0,2], [1,1,1], [1,2,0 ], [2,0,1 ], [2,1,0 ] ];
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:
- solution with 3 elements:
- solution with 2 elements:
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.
Optimalization: from this wiki aricle I know that finding longest solution is NP-hard problem - but what about finding the shortest solution? Does exists algorithm which not use brute-force to find shortest solution (shortest 3-d matching)?