1

Say we have multiple arrays:

var a := [1, 2, 3]
var b := [2, 3, 4, 5]
var c := [1, 3, 4, 6]
var d := [1, 2, 5]

We want to find the three arrays with the smallest cardinal number when the three arrays are unified.

As a program:

function findMostSimilar(var haystack, var arrayCount) {
    var result := ...
    // algorithm
    return result
}
var setOfArrays := [a, b, c, d]
var result := findMostSimilar(setOfArrays, 3)

The result should be:

result = [a, b, d] //(we only need [1, 2, 3, 4, 5])

Is there an efficient way to find such a subset?

Update

As in the comments suggested (thank you amon) the best result would be the unification of input arrays which have the smallest cardinal number.

Is this a use case for MapReduce?

  1. Map: merge n input arrays
  2. Combine: get the cardinal number of the set
  3. Reduce: get the combinations with the smallest cardinal number

Update 2

In the result d is included because we need to find three arrays.

As for a more practical example:

We have five recipes with different ingredients and we want to get the three recipes which combined need the smallest number of overall ingredients.

I replaced intersection with union because intersection was wrong (thank you Tyler Durden).

  • 4
    Define the “intersection rate” of three arrays. Once you have a solid definition of that, you can at least use a brute-force algorithm. A careful description of a problem is already half of the solution. – amon Jun 15 '15 at 19:37
  • It is unclear what you are asking. It is true that in your example, the union of a b and d is { 1,2,3,4,5 }. However, the union of just a and b is the same thing, so why is d even included? The intersection of a, b and d does not include the value 1 because 1 is not present in b. Your question needs serious clarification. – Tyler Durden Jun 15 '15 at 23:21
  • Might be a good idea to compute how "unique" the elements in the different arrays are. Then pick the ones that have the least unique elements, as those will have greatest overlap with other arrays. But this is just a very coarse heuristic... – tobias_k Jun 16 '15 at 13:19
  • 1
    Seems very much related to en.wikipedia.org/wiki/Maximum_coverage_problem where you want to find maximize the size of the union of the arrays you want to minimize (and which is hard). Also if you're brute forcing, you'll be taking unions of haystack.size() choose arrayCount arrays. Is that to complex (timewise)? – Hirle Jun 16 '15 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.