I have an algorithm problem. I’ll simplify the issue, because most of what I’m dealing with has nothing to do with the algorithm I need.
Basically, I have a list of objects that each have properties. Let’s say for the sake of simplicity that this was a simple struct or another simple data type containing a string ID and an array of strings that are its properties. The properties can be things like “tool”, “weapon”, “food”, etc.
What I need to do is turn this list of objects into a tree, where the most common properties go on top, and the least common go on the bottom. It’s a bit more complex than that, actually. For example, let’s say that I have:
- Four objects with only the “weapon” property.
- Six objects with a “tool” and “weapon” property.
- Two items with a “food” and “fruit” property.
- One item with a “tool” property.
If I were to turn this into the tree that I want, it’d look like this:
weapon(as there are ten items that have the weapon property)tool(as there are six items with the tool and weapon properties)
foodfruit
tool
It’s simple to do by hand, but I can’t seem to wrap my head around putting this into program form. Any help?
2
You can implement thus recursively:
- Find the most common property in the set of objects.
- Make this property a (new) root of the tree.
- Divide the set in a subset of objects that have the property and a subset of objects that don’t have the property.
- Recurse: create a tree of the subset of objects that have the property (removing this property from all objects) and set that tree as a subtree of the newly created root.
- Repeat steps 1..5 with the other subset (the objects that didn’t have the selected property) until the set its empty.