Алгоритм определения перестановок ганкелевых матриц

Я пытаюсь написать код, чтобы определить, является ли матрица перестановкой матрицы Ханкеля, но я не могу думать об эффективном решении, отличном от очень медленной грубой силы. Вот спецификация.

Ввод: n на n матрицу M, чьи записи равны 1 или 0.

Формат ввода: Промежуточные строки. Одна строка на строку. Например

Вывод: Перестановка строк и столбцов M, так что M является Hankel matrix, если это возможное. Матрица Ганкеля имеет постоянные косоугольные диагонали (положительные наклонные диагонали).

Когда я говорю перестановку, я имею в виду, что мы можем применить одну перестановку к порядку строк и, возможно, другую по столбцам.

Буду очень признателен за любые идеи.

Ответ 1

Без потери общности мы будем предполагать, что число единиц меньше, чем 1. Затем мы можем найти возможные диагонали в матрице Ханкеля, которые могут быть равны 0, чтобы дать нам соответствующее число 0 во всей матрице. И это даст нам возможные ганкелевые матрицы. Оттуда вы можете подсчитать количество 0 в каждом столбце и сравнить его с числом 0 в столбцах исходной матрицы. Как только вы это сделали, у вас гораздо меньше места для выполнения поиска грубой силы: перестановка на столбцах и строках, имеющих правильное количество 0.

Пример: OP предложил матрицу 4x4 с 7 0. Нам нужно разбить это, используя набор {4,3,3,2,2,1,1}. Итак, или разделов будет:

{4,3}
{4,2,1} (2 из этих матриц)
{3,3,1}
{3,2,2}
{3,2,1,1} (2 из этих матриц)

И это дает нам ганкелевые матрицы (исключая симметрии)

1 1 0 0    1 1 1 0    0 1 1 0    1 1 0 1
1 0 0 1    1 1 0 1    1 1 0 1    1 0 1 0
0 0 1 1    1 0 1 0    1 0 1 0    0 1 0 1
0 1 1 1    0 1 0 0    0 1 0 1    1 0 1 0

1 0 0 1    0 1 1 1    0 1 0 1
0 0 1 1    1 1 1 0    1 0 1 1
0 1 1 0    1 1 0 0    0 1 1 0
1 1 0 1    1 0 0 0    1 1 0 0

Исходная матрица имела столбцы с 3, 1, 2 и 1 0 в четырех столбцах. Сравнивая это с 7 возможными матрицами Ханкеля, мы получаем 2 возможности

1 1 1 0    0 1 1 1    
1 1 0 1    1 1 1 0    
1 0 1 0    1 1 0 0    
0 1 0 0    1 0 0 0

Теперь есть только 4 возможных перестановки, которые могли бы сопоставить исходную матрицу с каждым из них: у нас есть только один выбор, основанный на столбцах с 2 и 3 0, но 2 варианта для столбцов с 1 0, а также 2 выбор для строк с 1 0. Проверяя эти перестановки, мы видим, что следующая матрица Ханкеля является перестановкой исходного

Ответ 2

Единственное, что получил первый ответ на этот вопрос, заключается в том, что перестановка строк и столбцов не изменяет суммы строк или суммы столбцов.

Еще одно простое наблюдение заключается в том, что в матрице Ханкеля разница в сумме строк между двумя последовательными строками равна -1, 0 или 1, и каждый случай дает нам ограничение на строки. Если разность равна 0, то вводимая переменная равна выходной переменной; в противном случае мы знаем, что 0 и которое равно 1.

имеет суммы строк 3, 2, 1, 3. Заказы, соблюдающие требование разности, равны 1 2 3 3 и 3 3 2 1, а wlog можно отменить развороты, так как перестановка строк и перестановок столбцов просто поворачивает матрицу на 180 градусов. Поэтому мы сводим к рассмотрению четырех перестановочных матриц (двух возможных порядков 3s в суммах строк и двух в суммах столбцов):

0 0 1 0    0 0 1 0    0 0 0 1    0 0 0 1
0 0 1 1    0 0 1 1    0 0 1 1    0 0 1 1
0 1 1 1    1 1 0 1    0 1 1 1    1 1 1 0
1 1 0 1    0 1 1 1    1 1 1 0    0 1 1 1

Мы могли бы продолжить анализ, заметив, что, заставляя исходные строки иметь суммы 1 и 2, мы ограничиваем порядок столбцов суммой 3, так как

0 0 1 0
0 0 1 1

не является допустимым начальным двумя строками матрицы Ганкеля. Независимо от того, легко ли реализовать этот вид рассуждений, зависит от вашей парадигмы программирования.

Обратите внимание, что в худшем случае этот вид рассуждений по-прежнему не оставляет полиномиального числа случаев для перебора силы через.

Ответ 3

Вот некоторые идеи.

1)

Перестановки строк и столбцов сохраняют суммы строк и столбцов:

1 0 1 0 - 2
0 0 0 1 - 1  row sums
1 0 0 0 - 1
1 1 1 0 - 3
| | | |
3 1 2 1
column sums

Каким бы способом вы не переставляли строки, суммы строк по-прежнему будут {2, 1, 1, 3} в некоторой перестановке; суммы столбцов не будут изменены. И наоборот. Матрицы Ханкеля и их перестановки всегда будут иметь тот же набор сумм строк, что и суммы столбцов. Это дает вам быстрый тест, чтобы исключить набор нежизнеспособных матриц.

2)

Я полагаю, что матрицы Ханкеля всегда могут быть перестановлены таким образом, что их суммы строк и столбцов находятся в порядке возрастания, и результат все еще является матрицей Ханкеля:

0 1 1 0 - 2         0 0 0 1 - 1
1 1 0 0 - 2         0 0 1 1 - 2
1 0 1 1 - 3   -->   0 1 1 0 - 2
0 0 1 0 - 1         1 1 0 1 - 3
| | | |             | | | |
2 2 3 1             1 2 2 3

Поэтому, если матрицу можно переставить в матрицу Ханкеля, ее можно также перевести в матрицу Ханкеля восходящей строки и суммы столбца. То есть мы можем уменьшить количество перестановок, необходимых для тестирования, только тестируя перестановки, где суммы строк и столбцов находятся в порядке возрастания.

3)

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

Результат состоит в том, что нам нужно только проверить перестановки столбцов столбцов или, а не столбцы и.

Применяется к исходному примеру:

1 0 1 0 - 2       0 0 0 1       0 1 0 0 - 1     0 0 0 1
0 0 0 1 - 1       1 0 0 0       0 0 0 1 - 1     0 1 0 0
1 0 0 0 - 1  -->  1 0 1 0  -->  0 0 1 1 - 2 --> 0 0 1 1 = Hankel!
1 1 1 0 - 3       1 1 1 0       1 0 1 1 - 3     1 0 1 1
| | | |
3 1 2 1      permute rows into|   ditto     | try swapping    
              ascending order | for columns |  top 2 rows

4)

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

0 1 1 0       0 1 0 1       0 0 1 1
1 0 0 1       0 1 1 0       0 1 0 1  New
1 0 1 0  -->  1 0 0 1  -->  1 0 1 0 Hankel
0 1 0 1       1 0 1 0       1 1 0 0
Original       rows         columns
 Hankel      ascending     ascending

Если это правда (и я все еще не определился), нам нужно только создать и протестировать одну перестановку любой заданной входной матрицы. Эта перестановка ставит как строки, так и столбцы в порядке возрастания суммы, а в случае равных сумм упорядочивает их по их двоичным интерпретациям. Если эта результирующая матрица не является Hankel, то нет перестановки, которая сделает ее Hankel.

Надеюсь, что вы поймете путь к алгоритму!

Приложение: Контрпримеры?

Пример @orlp:

0 0 1 0     0 0 1 0     0 0 0 1
0 1 0 1     0 1 0 1     0 1 1 0
1 0 1 1 --> 0 1 1 1 --> 0 1 1 1
0 1 1 1     1 0 1 1     1 0 1 1
  (A)         (B)         (C)

A: Оригинальный Ханкель. Суммы строк составляют 1, 2, 3, 3; Строки 3 и 4 не находятся в двоичном порядке.
B: свопинг строк 3 и 4. Столбцы 3 и 4 не находятся в двоичном порядке.
C: Обмен столбцами 3 и 4. Результат - это Hankel и удовлетворяет всем свойствам.

Пример @Degustaf:

1 1 0 1     0 1 0 0     0 0 1 0
1 0 1 0     1 0 0 1     0 1 0 1
0 1 0 0 --> 1 0 1 0 --> 1 0 0 1
1 0 0 1     1 1 0 1     0 1 1 1
  (A)         (B)         (C)

A: Оригинальная ганкелевая матрица. Строковые суммы - 3, 2, 1, 2.
B: Переставить так, чтобы сумма строк составляла 1, 2, 2, 3, а строки суммы 2 находились в восходящем двоичном порядке (то есть 1001, 1010)
C: Переупорядочить суммы столбцов до 1, 2, 2, 3, с двумя столбцами суммы 2 в порядке (0101, 1001). Результатом является Hankel и удовлетворяет всем свойствам. Также обратите внимание, что перестановка в столбцах соответствует перестановке в строках: новый порядок столбцов из старого - {3, 4, 2, 1}, ту же операцию, что и для A от B.

Примечание. Я предлагаю двоичный порядок (# 4) только для ситуаций тай-брейка в сумме строк или столбцов, а не в качестве замены для сортировки в (# 2).