24

我的女朋友在一次采访中被问到这个问题，我非常喜欢它，我想我会分享它......编写一个接收字典（单词数组）的算法。该数组按字典顺序排序，但 abc 顺序可以是任何值。例如，它可以是 z、y、x、..、c、b、a。或者它可能完全搞砸了：d，g，w，y，......它甚至不需要包括所有的abc字母，最后它根本不必是字母。它可以是构成字符串的任何符号。例如，它可以由 5、α、!、@、θ 组成……你明白了。这取决于你的算法来发现字母是什么（简单的部分）。

该算法应返回符号的正确字典顺序。

注意/需要考虑的事项： 1. 对于给定的字典，您是否总能发现所有字母的完整顺序？考虑一个只有 1 个单词的字典，有多个符号... 2. 你不能假设字典没有错误。该算法应确定字典是否包含矛盾并输出存在错误。3. 提示：想一个好的数据结构来表示你发现的符号之间的关系。这应该使问题更容易。

我可能会在明天发布我的解决方案。我绝不声称它是最有效的。我想先看看别人的想法。希望你喜欢这个问题

PS 我认为发布解决方案的最佳格式是使用伪代码，但我将此留给您考虑

4

4 回答 4

34

这是有向无环图上的拓扑排序。您需要首先构建图形：顶点是字母，如果一个在字典顺序上小于另一个，则有一条边。然后拓扑顺序会给你答案。

矛盾在于有向图不是无环的。唯一性取决于是否存在哈密顿路径，该路径可在多项式时间内进行测试。

构建图表

您可以通过比较字典中每两个连续的“单词”来做到这一点。假设您有这两个词一个接一个出现：

x156@
x1$#2z

然后你找到最长的公共前缀，x1在这种情况下，并检查这个前缀之后的紧随其后的字符。在这种情况下，我们有5和$。由于单词在字典中按此顺序出现，我们可以确定5必须在字典上小于$。

同样，给定以下单词（在字典中一个接一个出现）

jhdsgf
19846
19846adlk

我们可以'j' < '1'从第一对中看出这一点（其中最长的公共前缀是空字符串）。第二对没有告诉我们任何有用的信息（因为一个是另一个的前缀，所以没有要比较的字符）。

现在假设稍后我们会看到以下内容：

oi1019823
oij(*#@&$

然后我们发现了一个矛盾，因为这对说'1' < 'j'。

拓扑排序

有两种传统的拓扑排序方式。算法上更简单的是深度优先搜索方法，其中从x到yif有一条边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)，这是字典的大小。

于 2010-06-26T10:51:10.890 回答
3

您想找到符号的总顺序。

1）您显然不能总是确定总订单。

2）您可以使用有向无环图来表示符号之间的偏序。每个字母在图中仅表示一次。您可以通过查看每对连续单词中相同位置的所有字母对来填充它。您在图表中创建的任何循环都指向字典中的错误。您将 a->d、a->b、b->d 等关系集展平为 a->b->d。如果你最后得到的是一个图，一个源（没有前任的字母）和一个汇（没有后继的字母），你有一个总顺序，就像字母表一样。

于 2010-06-26T10:55:43.960 回答
2

我使用维基百科中的其他建议算法解决了这个问题。这是来自维基百科的伪代码：

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)

我认为它为查找路径提供了一种更“常识”的方法（即，如果我正在查看图表并且必须找到路径，我将如何解决它）。尽管如此，它对多基因润滑剂建议的深度优先方法没有任何优势（如果您按照评论中的建议添加循环检测代码）感谢您的评论。答案

于 2010-06-26T12:55:10.650 回答
1

你有一个单词数组中的字典，我建议使用这个数据结构，因为它已经足够好并且转换需要时间。

你想找到正确的字符顺序，

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

你的字典中有 m 个单词。最好有一组规则，例如 (Ci, Cj)，这意味着 Ci <= Cj，其中 i, j 是正自然数并且 i < m, j < m。我们应该有一组错误

因为 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 i = 1, l do foreach j = i + 1, l do if charSet.exists(charI, charJ) and charSet.exists(charJ, charI) error.add("悖论关系", charI, charJ)

在此之后，您可以通过考虑 charI = charJ 在集合中同时存在 (charI, charJ) 和 (charJ, charI) 并且 charI <= charJ 是唯一的规则来构建单词的顺序，反之亦然，我们可以考虑那个 charI < charJ。

结论：使用“<=”关系比使用“<”关系要好，因为“<=”是数论中一个完整的良好有序关系，“<”只是良好的有序关系。注意：如果 charI < charJ 或 charI = charJ，输出必须正确显示。例如，您可以使用以下表示法：characters(C1C2C3, C4, C5C6, ...) 其中 C1 = C2 = C3 < C4 < C5 = C6...

我希望这有帮助。

当然，如果 Wj 包含 Wi 那么我们不能从那里提取规则

于 2010-06-26T14:15:25.273 回答