Is there a suitable data structure for solving this question?

Question

I have four group of data:

//group 1
2 2 6
2 2 7
2 3 5
2 3 6
2 3 7

3 2 5
3 2 6
3 2 7
3 3 4
3 3 5
3 3 6
3 3 7
...
...
7 2 2
7 2 3
7 2 5
7 2 7
7 3 2
7 5 2
7 6 2

//group 2
2 2 2
2 2 3
2 2 4
2 2 5
2 3 2
2 3 3

3 3 2
3 3 3
3 4 2
...
...

5 2 2

//group 3
2 4
2 5

3 3
3 4
3 5
3 6
...
...
7 2

//group 4
6
7
8

And what I want to do is for given input number(s), give all the possible results. A example might help to explain what I want to do: Say input is 7, then the output should be the following:

from group 1
7 2 2
7 2 3
7 2 5
7 2 7
7 3 2
7 5 2
7 6 2

from group 2
//nothing

from group 3
7 2

from group 4
7

Then I add second input 2 (so the total input is 7 2), then the result should be

from group 1
7 2 2
7 2 3
7 2 5
7 2 7

from group 2
//nothing

from group 3
7 2

from group 4
//nothing

Then I add a 3rd input 5 (so the total input is 7 2 5), then the result should be

from group 1
7 2 5

from group 2
//nothing

from group 3
//nothing

from group 4
//nothing

It appears to be I need a forest(several trees) for this, correct ? If so , is there any good c++ tree implementation of forest for this task or I better hand made one myself ?

Many Thanks

Answer 1

Something like to hold the data

std::set<std::vector<int> > data;

Now you can create one of these for each group if there is no guarantee that the number of items in each group is the same, or if you know what each group is a specific number of items, then put them all in the same set.

Then use std::find_if with a custom predicate with the above data. And in this predicate have a std::vector which is the sequence you are looking for.

struct search_sequence
{
  bool operator()(std::vector<int> const& cVal) const
  {
    if (sequence.size() <= cVal.size())
      return std::equal(sequence.begin(), sequence.end(), cVal.begin());
    return false;
  }

  std::vector<int> sequence;
};

Now applying this with std::find_if will find all sequences in data which start with the search sequence.

EDIT: To store in the single instance, wrap the vector, e.g.

struct group_entry
{
  int id;
  std::vector<int> data;

  friend bool operator<(group_entry const& lhs, group_entry const& rhs)
  {
    return lhs.id < rhs.id && lhs.data < rhs.data;
  }
};

Now your set contains

std::set<group_entry> data;

Add all the data from all the groups

Modify the predicate:

struct search_sequence
{
  bool operator()(group_entry const& cVal) const
  {
    if (sequence.size() <= cVal.data.size())
      return std::equal(sequence.begin(), sequence.end(), cVal.data.begin());
    return false;
  }

  std::vector<int> sequence;
};