Вопрос из интервью, Извлечение алфавитного порядка из словаря

Ответ 1

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

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

Построение графика

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

[email protected]
x1$#2z

Тогда вы найдете самый длинный общий префикс, x1 в этом случае, и после этого префикса проверьте сразу следующие символы. В этом случае имеем 5 и $. Поскольку слова появляются в этом порядке в словаре, мы можем определить, что 5 должно лексикографически меньше $.

Аналогично, учитывая следующие слова (появляющиеся один за другим в словаре)

jhdsgf
19846
19846adlk

Мы можем сказать, что 'j' < '1' из первой пары (где самый длинный общий префикс - пустая строка). Вторая пара не говорит нам ничего полезного (так как один является префиксом другого, поэтому сравнивать нечего).

Предположим позже, что мы увидим следующее:

oi1019823
oij(*#@&$

Тогда мы нашли противоречие, потому что эта пара говорит, что '1' < 'j'.

Топологическая сортировка

Существует два традиционных способа сделать топологическую сортировку. Алгоритмически проще - это подход поиск глубин в начале, где есть ребро от x до y, если y < x.

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

L ← Empty list that will contain the sorted nodes
S ← Set of all nodes with no incoming edges

function visit(node n)
    if n has not been visited yet then
        mark n as visited
        for each node m with an edge from n to m do
            visit(m)
        add n to L

for each node n in S do
    visit(n)

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

Проверка уникальности

Ниже приведена цитата из Википедии:

Если топологическая сортировка обладает тем свойством, что все пары последовательных вершин в отсортированном порядке связаны ребрами, то эти ребра образуют направленный гамильтонов путь в DAG. Если существует гамильтонов путь, то топологический порядок сортировки является единственным; ни один другой порядок не уважает края пути. И наоборот, если топологическая сортировка не образует гамильтонова траекторию, DAG будет иметь два или более допустимых топологических порядка, так как в этом случае всегда можно сформировать второе допустимое упорядочение, заменяя две последовательные вершины, не связанные ребро друг другу. Поэтому в полиномиальное время можно проверить, существует ли уникальное упорядочение и существует ли гамильтонов путь.

Таким образом, чтобы проверить, является ли порядок уникальным или нет, вы просто проверяете, связаны ли все две последовательные вершины в L (из приведенного выше алгоритма) прямыми ребрами. Если они есть, то порядок уникален.

Анализ сложности

После построения графика топологическая сортировка O(|V|+|E|). Проверка уникальности O(|V| edgeTest), где edgeTest - сложность проверки того, связаны ли две вершины ребрами. С матрицей смежности это O(1).

Для построения графика требуется только однолинейное сканирование словаря. Если есть слова W, то это O(W cmp), где cmp - сложность сравнения двух слов. Вы всегда сравниваете два последующих слова, поэтому при необходимости вы можете делать всевозможные оптимизации, но в противном случае наивное сравнение O(L), где L - длина слов.

Вы также можете закорачивать словарь, как только вы определили, что у вас достаточно информации об алфавите и т.д., но даже наивный шаг в построении займет O(WL), который является размером словаря.

Ответ 2

Вы хотите найти общий порядок символов.

1) Очевидно, вы не всегда можете определить общий порядок.

2) Вы можете использовать направленный ациклический граф для представления частичного порядка между символами. Каждая буква представляется только один раз на графике. Вы заполняете его, просматривая все пары букв в одной позиции в каждой паре последовательных слов. Любые циклы, которые вы создаете в графе, указывают на ошибку в словаре. Вы спрямляете множество отношений, таких как a- > d, a- > b, b- > d в a- > b- > d. Если то, что вы получите в конце, это граф с одним источником (буква без предшественников) и один приемник (буква без преемников), у вас есть полный порядок, например, алфавит.

Ответ 3

Я решил это, используя другой предложенный алгоритм в Википедии. Вот psuedocode из Википедии:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    output error message (graph has at least one cycle)
else 
    output message (proposed topologically sorted order: L)

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

Ответ 4

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

Вы хотите найти правильный порядок символов,

C1, C2, C3, C4,..., Cn

У вас есть количество слов в словаре. Было бы превосходно иметь набор правил, таких как (Ci, Cj), что означает, что Ci <= Cj, где i, j - положительные натуральные числа, а я < m, j < м. У нас должен быть набор ошибок

Поскольку V - огромное число и оно больше m * m, хороший подход, на мой взгляд, будет следующим:

foreach i = 1, m do
    foreach j = i + 1, m do
        findFirstDifferenceInTheWords
        /*charI is the first difference in Wi from Wj and charJ is the first difference in 
          Wj*/
        if (Wi <> Wj)
            if (Wi contains Wj or Wj contains Wi) == false
            charSet.add(charI, charJ)
        else if k exists and the following is true ((i < k < j) and (Wi <> Wk))
            error.addIfDoesntExist("paradox", Wi)
        else
            error.addIfDoesntExist("redundant", Wi)
        end_if
    end_foreach
end_foreach

Мы нашли l количество правил

foreach я = 1, я делаю   foreach j = я + 1, l do       если charSet.exists(charI, charJ) и charSet.exists(charJ, charI)           error.add( "парадоксальное отношение", charI, charJ)

После этого вы можете построить порядок слов, рассматривая charI = charJ, и оба (charI, charJ) и (charJ, charI) существуют в наборе, и где charI <= charJ является единственным правилом, а не наоборот, мы можем считать, что charI < charJ.

Заключение: использование отношения "< =" лучше, чем использование "<" потому что "< =" - полное и хорошее упорядоченное отношение в теории чисел, "<" это просто хороший заказ. ПРИМЕЧАНИЕ. Выход должен отображаться правильно, если charI < charJ или charI = charJ. Например, вы можете использовать это обозначение: символов (C1C2C3, C4, C5C6,...) Где C1 = C2 = C3 < C4- C5 = C6...

Надеюсь, это поможет.

Конечно, если Wj содержит Wi, мы не можем извлечь из него правило