Я ищу модуль Python или коды для перестановки асимметричной матрицы в треугольной форме - PullRequest
Новая
       61

Я ищу модуль Python или коды для перестановки асимметричной матрицы в треугольной форме

0 голосов
/ 13 марта 2019

У меня есть асимметричная матрица. 

    A   B   C   D
A   0   0   1   0
B   1   0   0   1
C   0   0   0   0
D   1   1   1   0

Я пытаюсь переключить строки и столбцы, чтобы они превратились в треугольную форму.

Как: 

    C   A   D   B
C   0   1   1   0
A   0   0   1   1
D   0   0   0   1
B   0   0   1   0

Кто-то дал некоторые коды, которые сделаны VBA и используются в Microsoft Excel.Согласно примечанию к этому коду, я нашел документ («Алгоритм 529: перестановки в блочную треугольную форму»), опубликованный в 1978 году, который был сделан в Фортране.Я также нашел статью («Реализация алгоритма Тарьяна для блочной триангуляции матрицы»), в которой можно описать концепцию.

Я смотрю на numpy, но не нашел такой функции.Мне интересно, есть ли готовый модуль в некоторых пакетах для завершения этого процесса.Большое спасибо.

1 Ответ

0 голосов
/ 13 марта 2019

Кстати, я не вижу треугольную матрицу в примере.

Проблема в NP-полная , поэтому вы можете просто генерировать все перестановки строк и столбцов, пока не будет достигнута треугольная матрица.(Или попробуйте реализовать алгоритм из связанной статьи)

Название статьи для записи 

Obtaining a Triangular Matrix by Independent Row-Column Permutations
Guillaume Fertin, Irena Rusu, Stéphane Vialette
...