最近有人问我以下面试问题:



我的方法如下:
A的优先级高于B,G的优先级高于H.
因此,我们获得了有关订购某些字符的信息:

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

可能的订购可以是ABDFGNHMC,ACBDFGNHMC,...
我的方法是使用数组作为位置保持器,并生成所有排列以标识所有有效顺序。为此,最坏的时间复杂度是N!其中N是字符集的大小。
我们能做得比蛮力方法更好吗?

提前致谢。

最佳答案

唐纳德·努斯(Donald Knuth)已写了A Structured Program to Generate all Topological Sorting Arrangements文件。这篇文章最初是在1974年被伪造的。该文章的以下引文使我对问题有了更好的理解(在文本中,i


该论文包括用于有效算法的伪代码。每个输出的时间复杂度为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);
}

关于algorithm - 给定字典,找到所有可能的字母顺序,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/7282049/

10-11 22:44
查看更多