Let's say you have the following set {Alpha, Beta, Charlie, Delta} with a bunch of attributes:

Alpha: Red and Blue, Large, Round, Heavy
Beta: Blue, Large, Triangle, Light
Charlie: Green, Small, Triangle, Light
Delta: Red, Small, Triangle, Heavy

Choosing the subset {Alpha, Charlie} includes at least one of every attribute, in this case:

Red, Blue, Green
Large, Small
Round, Triangle
Light, Heavy. 

Removing Beta and Delta doesn't make much of a difference, since attributes for those elements are still within the subset. This is pretty intuitive given the small sample size, but what exactly is this 'process' called? I'm looking to write an algorithm, that when given a data size much larger than this, can filter out the unnecessary elements in the set while still keeping at least 1 instance of every attribute.

Two extra criteria:
1. Not every element will have every attribute. For example, element Echo may only state Triangle and Heavy.
2. An element can have two of the same attribute. In the case of Alpha, it is both Red and Blue. Choosing Alpha to be in the subset checks off BOTH red and blue.

I'm not a math major so I don't know much about these sort of algorithms, so if anyone could give me a helping hand or just let me know what this type of sorting algorithm is, that would be great!

Currently, my thinking is:
1. Create multiple arrays that list every attribute and how many times they appear.
2. Use recursive loops to find the elements that have attributes that only appear once. These obviously must be in the subset, and those attributes are checked off.
3. Determine the attributes that appear twice. The element that has that attribute, but also has the largest number of un-accounted-for attributes is added to the subset. Those attributes are checked off.
4. Rinse and repeat.

My issue with my current algorithm is that it kind of seems like a brute force method with no real logic behind it. I've read a little into feature selection and feature extraction, but I'm not quite sure of those are applicable. I'm looking for ways to improve it mathematically!

  • 2
    $\begingroup$ If that can help, you are trying to solve a set covering problem, which is a classical discrete optimization problem. $\endgroup$
    – borisd
    Jan 6 '17 at 7:42

As per borisd's comment, the correct term I was looking for is a 'set covering problem which is a classical discrete optimization problem'.

To be more specific, I used the Greedy algorithm to determine the sub-set. Not the best solution since there is still overlap, but it works for my intended use. Also see the link below for more information:



Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.