3 replies to this topic

[ThemePark]

I have a list of a lot of sets. Each set contains some numbers between 1 and N, both inclusive. No number occurs more than once within a set. I then need to find the minimum amount of sets that together will contains all the numbers from 1 to N, and find out which sets that is.

It seems like a problem that there should be an algorithm for, but I'm not really sure what to look for, so I'm hoping someone here knows how I should go about with doing this.

[WingedPanther]

What language are you doing this in? C++'s std::set could help with this. One thing you may want to look for is "sparse" numbers, numbers that appear in only a few sets, as those will be keys to simplifying the problem. If one set is a subset of another, you can ignore it, too.

[ThemePark]

I'm doing this in Java. And yes, sparse numbers will help a lot, but I'm not sure how many times each number will occur. Thus I also don't know if there will be sets that are subsets of other sets, so I'll need a algorithm that doesn't depend on that. Besides, I have about a million sets, each of which contains a somewhat large amount of objects (I just used numbers as an easily understandable example), so efficiency is rather important here.

[WingedPanther]

Once you've loaded all the data, I would START by checking for subsets/sparse values. That would be the first step of my algorithm.