在 Python 中的置换树上实现深度优先搜索

Question

我有一个大小为 n 的二次矩阵，比如 A，具有非负实数 a_ij。此外，我有一个排列树。对于 n = 3，它看起来像这样：.

现在我想沿着树的分支进行深度搜索（我真的不知道，"Depth-search" 是否是对此的正确描述，但让我们现在使用它）以下方式：

在最左边的第一个部分树上，从 "empty" 排列 (x,x,x) 开始执行以下操作：

如果a_12>a_21设置(1,2,x)然后检查是否a_23>a_32。如果也是这样，将 (1,2,3) 保存在一个列表中，比如 P。然后返回到第一级并检查是否 a_13 > a_31 等等。如果 a_21 > a_12 或者 a_32 > a_23 不保存 P 中的 Permutation 回到第一层检查是否 a_13 > a_31.如果为真，则设置 (1,3,x) 然后检查是否 a_23 > a_32。如果这是真的，将 (1,3,2) 保存在 P 中并继续下一个部分树。如果 a_31 > a_13 或 a_32 > a_23 不保存 P 中的排列并继续对下一个部分树执行相同的过程。

这 procedure/algorithm 我想为任意自然数 n > 0 实现，输入仅为矩阵 A 和 n，输出为满足这些条件的所有大小为 n 的排列。到目前为止，我无法以一般方式实现它。

最好是 Python，但伪代码也不错。我也想避免像 "itertools Permutation" 这样的函数，因为在用例中我需要将它应用于大 n，例如 n = 100，然后 itertools Permutation 非常慢。

Answer 1

如果我没理解错的话，这应该能满足您的需求：

import numpy as np
from itertools import permutations

def fluboxing_permutations(a, n):
    return [p for p in permutations(range(n))
        if all(a[i, j] > a[j, i] for i, j in zip(p, p[1:]))]

n = 3
a = np.random.random([n, n])
fluboxing_permutations(a, n)

itertools.permutations 将按字典顺序产生排列，这对应于您的树；然后我们检查对于排列中每个连续的索引对，矩阵中的元素大于交换索引处的元素。如果是这样，我们保留排列。

（不知道如何描述函数的作用，所以我起了个新名字。希望你喜欢。如果有人知道更好的描述方式，请编辑！:P）

编辑：这是一个递归函数，它应该做同样的事情，但有修剪：

def fluboxing_permutations_r(a, n):
    nset = set(range(n))
    def inner(p):
        l = len(p)
        if l > 1 and a[p[-2]][p[-1]] <= a[p[-1]][p[-2]]:
            return []
        if l == n:
            return [p]
        return [r for i in nset - set(p)
                for r in inner(p + (i,))]
    return inner(())

p 以空元组开始，但它在递归中增长。一旦部分排列中至少有两个元素，我们就可以测试最后两个元素并查看它是否未通过测试，如果失败则拒绝它（将其子树从搜索中删除 space）。如果它是一个没有被拒绝的完整排列，我们 return 它。如果它还没有满，我们将所有可能的索引附加到它上面，然后递归。

tinyEDIT: 顺便说一句，参数 n 有点多余，因为函数顶部的 n = len(a) 应该处理它。

在 Python 中的置换树上实现深度优先搜索

Implementation of Depth-First-Search on a permutation tree in Python

sorting

algorithm

permutation

depth-first-search

python-3.x