Проверка возможности связывания списка строк

Question

Вопрос

Реализация функции bool chainable(vector<string> v), которая принимает набор строк в качестве параметров и возвращает true, если они могут быть цепочкой . Две строки могут быть соединены в цепочку, если первая заканчивается тем же символом, с которого начинается вторая, например ::10000

ship->petal->lion->nick  = true;
ship->petal   axe->elf   = false;

Мое решение:

Моя логика заключается в том, что если он будет цепным, будет только один начало и конец, которые не совпадают. Поэтому я создаю список начала и список концов. вот так.

starts:s,p,l,n
ends:  p,l,n,k

если я удаляю общие элементы, списки должны содержать не более одного элемента. а именно с и к. Если это так, список цепочки. Если список циклический, окончательные списки пусты.

Но я думаю, что мне здесь не хватает некоторых случаев,

EDIT: Хорошо, ясно, у меня были ошибки в моем решении. Можем ли мы сделать лучший алгоритм для этого?

Answer 1

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

Некоторые необходимые условия существования эйлеровых путей в таких графах:

1. График должен быть подключен.
2. Все вершины с не более чем двумя исключениями имеют одинаковое количество входящих и исходящих ребер. Если существуют исключительные вершины, их ровно две, одна из которых имеет на одно выходное ребро больше, чем входящее, а на другое - на одно входящее ребро больше, чем на исходящее.

Необходимость легко увидеть: если у графа есть эйлеровы пути, любой такой путь встречается со всеми вершинами, кроме изолированных вершин (ни исходящих, ни входящих ребер). По построению, в рассматриваемом графе нет изолированных вершин. В эйлеровом пути каждый раз, когда посещается вершина, кроме начала и конца, используется одно входящее ребро и одно исходящее ребро, поэтому каждая вершина с возможным исключением начальной и конечной вершин имеет одинаковое количество входящих и исходящих ребер. Начальная вершина имеет на один исходящий ребро больше, чем входящий, а конечная вершина на один входящий ребро больше, чем исходящий, если путь Эйлера не является циклом, и в этом случае все вершины имеют одинаковое количество входящих и исходящих ребер.

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

Это позволяет проводить очень эффективную проверку:

• записать все ребра и вершины, полученные из слов
• использовать объединяющую структуру / алгоритм поиска для подсчета связанных компонентов графа
• запись indegree - outdegree для всех вершин

Если number of components > 1 или существует (по крайней мере) одна вершина с |indegree - outdegree| > 1 или имеется более двух вершин с indegree != outdegree, слова не являются цепочечными, в противном случае они являются.

Answer 2

Разве это не похоже на печально известную проблему коммивояжера ?

Если у вас есть n строк, из них можно построить график, где каждому узлу соответствует одинстрока.Вы строите ребра следующим образом:

• Если строка (соответственно узел) a и b являются цепочечными, вы вводите ребро a -> b с весом 1.
• Для всех непересекающихся строк (соответственно узлов) a и b вы вводите ребро a -> b с весом n.

Затем,все ваши строки являются цепочечными (без повторов), если и только если вы можете найти оптимальный график TSP на графике, вес которого меньше 2n.

Примечание: Ваша проблема на самом делепроще, чем TSP, поскольку вы всегда можете преобразовать цепочку строк в TSP, но не обязательно наоборот.

Answer 3

Вот случай, когда ваш алгоритм не работает:

ship
pass
lion
nail

Ваш стартовый и конечный списки оба s, p, l, n, но вы не можете сделать одну цепочку (вы получаете две цепочки - ship->pass и lion->nail).

Рекурсивный поиск, вероятно, будет наилучшим - выберите начальное слово (1) и для каждого слова, которое может следовать за ним (2), попытайтесь найти меньшеепроблема создания цепочки, начинающейся с (2), которая содержит все слова, кроме (1).

Answer 4

Как указал phimuemue, это проблема с графом.У вас есть набор строк (вершин) с (направленными) ребрами.Ясно, что график должен быть связан , чтобы иметь возможность цепочки - это легко проверить.К сожалению, правила за этим немного неясны:

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

// this can form a valid Eulerian path
yard
dog
god
glitter

yard -> dog -> god -> dog -> glitter

Если строки нельзя использовать более одного раза, проблема состоит в том, чтобы найти гамильтонов путь .Поскольку задача о гамильтоновом пути NP-полна, точное эффективное решение не известно.Конечно, для малых n эффективность на самом деле не важна, и решение с использованием грубой силы будет работать нормально.

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

digraph G {
    alpha -> beta;
    beta -> gamma;
    gamma -> beta;
    gamma -> delta;
}

Однако этот граф не может быть построен из строк с использованием правил этой головоломки:Поскольку alpha и gamma оба подключаются к beta , они должны заканчиваться одним и тем же символом (допустим, они заканчиваются на 'x'), но gamma также подключается к delta , поэтому delta также должно начинаться с 'x'.Но delta не может начинаться с 'x', потому что, если бы это было так, тогда было бы ребро alpha -> delta, которого нет в исходном графике.

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

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

(*) У него также есть гамильтонов путь: alpha -> beta -> gamma -> delta, но это не имеет значения длячто следует.

Answer 5

если вы замените petal и lion на pawn и label, у вас останется:
starts:s,p,l,n
ends: p,l,n,k

Ваш алгоритм решает, что он цепной, но это не так.
Проблема в том, что вы отключаете первую и последнюю буквы каждого слова.

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

Answer 6

Вот простая программа, которая делает это итеративно:

#include <string>
#include <vector>
#include <iostream>

using std::vector;
using std::string;

bool isChained(vector<string> const& strngs)
{
    if (strngs.size() < 2) return false;      //- make sure we have at least two strings
    if (strngs.front().empty()) return false; //- make sure 1st string is not empty

    for (vector<string>::size_type i = 1; i < strngs.size(); ++i)
    {
        string const& head = strngs.at(i-1);
        string const& tail = strngs.at(i);
        if (tail.empty())  return false;
        if (head[head.size()-1] != tail[0])  return false;
    }

    return true;
}

int main()
{
    vector<string>  chained;
    chained.push_back("ship");
    chained.push_back("petal");
    chained.push_back("lion");
    chained.push_back("nick");

    vector<string>  notChained;
    notChained.push_back("ship");
    notChained.push_back("petal");
    notChained.push_back("axe");
    notChained.push_back("elf");

    std::cout << (isChained(chained) ? "true" : "false") << "\n";     //- prints 'true'
    std::cout << (isChained(notChained) ? "true" : "false") << "\n";  //- prints 'false'

    return 0;
}

Answer 7

Это может быть решено путем сведения к задаче Эйлера, рассматривая орграф G с N (G) = и E (G) = a->e для слов aWe.

Answer 8

отдельно проверяется на "является цепным" и является "цилиндрическим"

, если оно должно быть циклическим, оно должно быть сначала цепным.Вы можете сделать что-то вроде этого:

if (IsChainable)
{
  if (IsCyclic() { ... }
}

Примечание. Это тот случай, если вы проверяете только первый и последний элемент цепочки на «циклический».