What is the better approach to find if a given set is a perfect subset of a set - If given subset is not sorted?

Question

Hi guys,

What is the best approach to find if a given set(unsorted) is a perfect subset of a main set. I got to do some validation in my program where I got to compare the clients request set with the registered internal capability set.

I thought of doing by having internal capability set sorted(will not change once registered) and do Binary search for each element in the client's request set. Is it the best I could get? I suspected that there might be better approach.

Any idea?

Regards,

Microkernel

Answer 1

Assuming that your language of choice doesn't implement a set class with "contains in a set" method already like Java does with HashSet...

A good approach is to use hashmaps (aka hashes aka associative arrays)

If your superset is not too big, generate a hashmap mapping each object in the larger set to a true value.

Then, loop over each element in a subset. Try to find the element in the generated hashmap. if you fail, your small set is NOT a peoper subset. If you finish the loop without failing, it is.

Answer 2

it depends on how many elements are in your sets. for bigger sets, usually use a Hashset for the mainset turns out best performance.

Answer 3

Since you know the internal capability set you can use a perfect hash function to test the elements of the client request set.