Быстрое и эффективное использование памяти в двоичной матрице

Question

Я сталкиваюсь с проблемами, пытаясь решить проблему, которая для меня сложнее, чем я предполагал. Учитывая двоичную матрицу NxM, я хочу сгенерировать все возможные решения при условии, что каждый столбец имеет ровно одну «1». Для 2x3 это будет:

1 1
0 0
0 0

1 0
0 1
0 0

1 0
0 0
0 1

0 1
1 0
0 0

0 0
1 1
0 0

0 0
1 0
0 1

0 1
0 0
1 0

0 0
0 1
1 0

0 0
0 0
1 1

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

Но: потребление памяти ужасно, когда я начинаю с

1 1
0 0
0 0

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

Может быть, это просто мой неправильный способ рекурсии, но в настоящее время я должен копировать текущий массив для каждой рекурсии, что, конечно, ужасно, но единственный способ, который я нашел, как например,

0 1
1 0
0 0

и дважды скопировать его для генерации

0 0
1 1
0 0

и

0 0
1 0
0 1

Независимо друг от друга легче. Но освобождение памяти в C при повторном использовании не похоже на мой уровень опыта. Я переписал в Java, надеясь, что GC может помочь мне (не могу в это поверить, но похоже, что так и есть), но, опять же, профилирование говорит, конечно, что копирование данных пожирает 99% циклов.

У вас есть предложения по моей проблеме? Может быть, есть даже название для этого, чтобы не думать о существующих алгоритмах? Есть ли у вас псевдокод для рекурсии под рукой? Большое спасибо от курящего мозга!

Я даже не уверен, является ли это комбинаторной или перестановочной проблемой.

Answer 1

Это довольно просто, без каких-либо "умных" математических трюков.

Во-первых, один стандартный метод представления разреженных матриц известен как список координат : (index_row, index_column, value) для ненулевых записей.

Во-вторых, ваши настройки довольно просты: все значения равны 1. [Итак, вам нужно только сохранить (ix_row, ix_col).]

В-третьих: это становится проще: у вас есть только одна строка на столбец. Таким образом, для данной матрицы размером N x P (строки x столбцы) мы можем предположить, что имеется P записей. Давайте просто предположим, что список координат для данной матрицы имеет 1: P для записей index_column и значение = 1 для всех записей. [Т.е. «полный» список координат будет: (ix_row (1), 1, 1), (ix_row (2), 2, 1), ..., (ix_row (P), P, 1)].

Следовательно, при заполнении списка координат проблема заключается в создании всех возможных индексов строк, которые просто выбирают из 1: N, P раз, с заменой . У вас есть N вариантов для строки для каждой строки в списке координат. Количество матриц N ^ P.

Создать список всех (1: N) x (1: N) x ... x (1: N) векторов довольно просто: начать с (1, 1, 1, ...., 1) и посчитаем в последнем элементе до (1, 1, 1, ..., N) и переходим на один шаг за раз.

Это сгенерирует все необходимые списки координат для описания всех матриц.

Answer 2

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

Зная, что вы делаете простой подсчет, мы можем разработать итеративный подход. Если у вас есть, как в вашем примере матрица 2x3, это эквивалентно подсчету в системе трехзначных чисел с 2 цифрами. Это означает, что наибольшее значение, которое мы можем представить, равно 3 ^ 2 - 1 = 8.

Это означает, что мы будем считать от 0 до 8. Теперь преобразуем в троичный, как вы бы вручную записали число в двоичное. Сколько 3 ^ 1, скажем, в 7? 2! Таким образом, позиция самой левой 1 в вашей матрице - строка 2 (с индексом от 0). Вычтите 3x2 = 6 из числа, которое мы конвертируем, оставив 1. Сколько есть 3 ^ 0? 1! Таким образом, 1 в крайнем правом столбце находится в строке 1.

Отсюда у нас достаточно информации, чтобы распечатать решение, и, выполнив его для всех чисел от 0 до M ^ N - 1, вы получите все свои решения!