Как сделать преобразование матрицы по тумблерам строк и столбцов?

Question

У меня есть квадратная матрица, состоящая из элементов 1 или 0. Переключатель i-й строки переключает все элементы i-й строки (1 становится 0 и наоборот) и j-й столбец переключает все элементы j-го столбца. У меня есть еще одна квадратная матрица похожий размер. Я хочу изменить исходную матрицу на итоговая матрица, использующая минимальное количество переключателей. Например

|0 0 1|
|1 1 1|
|1 0 1|

до

|1 1 1|
|1 1 0|
|1 0 0|

потребует переключения первого ряда и последнего колонка.

Какой будет правильный алгоритм для этого?

Answer 1

В общем, проблема не будет иметь решения. Чтобы увидеть это, обратите внимание, что преобразование матрицы A в матрицу B эквивалентно преобразованию матрицы A - B (вычисленной с использованием двоичной арифметики, так что 0 - 1 = 1) в нулевую матрицу. Посмотрите на матрицу A - B и примените переключатели столбцов (при необходимости), чтобы первая строка стала все 0 или все 1. На этом этапе вы закончили с переключателями столбцов - если вы переключаете один столбец, вы должны переключить их все, чтобы получить правильный первый ряд. Если хотя бы одна строка представляет собой смесь из 0 и 1 на данный момент, проблема не может быть решена. Если каждая строка теперь имеет все 0 или все 1, проблема решается путем переключения соответствующих строк для достижения нулевой матрицы.

Чтобы получить минимум, сравните количество необходимых переключателей, когда первая строка превращается в 0 против 1. В примере OP кандидаты будут переключать столбец 3 и строку 1 или переключать столбцы 1 и 2 и строки 2 и 3. Фактически, вы можете упростить это, посмотрев на первое решение и посмотрев, меньше ли число переключателей больше N - если больше N, чем переключать противоположные строки и столбцы.

Answer 2

Это не всегда возможно. Если вы начнете с матрицы 2x2 с четным числом 1 с, вы никогда не достигнете конечной матрицы с нечетным числом 1 с.

Answer 3

Алгоритм

Упростите задачу из «Попробуйте преобразовать A в B» в «Попробуйте преобразовать M в 0», где M = A xor B. Теперь все позиции, которые должны быть переключены, имеют 1 в них.

Рассмотрим произвольную позицию в M. На нее влияет ровно одно переключение столбца и ровно одно переключение строки. Если его начальное значение - V, наличие переключателя столбца - C, а наличие переключателя строки - R, то конечное значение F - V xor C xor R. Это очень простое отношение, и оно делает проблему тривиальной решить.

Обратите внимание, что для каждой позиции R = F xor V xor C = 0 xor V xor C = V xor C. Если мы установим C, то получим значение R, и наоборот. Это потрясающе, потому что это означает, что если я установлю значение любого переключателя строк, то я заставлю все переключателей столбцов. Любой из этих переключателей столбцов заставит все переключателей строк. Если результатом является матрица 0, то у нас есть решение. Нам нужно попробовать только два случая!

Псевдо-код

function solve(Matrix M) as bool possible, bool[] rowToggles, bool[] colToggles:
    For var b in {true, false}
        colToggles = array from c in M.colRange select b xor Matrix(0, c)
        rowToggles = array from r in M.rowRange select colToggles[0] xor M(r, 0)
        if none from c in M.colRange, r in M.rowRange
                where colToggle[c] xor rowToggle[r] xor M(r, c) != 0 then
            return true, rowToggles, colToggles
        end if
    next var
    return false, null, null
end function

Анализ

Анализ тривиален. Мы пробуем два случая, в которых мы бежим вдоль строки, затем столбца, затем всех ячеек. Следовательно, если имеется r строк и c столбцов, то есть матрица имеет размер n = c * r, то временная сложность составляет O (2 * (c + r + c * r)) = O (c * r) = O ( п). Единственное пространство, которое мы используем, - это то, что требуется для хранения результатов = O (c + r).

Следовательно, алгоритм принимает линейное по размеру матрицы время и использует линейное по размеру выходное пространство. Он асимптотически оптимален по очевидным причинам.

Answer 4

Я придумал алгоритм грубой силы.

Алгоритм основан на 2 гипотезах:
^{(поэтому он может работать не для всех матриц - я проверю их позже)}

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

Алгоритм:
Допустим, у нас есть матрица m = [[1,0], [0,1]].

m: 1 0
   0 1

Мы генерируем список всех номеров строк и столбцов,
как это: ['r0', 'r1', 'c0', 'c1']

Теперь мы применяем грубую силу, иначе изучаем все возможные комбинации шагов.
Например,
мы начинаем с одношагового решения,
ksubsets = [['r0'], ['r1'], ['c0'], ['c1']]

если ни один элемент не является решением, переходите к двухэтапному решению
ksubsets = [['r0', 'r1'], ['r0', 'c0'], ['r0', 'c1'], ['r1', 'c0'], ['r1', 'c1'], ['c0', 'c1']]

и т.д ...

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

---

Реализация Python (протестирована на версии 2.5)

# Recursive definition (+ is the join of sets)
# S = {a1, a2, a3, ..., aN}
#
# ksubsets(S, k) = {
# {{a1}+ksubsets({a2,...,aN}, k-1)}  +
# {{a2}+ksubsets({a3,...,aN}, k-1)}  +
# {{a3}+ksubsets({a4,...,aN}, k-1)}  +
# ... }
# example: ksubsets([1,2,3], 2) = [[1, 2], [1, 3], [2, 3]]
def ksubsets(s, k):
    if k == 1: return [[e] for e in s]
    ksubs = []
    ss = s[:]
    for e in s:
        if len(ss) < k: break
        ss.remove(e)
        for x in ksubsets(ss,k-1):
            l = [e]
            l.extend(x)
            ksubs.append(l)
    return ksubs

def toggle_row(m, r):
    for i in range(len(m[r])):
        m[r][i] = m[r][i] ^ 1

def toggle_col(m, i):
    for row in m:
        row[i] = row[i] ^ 1

def toggle_matrix(m, combos):
    # example of combos, ['r0', 'r1', 'c3', 'c4']
    # 'r0' toggle row 0, 'c3' toggle column 3, etc.
    import copy
    k = copy.deepcopy(m)
    for combo in combos:
        if combo[0] == 'r':
            toggle_row(k, int(combo[1:]))
        else:
            toggle_col(k, int(combo[1:]))

    return k

def conversion_steps(sM, tM):
# Brute force algorithm.
# Returns the minimum list of steps to convert sM into tM.

    rows = len(sM)
    cols = len(sM[0])
    combos = ['r'+str(i) for i in range(rows)] + \
             ['c'+str(i) for i in range(cols)]

    for n in range(0, rows + cols -1):
        for combo in ksubsets(combos, n +1):
            if toggle_matrix(sM, combo) == tM:
                return combo
    return []

Пример:

m: 0 0 0
   0 0 0
   0 0 0

k: 1 1 0
   1 1 0
   0 0 1

>>> m = [[0,0,0],[0,0,0],[0,0,0]]
>>> k = [[1,1,0],[1,1,0],[0,0,1]]
>>> conversion_steps(m, k)
['r0', 'r1', 'c2']
>>> 

Answer 5

Я думаю, что грубая сила не нужна.

Проблема может быть перефразирована с точки зрения группы. Матрицы над полем из 2 элементов составляют коммутативную группу относительно сложения.

Как указывалось ранее, вопрос о том, можно ли переключить A в B, эквивалентен тому, чтобы увидеть, можно ли переключить AB в 0. Обратите внимание, что переключение строки i выполняется путем добавления матрицы с единственными в строке i и нулями. в противном случае переключение столбца j выполняется путем добавления матрицы с единственными в столбце j и нулями в противном случае.

Это означает, что A-B может переключаться на нулевую матрицу тогда и только тогда, когда A-B содержится в подгруппе, генерируемой переключающими матрицами.

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

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

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

2. Переключение столбцов таким образом, чтобы каждый 0 в первой строке становился 1. Если после этого есть строка, в которой встречаются как единицы, так и нули, то решения не существует. В противном случае примените тот же подход к строкам (см. Ниже).

Поскольку столбцы были успешно переключены в том смысле, что в каждой строке содержатся только единицы или нули, существует две возможности:

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

2. Переключение строк таким образом, что каждый 0 в первой строке становится равным нулю.

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

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

Answer 6

Вместо того, чтобы рассматривать это как проблему матрицы, возьмите 9 битов из каждого массива, загрузите каждый из них в 2-байтовые типы размеров (16 бит, которые, вероятно, являются источником массивов в первую очередь), затем сделать один XOR между двумя.

(порядок битов будет отличаться в зависимости от вашего типа процессора)

Первый массив станет: 0000000001111101 Второй массив станет: 0000000111110101

Один XOR будет производить вывод. Никаких петель не требуется. Все, что вам нужно сделать, это «распаковать» результат обратно в массив, если вы все еще хотите. Вы можете прочитать биты, не прибегая к этому, хотя.i

Answer 7

Это проблема поиска в пространстве состояний. Вы ищете оптимальный путь от начального состояния до конечного состояния. В данном конкретном случае «оптимальный» определяется как «минимальное количество операций».

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

Предполагая, что пункт назначения находится в пространстве состояний (в некоторых случаях это НЕ допустимое предположение: см. Ответ Хенрика), я бы попытался выполнить классический эвристический поиск (вероятно, A *, поскольку он о лучшем в породе) алгоритм на проблему и посмотрим что получилось.

Первая, наиболее очевидная эвристика - это «количество правильных элементов».

В любом приличном учебнике по искусственному интеллекту будет обсуждаться поиск и алгоритм A *.

Вы можете представить свою матрицу как неотрицательное целое число, каждая ячейка в матрице которой соответствует ровно одному биту в целом числе. В системе, которая поддерживает 64-битные длинные целые числа без знака, это позволяет вам играть с любым размером до 8x8. Затем вы можете использовать операции исключающего ИЛИ для числа для реализации операций переключения строк и столбцов.

ВНИМАНИЕ: необработанный общий размер пространства состояний равен 2 ^ (N ^ 2), где N - количество строк (или столбцов). Для матрицы 4x4 это 2 ^ 16 = 65536 возможных состояний.

Answer 8

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

for every row, i:
  if matrix1[i] == matrix2[i]
    continue;
  else
    toggle matrix1[i];
    if matrix1[i] == matrix2[i]
      continue
    else
      die("cannot make similar");