Есть ли подходящая структура данных для решения этого вопроса?

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, тогда результат должен быть следующим:

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),тогда результат должен быть

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

Затем я добавляю 3-й вход 5 (итого 7 7 5), тогда результат должен быть

from group 1
7 2 5

from group 2
//nothing

from group 3
//nothing

from group 4
//nothing

Кажется, чтоМне нужен лес (несколько деревьев) для этого, верно?Если да, то есть ли хорошая реализация дерева c ++ в лесу для этой задачи или я лучше сам ее сделал?

Большое спасибо

Answer 1

«Лес деревьев» в терминах c ++ будет:

vector<set<string> >

Где строки в наборе: «2 2 6», «2 2 7» и т. Д.

Предполагая, что вы хотите использовать только префиксы, и все числа представляют собой одну цифру (или ноль, выравниваемый по той же ширине), вы можете реализовать алгоритм с помощью set :: lower_bound и set :: upper_bound на нужный префикс (в данном примере сначала «7», затем «7 2» и т. д.).

Пример:

void PrintResults(const vector<set<string> >& input, const string& prefix) {
  for (int i = 0, end(input.size()); i < end; ++i) {
    cout << "from group " << i + 1 << endl;
    const set<string>& group_set = input[i];
    set<string>::const_iterator low(group_set.lower_bound(prefix)), high(group_set.upper_bound(prefix));
    if (low == high) {
      cout << "//nothing" << endl;
    } else {
      for (; low != high; ++low) {
        cout << *low << endl;
      }
    }
  }
}

Для этого вы можете использовать вектор попыток, но нет версии библиотеки std.

Answer 2

Что-то вроде хранения данных

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

Теперь вы можете создать один из них для каждой группы, если нет гарантии, что количество элементов в каждой группе одинаково, или если вы знаете, чтокаждая группа - это определенное количество элементов, затем поместите их в один набор.

Затем используйте std::find_if с пользовательским предикатом с указанным выше data.И в этом предикате есть std::vector, то есть последовательность, которую вы ищете.

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, которые начинаются с последовательности поиска.

РЕДАКТИРОВАТЬ: чтобы сохранить в одном экземпляре, оберните вектор, например,

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;

Добавить все данные из всех групп

Изменить предикат:

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

Answer 3

Как говорили другие авторы, вам нужно дерево префиксов.Вот простой пример, чтобы вы начали, предполагая, что только символы 0-7.Обратите внимание, что я поставил очень мало безопасности, и число предполагает, что переданные ему строки следуют с пробелами (ДАЖЕ ПОСЛЕДНИЙ ОДИН), и результаты возвращаются одинаково (это проще).Для реального кода нужно больше безопасности.Кроме того, код не скомпилирован / не протестирован, поэтому, вероятно, есть ошибки.

class number { //create a prefix node type
    number& operator=(const number& b); //UNDEFINED, NO COPY
    int endgroup;  //if this node is the end of a string, this says which group
    number* next[8];  // pointers to nodes of the next letter
public:
    number() :group(-1) { //constructor
        for(int i=0; i<8; ++i)
            next[i] = nullptr;
    }
    ~number() { // destructor
        for(int i=0; i<8; ++i)
            delete next[i];
    }
    void add(char* numbers, int group) { //add a string to the tree for a group
        if(next[numbers[0] == '\0') //if the string is completely used, this is an end
            endgroup = group;
        else {
            int index = numbers[0]-'0'; //otherwise, get next letter's node
            if (next[index] == nullptr)
                next[index] = new number; //and go there
            next[index].add(numbers+2, group); //+2 for the space
        }
    }
    void find(char* numbers, 
        std::vector<std::pair<int, std::string>>& out, 
        std::string sofar="") 
    { //find all strings that match
        if(numbers[0]) { //if there's more letters 
            sofar.append(numbers[0]).append(' '); //keep track of "result" thus far
            int index = numbers[0]-'0'; //find next letter's node
            if (next[index] == nullptr)
                return; //no strings match
            next[index].find(numbers+2, out, sofar); //go to next letter's node
        } else { //if there's no more letters, return everything!
            if (endgroup > -1) //if this is an endpoint, put it in results
                out.push_back(std::pair<int, std::string>(endgroup, sofar));
            for(int i=0; i<8; ++i) { //otherwise, try all subsequent letter combinations
                if (next[i]) {
                    std::string try(sofar);  //keep track of "result" thus far
                    try.append('0'+i).append(' ');
                    next[i].find(numbers, out, try); //try this letter
                }
            }
        }
    }
} root; //this is your handle to the tree

int main() {
    //group one
    root.add("2 2 6", 1);
    root.add("2 2 7", 1);
    //...
    //group two
    root.add("2 2 2", 2);
    //...

    std::string pattern;
    char digit;
    while(true) {
        std::cin >> digit;
        if (digit<'0' || digit > '7')
            break;
        pattern.append(digit).append(' ');
        std::vector<std::pair<int, std::string>> results;
        root.find(pattern.c_str(), results);
        for(int g=1; g<4; ++g) {
            std::cout << "group " << g << "\n";
            for(int i=0; i<results.size(); ++i) {
                if( results.first == g)
                    std::cout << results.second;
            }
        } 
    }
}

Answer 4

Вот эскиз возможного решения:

class Group
{
    int id;

    std::vector<int> values;
}

Этот класс используется для хранения как всей группы (исходных данных), так и результата запроса (содержимого группы после применения какого-либо фильтра).

Дерево строится с использованием узлов и ребер; каждый узел использует вектор Group для хранения результата для этого узла.

class Node;

typedef Node *NodePtr;

class Edge
{
    NodePtr target;

    int value;
};

class Node
{
    // Results for each group. Maybe empty for certain groups.
    // Contains all elements for all groups in the root node.
    std::vector<Group> results;

    std::vector<Edge> children;
};

При поиске вы начинаете с корня. Чтобы соответствовать, например, 7 2, вы ищете дочерний элемент корня, который достигается путем обхода ребра со значением == 7. Затем вы смотрите на целевой узел этого ребра и ищите ребро со значением == 2. Когда вы достигнете последний узел пути, у вас есть результат в векторе результатов.

Обновление Конечно, у вас также есть проблема построения такого дерева. Вы можете сделать это, используя рекурсивный алгоритм.

Вы начинаете с корневого узла, содержащего все группы и все списки. Затем для каждого первого элемента списка добавляется ребро с соответствующим узлом и соответствующим набором результатов.

Вы повторяете вышеуказанный шаг для каждого дочернего узла, на этот раз просматривая вторые элементы в списках. И так до тех пор, пока вы не сможете больше расширять дерево.

Answer 5

Поскольку глубина кажется фиксированной,

std::map<int, std::map<int, std::set<int> > >

выполнит эту работу.Не уверен, что оно того стоит, учитывая количество элементов данных.

Answer 6

Массивы строк сделают свое дело.Каждая строка является строкой.Вы можете украсить строки разделителями, чтобы упростить поиск, например, "/ 7/2/2 /" вместо "7 2 2", чтобы вы могли искать "/2".

Я думаю, это вашапрофессор хочет, чтобы вы использовали более сложную структуру данных.