Добрый день!

Есть матрицы Y размерности NxN, элементы которой могут быть только двух типов, например 0 и 1.

Две или более матрицы считаются эквивалентными, если, переставляя любое количество строк и/или столбцов, их можно привести к одному и тому же виду. Например, для матрицы, в которой есть только один единичный элемент, расположенный в ячейке Y[1][1], все остальные матрицы с только одним единичным элементом, где бы он не находился, являются эквивалентными.

Интересует алгоритм получения всех не эквивалентных матриц при заданных размерности матрицы N и числе M единичных элементов, 0<= M <= (N*N).

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

Спасибо.

С уважением,
Геннадий Майко.

Здравствуйте, Геннадий Майко, Вы писали:

ГМ>Добрый день!

ГМ>Есть матрицы Y размерности NxN, элементы которой могут быть только двух типов, например 0 и 1.

ГМ>Две или более матрицы считаются эквивалентными, если, переставляя любое количество строк и/или столбцов, их можно привести к одному и тому же виду. Например, для матрицы, в которой есть только один единичный элемент, расположенный в ячейке Y[1][1], все остальные матрицы с только одним единичным элементом, где бы он не находился, являются эквивалентными.

ГМ>Интересует алгоритм получения всех не эквивалентных матриц при заданных размерности матрицы N и числе M единичных элементов, 0<= M <= (N*N).

ГМ>В качестве альтернативы интересует алгоритм проверки, что 2 заданные матрицы являются эквивалентными.

ГМ>Спасибо.

ГМ>С уважением,
ГМ>Геннадий Майко.

Эквивалентность.
Матрицы в данном случае в точности эквивалентны двусвязным графам. А Вас интересует алгоритм проверки двух графов на планарность (т.е. именно то,что 2 графа эквивалентны друг другу с точностью до перестановки).
По-моему задача планарности NP-полная. Перебор пишется довольно просто, а дальше можно придумывать разного рода отсечения и оптимизации. Например, простейшая эвристика с неэквивалентностью суммы элементов каждой из матриц. Более того, эта эвристика с успехом может быть применена для отсечения inner cases — как только вы сделали перестановку вы как бы начинаете работать с матрицей размерности меньшей на единицу, пока не вернетесь и сделаете другую перестановку для заданной вершины графа (~строки столбца матрицы).

Здравствуйте, www,

ГМ>>Есть матрицы Y размерности NxN, элементы которой могут быть только двух типов, например 0 и 1.

ГМ>>Две или более матрицы считаются эквивалентными, если, переставляя любое количество строк и/или столбцов, их можно привести к одному и тому же виду. Например, для матрицы, в которой есть только один единичный элемент, расположенный в ячейке Y[1][1], все остальные матрицы с только одним единичным элементом, где бы он не находился, являются эквивалентными.

ГМ>>Интересует алгоритм получения всех не эквивалентных матриц при заданных размерности матрицы N и числе M единичных элементов, 0<= M <= (N*N).

ГМ>>В качестве альтернативы интересует алгоритм проверки, что 2 заданные матрицы являются эквивалентными.


www>Эквивалентность.
www>Матрицы в данном случае в точности эквивалентны двусвязным графам. А Вас интересует алгоритм проверки двух графов на планарность (т.е. именно то,что 2 графа эквивалентны друг другу с точностью до перестановки).
--
В принципе я понимаю, что можно использовать и графы для решения этой проблемы, но мне лично удобнее работать с матрицами и с точки зрения реализации этого алгоритма на С++, и с точки зрения представления окончательного решения.


www>По-моему задача планарности NP-полная. Перебор пишется довольно просто, а дальше можно придумывать разного рода отсечения и оптимизации. Например, простейшая эвристика с неэквивалентностью суммы элементов каждой из матриц. Более того, эта эвристика с успехом может быть применена для отсечения inner cases — как только вы сделали перестановку вы как бы начинаете работать с матрицей размерности меньшей на единицу, пока не вернетесь и сделаете другую перестановку для заданной вершины графа (~строки столбца матрицы).
--
Да, я тоже пока склоняюсь к такому варианту. Эвристик отсечения неэквивалентных схем я уже придумал не одну, да и рекурсию здесь хорошо использовать.

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

С уважением,
Геннадий Майко.

Здравствуйте, www, Вы писали:


www>Эквивалентность.
www>Матрицы в данном случае в точности эквивалентны двусвязным графам. А Вас интересует алгоритм проверки двух графов на планарность (т.е. именно то,что 2 графа эквивалентны друг другу с точностью до перестановки).
www>По-моему задача планарности NP-полная. Перебор пишется довольно просто, а дальше можно придумывать разного рода отсечения и оптимизации. Например, простейшая эвристика с неэквивалентностью суммы элементов каждой из матриц. Более того, эта эвристика с успехом может быть применена для отсечения inner cases — как только вы сделали перестановку вы как бы начинаете работать с матрицей размерности меньшей на единицу, пока не вернетесь и сделаете другую перестановку для заданной вершины графа (~строки столбца матрицы).

Вероятно, вы имели в виду изоморфность? Планарность — это все таки совсем другое понятие

www>Эквивалентность.
www>Матрицы в данном случае в точности эквивалентны двусвязным графам. А Вас интересует алгоритм проверки двух графов на планарность (т.е. именно то,что 2 графа эквивалентны друг другу с точностью до перестановки).
www>По-моему задача планарности NP-полная. Перебор пишется довольно просто, а дальше можно придумывать разного рода отсечения и оптимизации. Например, простейшая эвристика с неэквивалентностью суммы элементов каждой из матриц. Более того, эта эвристика с успехом может быть применена для отсечения inner cases — как только вы сделали перестановку вы как бы начинаете работать с матрицей размерности меньшей на единицу, пока не вернетесь и сделаете другую перестановку для заданной вершины графа (~строки столбца матрицы).

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