Учитывая словарь, найти все возможные заказы букв

Question

Мне недавно задали следующий вопрос:

У вас есть страница словаря, написанная на иностранном языке. Предположим, что язык похож на английский и читается / пишется слева направо право. Также слова расположены в лексикографическом порядке. За Пример страницы может быть: ADG, ADH, BCD, BCF, FM, FN
Вы должны указать все возможные лексикографические обозначения персонажа. установить подарок на странице.

Мой подход заключается в следующем: A имеет более высокий приоритет, чем B, а G имеет более высокий приоритет, чем H. Поэтому у нас есть информация о порядке заказа некоторых персонажей:

A->B, B->F, G->H, D->F, M->N

Возможные заказы могут быть ABDFGNHMC, ACBDFGNHMC, ... Мой подход состоял в том, чтобы использовать массив в качестве держателя позиции и генерировать все перестановки, чтобы идентифицировать все действительные упорядочения. Наихудшая временная сложность для этого - N! где N - размер набора символов. Можем ли мы сделать лучше, чем подход грубой силы.

Заранее спасибо.

Answer 1

Дональд Кнут написал статью Структурированная программа для генерации всех топологических сортировочных структур . Эта статья была первоначально опубликована в 1974 г.

Естественный способ решения этой проблемы - позволить x ₁ быть элемент, не имеющий предшественников, затем стереть все связи из x ₁ 2 был элементом & ne; x ₁ без предшественников в системе, какой она сейчас существует, затем стереть все отношения из x ₂ only , поскольку x ₁ должен быть элементом без предшественников, а х ₂ должен быть без предшественников когда все отношения x ₁ все решение проблемы топологической сортировки; это типичный пример процедуры «возврата», где на каждом этапе мы рассматриваем Подзадача из "Найти все способы для завершения данного частичного перестановка x ₁ x ₂ ... x _k в топологическая сортировка x ₁ x ₂ ... x _n . " Общий метод состоит в том, чтобы перейти на все возможные варианты x _{k + 1} .
Основная проблема в приложениях возврата - найти подходящий способ упорядочить данные так, чтобы их было легко последовательность возможных вариантов x _{k + 1} ; в этом В случае, если нам нужен эффективный способ обнаружить множество всех элементов & ne; {x ₁ , ..., x _k }, которые не имеют других предшественников чем х ₁ , ..., х _к , и поддерживать эти знания эффективно при переходе от одной подзадачи к другой.

Статья содержит псевдокод для эффективного алгоритма. Временная сложность для каждого выхода составляет O (m + n), где m - это количество входных отношений, а n - это количество букв. Я написал программу на C ++, которая реализует алгоритм, описанный в статье - поддержание имен переменных и функций, - который принимает буквы и отношения из вашего вопроса в качестве входных данных. Я надеюсь, что никто не будет жаловаться на то, что программа дает этот ответ - из-за языкового тега.

#include <iostream>
#include <deque>
#include <vector>
#include <iterator>
#include <map>

// Define Input
static const char input[] =
    { 'A', 'D', 'G', 'H', 'B', 'C', 'F', 'M', 'N' };
static const char crel[][2] =
    {{'A', 'B'}, {'B', 'F'}, {'G', 'H'}, {'D', 'F'}, {'M', 'N'}};

static const int n = sizeof(input) / sizeof(char);
static const int m = sizeof(crel) / sizeof(*crel);

std::map<char, int> count;
std::map<char, int> top;
std::map<int, char> suc;
std::map<int, int> next;
std::deque<char> D;
std::vector<char> buffer;

void alltopsorts(int k)
{
    if (D.empty())
        return;
    char base = D.back();

    do
    {
        char q = D.back();
        D.pop_back();

        buffer[k] = q;
        if (k == (n - 1))
        {
            for (std::vector<char>::const_iterator cit = buffer.begin();
                 cit != buffer.end(); ++cit)
                 std::cout << (*cit);
            std::cout << std::endl;
        }

        // erase relations beginning with q:
        int p = top[q];
        while (p >= 0)
        {
            char j = suc[p];
            count[j]--;
            if (!count[j])
                D.push_back(j);
            p = next[p];
        }

        alltopsorts(k + 1);

        // retrieve relations beginning with q:
        p = top[q];
        while (p >= 0)
        {
            char j = suc[p];
            if (!count[j])
                D.pop_back();
            count[j]++;
            p = next[p];
        }

        D.push_front(q);
    }
    while (D.back() != base);
}

int main()
{
    // Prepare
    std::fill_n(std::back_inserter(buffer), n, 0);
    for (int i = 0; i < n; i++) {
        count[input[i]] = 0;
        top[input[i]] = -1;
    }

    for (int i = 0; i < m; i++) {
        suc[i] = crel[i][1]; next[i] = top[crel[i][0]];
        top[crel[i][0]] = i; count[crel[i][1]]++;
    }

    for (std::map<char, int>::const_iterator cit = count.begin();
         cit != count.end(); ++cit)
        if (!(*cit).second)
            D.push_back((*cit).first);

    alltopsorts(0);
}

Answer 2

Существует без алгоритма , который может работать лучше, чем O (N!), Если есть N!ответы.Но я думаю, что есть лучший способ понять проблему:

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

Answer 3

хорошо, я сразу признаю, что у меня нет оценки сложности времени для среднего случая, но, возможно, помогут следующие два наблюдения.

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

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

даже с «тупым» поиском вы можете заметить, что вы часто можете обрезать результаты поиска, сверяя свой заказ в любой точке с имеющимися у вас парами.

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

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

надеюсь, что это поможет некоторым.

Answer 4

Я бы решил это так:

1. Посмотрите на первую букву: (A -> B -> F)
2. Посмотрите на вторую букву,но учитывайте только тех, у кого первая буква одинакова: (D) , (C) , (M -> N)
3. Посмотрите натретья буква, но учитываются только те, у кого одинаковые буквы 1. и 2.: (G -> H) , (D -> F)
4. И таквключен, пока что-то осталось ... (посмотрите на N-ю букву, сгруппируйте по предыдущим буквам)

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