Вычисление порядка группы инерции булевой функции

[bgm123]

Немного теории:
Группа $S_6$ перестановок переменных состоит из $6!$ преобразований вида:
$ (x_1 \to x_{i1}, ... ,x_6 \to x_{i6}) $. Группой инерции булевой функции $f$ относительно группы $S_6$ называют множество всех подстановок, сохраняющих функцию.

Теперь задача:
Дана булева функция $ f = (x1 + x4) * (x2 + x3) + x5*x6$. Требуется вычислить порядок группы инерции этой функции в $S_6$.

Я так понимаю, чтобы не перебирать все варианты, нужно использовать некоторые эвристики для отбрасывания. Вопрос: как это делается? Какие эвристики можно использовать? Может быть есть другое решение?

-- 19.03.2013, 17:33 --

Правильный ответ 16

-- 19.03.2013, 18:20 --

Я нашёл способ проверки всех допустимых подстановок в которых длина цикла не больше 1. Например, для проверки того, можно ли поменять x3 и x4 местами достаточно проверить, чтобы подфункции функции f соотв. наборам x3 = 0, x4 = 1 и x4 = 0, x3 = 1 были равны. Возникают некоторые трудности, когда в подстановке присутствуют циклы, длины > 1. Например, может оказаться, что одну из пар переменных (x1, x3), (x2, x4) нельзя переставлять, но обе пары в подстановке, входящей в группу инерции могут быть. Как исключить такие подстановки?

[bgm123]

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

[Deggial]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
Причина переноса: формулы не полностью оформлены ТеХом

Оформите формулы ТеХом полностью и правильно. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.