Определить, является ли какая-либо перестановка строк в матрице Toeplitz

A Toeplitz matrix "- это матрица, в которой каждая нисходящая диагональ слева направо постоянна." Учитывая двоичную матрицу M, существует ли эффективный алгоритм, чтобы определить, есть ли перестановка строк, которые делают его Toeplitz?

Например, установите

M= [0 1 1]
   [1 1 0]
   [1 0 1]

Если вы меняете первый и второй строки, вы получаете

[1 1 0]
[0 1 1]
[1 0 1]

который является теплицем.

В python вы можете сделать случайную двоичную матрицу следующим образом.

n = 10
h = 10
M =  np.random.randint(2, size=(h,n))

Я хотел бы применить тест к M.

(Обратите внимание, что матрица M не должна быть квадратной.)

Ответы

Ответ 1

Эта проблема может быть решена в линейном O (h * w) времени, где h - количество строк, а w - количество столбцов.

Построить граф, где каждая вершина соответствует подстроке (w-1) -length, которая может быть либо префиксом, либо суффиксом некоторой строки в матрице. Одна вершина может соответствовать нескольким подстрокам. Подключите эти вершины к краям h. Каждому ребру соответствует строка матрицы. Он направлен от вершины, соответствующей этому префиксу строки, вершине, соответствующей этому суффиксу строки.

Чтобы определить, является ли какая-либо перестановка строк теплицевой матрицей, достаточно проверить, является ли построенный граф эйлеровым графом. Чтобы найти перестановку, достаточно найти Эйлеровский путь на этом графике.

Нам нужен эффективный способ связывания вершин и ребер. Прямой подход предполагает сравнение каждой пары подстроки строк. Это не очень интересно из-за сложности времени O (h 2 * w).

Здание Обобщенное дерево суффиксов (или массив суффикса) для строк матрицы нуждается только в времени O (h * w). И это дерево позволяет связывать вершины и ребра также в линейном времени: каждый внутренний node с глубиной w-1 представляет некоторую подстроку (w-1) -length (вершина); каждый лист, прикрепленный к этому node, представляет собой некоторый суффикс строки (входящий край); и каждый лист, прикрепленный к этому ребенку node, представляет собой некоторую строку, содержащую эту подстроку в качестве префикса (исходящий край).

Другой альтернативой является использование хэш-карты. С подстрокой (w-1) -length строки матрицы в качестве ключа и пары списков индексов строк (для строк, где эта подстрока является префиксом/суффикс) в качестве значения. Сравнивая с суффиксом tree/array подход, это позволяет упростить реализацию, требует меньше памяти (каждому ключу нужно только пространство для хэш-значения и указатель на начало подстроки), должен работать быстрее (в среднем), но имеет худшую худшую сложность: О (ч 2 * ш).

Ответ 2

Один простой подход, который будет работать для малых матриц:

Sort the rows of M
For each choice of start row
    For each choice of end row
         construct a Toeplitz matrix T from the given start and end row
         Sort the rows of T and compare to M
         If you find a match then T is a permutation of M that is Toeplitz

Это основано на том, что матрица Тёплица однозначно определена после того, как вы знаете начальную и конечную строки.

Однако этот подход не особенно эффективен.

Пример кода Python

M= [[0, 1, 1],
   [1, 1, 0],
   [1, 0, 1]]

n=len(M)
M2 = sorted(M)
for start in M2:
    for end in M2:
        v = end+start[1:]
        T = [v[s:s+n] for s in range(n-1,-1,-1)]
        if sorted(T)==M2:
            print 'Found Toeplitz representation'
            print T

печатает

Found Toeplitz representation
[[0, 1, 1], 
 [1, 0, 1], 
 [1, 1, 0]]
Found Toeplitz representation
[[1, 0, 1],
 [1, 1, 0],
 [0, 1, 1]]
Found Toeplitz representation
[[1, 1, 0], 
 [0, 1, 1], 
 [1, 0, 1]]

Ответ 3

Вы можете провести предварительную проверку для условия исключения:

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

Кроме того, если я и я + 1 - два соседних столбца, то:

  • Если sum(i+1) = sum(i) + 1, то мы знаем, что самый нижний элемент в столбце я должен быть 0, а самый верхний элемент в столбце (i + 1) должен быть 1.

  • Если sum(i+1) = sum(i) - 1, то мы знаем, что самый нижний элемент в столбце я должен быть 1, а самый верхний элемент в столбце (i + 1) должен быть 0.

  • Если sum(i+1) = sum(i), то мы знаем, что самый нижний элемент в столбце я должен быть равен самому верхнему элементу в столбце (i + 1).

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

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

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

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