Дано:Найти число матричных групп
Две матрицы считаются эквивалентными, если одна может быть получена от другого путем замены строк и столбцов. Матрицы, эквивалентные, могут быть сгруппированы вместе. Как найти число таких групп?
Это типичная проблема polya theorem. Сначала вы должны изучить его и связанные с ним концепции из Википедии, например, перестановки, циклов и группы.
Скажем, количество строк равно N, количество столбцов - M, а максимальное значение может принимать значение V. Существует (N + M)! перестановки в группе и цвета V, которые мы можем использовать.
Простое решение будет перечислить всю возможную перестановку строк и перестановку столбцов. Тогда c (g) можно вычислить c (перестановка строк) * c (перестановка столбцов). Это алгоритм O ((N + M)!).
Усовершенствованное решение требует некоторого трюка. Вы можете подсчитать количество перестановок строк, которые имеют точно циклы c_row, где 1 < = c_row < = N, и аналогично для столбцов. Затем вы можете перечислить все пары (c_row, c_column) и суммировать результат. Это был бы алгоритм O (N^2 + M^2 + NM) с правильной реализацией.
В обоих случаях вам нужно будет использовать некоторый класс, например BigInteger, в java, так как ответ будет очень огромным.
Если у меня будет больше времени, и вам понадобится код для демонстрации, я напишу один позже.
Пожалуйста, не пишите код для этого вопроса, который плохо сформулирован и не показывает никаких усилий. Если ОП улучшит вопрос, тогда и только тогда ваш код будет подходящим. И, пожалуйста, не редактируйте и не «корректируйте» вопрос, когда OP не указывает вообще, какая коррекция подходит. –
@RoryDaulton Спасибо за советы. Уверен, что ОП не представила эту проблему самым ясным образом. Однако такого описания на самом деле достаточно, чтобы понять то, что хочет запросить OP, а «исправление» - это предложение издания, которое должно быть рассмотрено ОП. –
Матрицы не имеют очевидного порядка, так что вы подразумеваете под «матрицей максимального значения»? Вы имеете в виду максимально допустимое значение абсолютного значения элемента матрицы? Какими являются элементы: целые положительные числа, целые числа, рациональные, вещественные, сложные, другие? Вам нужен код, который найдет число таких групп или просто номер? Самое главное, какую работу вы проделали до сих пор по этой проблеме? Пожалуйста, покажите свой запрошенный код - вот что это за сайт. Проверьте [FAQ] (http://stackoverflow.com/tour) и [Как спросить] (http://stackoverflow.com/help/how-to-ask). –