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

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

    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, но такой функции не нашел. Меня интересует, есть ли в некоторых пакетах готовый модуль для завершения этого процесса. Большое спасибо.


python-3.x matrix permutation triangular symmetric
person Zhentao    schedule 13.03.2019    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

Obtaining a Triangular Matrix by Independent Row-Column Permutations
Guillaume Fertin, Irena Rusu, Stéphane Vialette
person MBo    schedule 13.03.2019
comment
Большое спасибо. На самом деле, я нашел эту статью раньше, но только что просмотрел ее. Я внимательно прочитаю. Я использовал слово «треугольный» вместе с книгой. Я просто хочу одновременно изменить строку или столбец, а затем переместить как можно больше единиц над диагналом. Я преднамеренно разработал заблокированный блок в примере, который после перестановки помещается в нижний правый угол. Еще раз спасибо за вашу информацию. - person Zhentao; 14.03.2019