有没有合适的数据结构来解决这个问题？ [英] Is there a suitable data structure for solving this question?

问题描述

我有四组资料：

//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

我想做的是给定的输入数字，给出所有可能的结果。
例子可能有助于解释我想要做什么：
说输入是7，那么输出应该是以下：

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

然后我添加第二个输入2是7 2），那么结果应该是组1中的

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

第三个输入5（所以总输入是7 2 5），那么结果应该是

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

似乎是我需要一个森林这个，正确吗？
如果是这样，是否有任何好的c ++树实现这个任务的森林，或者我更好的自己做一个？

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 ?

很感谢

推荐答案

类似于保存数据

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.

然后使用 std :: find_if 使用具有上述数据的自定义谓词。在这个谓词中有一个 std :: vector ，这是你正在寻找的序列。

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;
};

现在使用 std :: find_if 将在搜索序列开头的 data 中找到所有序列。

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

编辑：要存储在单个实例中，包装向量，例如

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;
  }
};

现在您的集合包含

std::set<group_entry> data;

添加所有组中的所有数据

Add all the data from all the groups

修改谓词：

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;
};

这篇关于有没有合适的数据结构来解决这个问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！