请解释一下这个算法的流程以及它是如何工作的?(高德纳拓扑排序)

Question

给定 {1....n} 上的关系 ~，其性质为 x~y 表示 x <y，此算法生成所有排列>

V1.[初始化。设置 a[j] <- j 和 a'[j] <- j 表示 0<=j<=n。

V2.[访问。访问排列 a[1]...a[n] 及其逆 a'[1]...a'[n].然后设置 k <- n。

V3.[k可以向左移动吗？设置 j <- a'[k] 和 l <- a[j-1]。如果为 l~k，请转到 V5。

V4.[是的，移动它。设置 a[j-1] <- k、a[j] <- l、a'[k] <- j-1 和 a'[l] <- j。转到 V2。

V5.[不，把k放回去。当 j

Knuth，保佑他，是一个未重建的汇编语言程序员。下面是将此算法渲染到经过测试的无 goto-Python 中。 precedes是关系~。

from itertools import permutations

def topological_orders(n, precedes):
    a = list(range(n + 1))
    ai = a[:]
    while True:
        yield tuple(a[1:])
        k = n
        while True:
            j = ai[k]
            l = a[j - 1]
            if not precedes(l, k):
                a[j - 1] = k
                a[j] = l
                ai[k] = j - 1
                ai[l] = j
                break
            while j < k:
                l = a[j + 1]
                a[j] = l
                ai[l] = j
                j += 1
            a[k] = ai[k] = k
            k -= 1
            if not k > 0:
                return

def test(n, precedes):
    fast_orders = set()
    for order in topological_orders(n, precedes):
        print(order)
        fast_orders.add(order)
    slow_orders = set()
    for order in permutations(range(n + 1)):
        if not any(precedes(order[i], order[j]) for i in range(n + 1) for j in range(i)):
            slow_orders.add(order[1:])
    assert fast_orders == slow_orders

if __name__ == '__main__':
    def divides(a, b):
        return a < b and (a == 0 or b % a == 0)
    test(6, divides)

根据您的意见，我们从

0123.

访问123并将3向左移动。

0132

访问132并将3向左移动。

0312

访问312 .我们不能移动3因为0 ~ 3.将其一直向右移动并尝试2移动。

0123

我们不能移动2因为1 ~ 2.尝试移动1 .我们不能移动1，因为0 ~ 1.试着移动0 - 哎呀，我们完成了。