3

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)
  • food
    • fruit
  • 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?

Improve this question
2
  • Can you write down in exact steps how to make that tree by hand, so that someone unfamiliar with your project could also do it? How do you decide that you need two tool entries (one at top level and another under weapon), but only one weapon entry? Commented Dec 28, 2014 at 10:35
  • There are objects that have both a tool and weapon property, but there are more items with the weapon property - so the weapon property is at the top. Then the tool entry comes under that, because there are six items with the weapon and tool property - so if you were to flatten it, you would get an object with both weapon and tool. Commented Dec 28, 2014 at 11:31

1 Answer 1

Reset to default
3

You can implement thus recursively:

  1. Find the most common property in the set of objects.
  2. Make this property a (new) root of the tree.
  3. Divide the set in a subset of objects that have the property and a subset of objects that don't have the property.
  4. 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.
  5. Repeat steps 1..5 with the other subset (the objects that didn't have the selected property) until the set its empty.
Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.