# Reducing a set into a subset that still contains every attribute found in the original set?

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!

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