给定一本字典,找到所有可能的字母排序

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

Donald Knuth 撰写了论文《生成所有拓扑排序安排的结构化程序》。这篇论文最初发表于 1974 年。论文中的以下引用使我对这个问题有了更好的理解（文中关系 i < j 代表“i 先于 j”）：

\n\n

\n

解决这个问题的一个自然方法是让 x ₁为\n 没有前驱的元素，然后从 x ₁ < j 中删除 \n 的所有关系，并让 x ₂为 ≠\nx ₁没有前驱的元素在现有的系统中，\n 然后删除 x ₂ < j 等的所有关系。不难验证此方法将始终成功，除非\n 输入中存在定向循环。此外，从某种意义上说，这是唯一继续进行的方法，因为 x ₁必须是没有前驱的元素，并且当删除所有关系 x _{1 < j 时，x 2}必须没有前驱，等等。这\n n 观察自然会导致找到拓扑排序问题的所有\n 解的算法；这是“回溯”过程的典型示例，在每个阶段我们都考虑“找到完成给定部分排列 x ₁ x ₂ ...x _k到 a的所有方法”的子问题\n 拓扑排序 x ₁ x ₂ ...x _n。” 一般方法是在 x _k+1的所有可能选择上进行分支。回溯应用程序中的一个核心问题是找到一种合适的方式来排列数据，以便可以轻松地对 x _k+1的可能选择进行排序；_{在这种情况下，我们需要一种有效的方法来发现所有元素 ≠\n {x 1} ,...,x _k }的集合，这些元素除了 x ₁ ,...,x _k之外没有前辈，并且当我们从一个子问题转移到另一个子问题时，有效地维持这一知识。

\n

\n\n

该论文包含一个高效算法的伪代码。每个输出的时间复杂度为 O(m+n)，其中 m 是输入关系的数量，n 是字母的数量。我编写了一个 C++ 程序，它实现了论文 \xe2\x80\x93 中描述的算法，维护变量和函数名称 \xe2\x80\x93，该算法将问题中的字母和关系作为输入。我希望没有人抱怨因为与语言无关的标签而将程序提供给这个答案 \xe2\x80\x93 。

\n\n

#include <iostream>\n#include <deque>\n#include <vector>\n#include <iterator>\n#include <map>\n\n// Define Input\nstatic const char input[] =\n    { \'A\', \'D\', \'G\', \'H\', \'B\', \'C\', \'F\', \'M\', \'N\' };\nstatic const char crel[][2] =\n    {{\'A\', \'B\'}, {\'B\', \'F\'}, {\'G\', \'H\'}, {\'D\', \'F\'}, {\'M\', \'N\'}};\n\nstatic const int n = sizeof(input) / sizeof(char);\nstatic const int m = sizeof(crel) / sizeof(*crel);\n\nstd::map<char, int> count;\nstd::map<char, int> top;\nstd::map<int, char> suc;\nstd::map<int, int> next;\nstd::deque<char> D;\nstd::vector<char> buffer;\n\nvoid alltopsorts(int k)\n{\n    if (D.empty())\n        return;\n    char base = D.back();\n\n    do\n    {\n        char q = D.back();\n        D.pop_back();\n\n        buffer[k] = q;\n        if (k == (n - 1))\n        {\n            for (std::vector<char>::const_iterator cit = buffer.begin();\n                 cit != buffer.end(); ++cit)\n                 std::cout << (*cit);\n            std::cout << std::endl;\n        }\n\n        // erase relations beginning with q:\n        int p = top[q];\n        while (p >= 0)\n        {\n            char j = suc[p];\n            count[j]--;\n            if (!count[j])\n                D.push_back(j);\n            p = next[p];\n        }\n\n        alltopsorts(k + 1);\n\n        // retrieve relations beginning with q:\n        p = top[q];\n        while (p >= 0)\n        {\n            char j = suc[p];\n            if (!count[j])\n                D.pop_back();\n            count[j]++;\n            p = next[p];\n        }\n\n        D.push_front(q);\n    }\n    while (D.back() != base);\n}\n\nint main()\n{\n    // Prepare\n    std::fill_n(std::back_inserter(buffer), n, 0);\n    for (int i = 0; i < n; i++) {\n        count[input[i]] = 0;\n        top[input[i]] = -1;\n    }\n\n    for (int i = 0; i < m; i++) {\n        suc[i] = crel[i][1]; next[i] = top[crel[i][0]];\n        top[crel[i][0]] = i; count[crel[i][1]]++;\n    }\n\n    for (std::map<char, int>::const_iterator cit = count.begin();\n         cit != count.end(); ++cit)\n        if (!(*cit).second)\n            D.push_back((*cit).first);\n\n    alltopsorts(0);\n}\n

\n