algorithm - 给定一本字典，找到所有可能的字母顺序

Question

我最近被问到以下面试问题:

You have a dictionary page written in an alien language. Assume that the language is similar to English and is read/written from left to right. Also, the words are arranged in lexicographic order. For example the page could be: ADG, ADH, BCD, BCF, FM, FN
You have to give all lexicographic orderings possible of the character set present in the page.

我的做法如下:A 的优先级高于 B，G 的优先级高于 H。因此我们有关于某些字符排序的信息:

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

可能的顺序可以是 ABDFGNHMC、ACBDFGNHMC、...我的方法是使用数组作为位置持有者并生成所有排列以识别所有有效排序。最坏情况下的时间复杂度是 N!其中 N 是字符集的大小。我们能否比蛮力方法做得更好。

提前致谢。

Answer 1

Donald Knuth 撰写了论文 A Structured Program to Generate all Topological Sorting Arrangements .这篇论文最初发表于 1974 年。论文中的以下引述使我更好地理解了这个问题(在文中，关系 i < j 代表“i 先于 j”):

A natural way to solve this problem is to let x₁ be an element having no predecessors, then to erase all relations of the from x₁ < j and to let x₂ be an element ≠ x₁ with no predecessors in the system as it now exists, then to erase all relations of the from x₂ < j , etc. It is not difficult to verify that this method will always succeed unless there is an oriented cycle in the input. Moreover, in a sense it is the only way to proceed, since x₁ must be an element without predecessors, and x₂ must be without predecessors when all relations x₁ < j are deleted, etc. This observation leads naturally to an algorithm that finds all solutions to the topological sorting problem; it is a typical example of a "backtrack" procedure, where at every stage we consider a subproblem of the from "Find all ways to complete a given partial permutation x₁x₂...x_k to a topological sort x₁x₂...x_n ." The general method is to branch on all possible choices of x_k+1.
A central problem in backtrack applications is to find a suitable way to arrange the data so that it is easy to sequence through the possible choices of x_k+1 ; in this case we need an efficient way to discover the set of all elements ≠ {x₁,...,x_k} which have no predecessors other than x₁,...,x_k, and to maintain this knowledge efficiently as we move from one subproblem to another.

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