Сложность: одна матрица является перестановкой строк / столбцов другой матрицы

Question

1. Даны две m x n матриц A и B, элементы которых принадлежат множеству S. Проблема: можно ли переставить строки и столбцы A, чтобы получить B? Какова сложность алгоритмов для решения этой проблемы? Детерминанты частично помогают (когда m = n): необходимым условием является то, что det (A) = +/- det (B).

2. Также разрешите A содержать слова "все равно", которые соответствуют любому элементу B.

3. Кроме того, если S конечно, разрешите перестановки элементов из A.

Это не домашнее задание - оно связано с разгаданной загадкой 17x17.

Answer 1

См. Ниже пример перестановки строк и столбцов матрицы:

Соблюдайте начальную и конечную матрицы. Все элементы в строке или столбце сохраняются только потому, что их порядок изменился. Также изменение в относительных положениях одинаково по строкам и столбцам

например. см. 1 в начальной и конечной матрицах. У его ряда есть элементы 12, 3 и 14 вместе с ним. Также его колонка имеет 5, 9 и 2 вместе с ней. Это сохраняется в трансформациях.

Основываясь на этом факте, я выдвигаю этот основной алгоритм, чтобы найти для данной матрицы A, можно ли переставить ее строки и столбцы для получения матрицы B.

 1. For each row in A, sort all elements in the row. Do same for B.
 2. Sort all rows of A (and B) based on its columns. ie. if row1 is {5,7,16,18} and row2 is {2,4,13,15}, then put row2 above row1
 3. Compare resultant matrix A' and B'. 
 4. If both equal, then do (1) and (2) but for columns on ORIGINAL matrix A & B instead of rows.
 5. Now compare resultant matrix A'' and B''