Реализация поиска по глубине в дереве перестановок в Python

Question

У меня есть квадратичная матрица размера n, скажем, A, с неотрицательными вещественными записями a_ij. Кроме того, у меня есть дерево перестановок. Для n = 3 это выглядит так: .

Теперь я хотел бы выполнить поиск по глубине (на самом деле я не знаю, является ли «поиск по глубине» правильным описанием для этого, но давайте пока воспользуемся им) вдоль ветвей дерева в следующем способ:

В первом частичном дереве слева, сделайте следующее, начиная с «пустой» перестановки (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 и возвращаются к первому уровню и проверяют, является ли a_13> a_31. Если это правда, установите (1,3, x), а затем проверьте, является ли a_23> a_32. Если это так, сохраните (1,3,2) в P и переходите к следующему частичному дереву. Если a_31> a_13 или a_32> a_23 не сохраняют перестановку в P и продолжают ту же процедуру для следующего частичного дерева.

Эту процедуру / алгоритм я хотел бы реализовать для произвольного натурального n> 0 с помощью Input только матрицы A и n и в качестве Output всех перестановок размера n, которые удовлетворяют этим условиям. В настоящее время я не могу реализовать это в общих чертах.

Желательно в Python, но псевдо-код тоже подойдет. Я также хочу избежать таких функций, как «Перестановка itertools», потому что в случае использования мне нужно применить это для больших n, например, n = 100, и тогда перестановка itertools будет очень медленной.

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 начинается как пустой кортеж, но растет в рекурсии. Если в частичной перестановке есть хотя бы два элемента, мы можем проверить последние два элемента и проверить, не прошел ли он тест, и отклонить его, если это произойдет (удалив его поддерево из пространства поиска). Если это полная перестановка, которая не была отклонена, мы ее возвращаем. Если он еще не заполнен, мы добавляем к нему все возможные индексы, которых там еще нет, и возвращаемся.

tinyEDIT: Кстати, параметр n является своего рода избыточным, потому что n = len(a) в верхней части функции должен заботиться об этом.