Algorithm: find largest subset from arrays

Question

I have multiple arrays. I need to find the largest subset of arrays, such that, all arrays in that subset have atleast an element in common with each other. By largest I mean, the subset should have most number of arrays. I am not interested in finding which particular arrays are in the subset, but rather the size of the subset. e.g. if:

a1 = [1,3,7]
a2 = [3,5,7]
a3 = [2,8,9]
a4 = [7,8,9]

then I should get largest subset size as 3, because largest subset of given arrays would be a1,a2 and a4, because:
a1 ∩ a2 != ∅ && a1 ∩ a4 != ∅ && a2 ∩ a4 != ∅

I have a function common(array1,array2) which returns true if array1 ∩ array2 != ∅ and false otherwise.
One way of solving it would be to make all possible pairs of arrays, and check them for commonality. But the issue here is, given a list of pairs that have common element(s) between them, how to construct the largest subset.
e.g. given the above example, how to construct {a1,a2,a4} from (a1,a2), (a1,a4), (a2,a4), (a3,a4).

Constructing the largest subset from the list of pairs of common sets wouldn't work, as you don't know what is common between them. — John Bupit
– John Bupit, Commented Nov 9, 2015 at 20:42
@John if a1 ∩ a2 != ∅ && a1 ∩ a4 != ∅ && a2 ∩ a4 != ∅, then we can have a subset having {a1,a2,a4} because all possible array pairs in this subset have an element in common with each other. — Saad
– Saad, Commented Nov 9, 2015 at 20:47
Consider the case a1 = {1, 2}; a2 = {2, 4}; a4 = {1, 4}. We have a1 ∩ a2 != ∅ && a1 ∩ a4 != ∅ && a2 ∩ a4 != ∅ but still a1 ∩ a2 ∩ a4 = ∅. — John Bupit
– John Bupit, Commented Nov 9, 2015 at 20:52
@John in scenarios where this intersection hold, can you suggest as how to proceed ? — Saad
– Saad, Commented Nov 9, 2015 at 23:59

John Bupit · Accepted Answer · 2015-11-09 20:49:12Z

2

Since you are not interested in finding which particular arrays are in the subset, but rather only the size of the subset, one way would be to create a map of all the possible values to the number of arrays containing that value.

For the example in the question, the map would look something like:

count[1] = 1 // contained by a1
count[2] = 1 // contained by a3
count[3] = 2 // contained by a1, a2
count[7] = 3 // contained by a1, a2, a4
count[8] = 2 // contained by a3, a4
count[9] = 2 // contained by a3, a4

The highest value in the count map (in this case, 3) is the desired result.

answered Nov 9, 2015 at 20:49

John Bupit

10.7k10 gold badges45 silver badges79 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Saad Over a year ago

Can you suggest any other alternative, that should work with object datatypes as well?

John Bupit Over a year ago

You can use this method, if you can represent an object uniquely with a string/int. Implementation of a map of such objects depends on the language you're using.

Saad Over a year ago

But the structure of object would be a complex/hierarchical one. I don't really want to represent each unique object, but want to simplify the computation by making use of intersection as explained in the question above.

John Bupit Over a year ago

How do you check whether two objects are equal or not? If you can check that, you can build a map, and an efficient one if you can even compare the objects.

Collectives™ on Stack Overflow

Algorithm: find largest subset from arrays

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related