Борис Цирлин
Рассматриваются алгоритмы подсчета последовательных схем.
Введение
Рассмотрим алгоритм подсчета всех не изоморфных друг другу последовательных схем из n
элементов, для чего, в свою очередь, необходимым этапом будет, как раз, построение списков изоморфных, полученных обоими способами, показанными в первой части. Т.е. по вектору возбуждений некоторой последовательной схемы надо построить вектора возбуждений схем, изоморфных данной, полученные, как путем перестановок, так и путем инвертирования.
Получение изоморфных схем путем перестановок
Начнем с самих перестановок, которые, для заданного n, определим, используя готовую программу (обычно она называется permutation), образцы которой имеются интернете. Результат работы такой программы для n = 3 - это список вида:
pertmutation(3) = [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]],
не требует пояснений. Далее построим два двумерных списка - первый - s измененных состояний, в которые преобразуются состояния исходной схемы в результате применения перестановок. При этом первой координатой в s будут номера состояний (или номера компонент вектора C возбуждений), а второй - номера перестановок из permutation. Два состояния схемы, а именно такие, в которых значения всех выходов ее элементов одинаковы и равны 0 или 1 - инвариантны к перестановкам, остальные же легко вычислить, представив состояния исходной схемы в двоичном коде, а затем, изменив веса компонент этого кода в соответствии с выбранной перестановкой, сложить эти модифицированные компоненты.
Второй двумерный список b возбуждений, первой координатой которого теперь будет номер перестановки из permutation, а второй - номер возбужденного элемента. В каждую же ячейку этого списка поместим число, соответствующее возбуждению того же элемента в изоморфной схеме. Т.е. b показывает, как меняется вес возбуждения элемента в зависимости от перестановки. Заметим, что если не возбужден ни один элемент, т. е. компонента вектора возбуждений равна 0, то перестановки этого значения не изменят. Это значит, что начальным элементом каждого вложенного списка в b, будет 0. Значения же остальных - определяются позицией возбужденного элемента в выбранной перестановке, т.е. его индексом в соответствующем вложенном списке permutation. Для решения такой задачи в Питоне удобно использовать метод index(). Единственно, следует учесть, что результат его работы на 1 меньше номера возбужденного элемента, т.к. индексы списков в этом языке нумеруются с 0, а элементы последовательных схем - с 1.
На рисунке приведены списки s и b для n = 3.
Для любой i-й перестановки из permutation, j-й компоненте вектора C возбуждения некоторой последовательной схемы соответствует s[ j ][ i ]-я компонента вектора Np[ i ] возбуждений, для изоморфной схемы. При этом соответствие это взаимно однозначное, что следует хотя бы из того, что в каждом столбце в s нет повторяющихся цифр. Значение этой компоненты определяется с помощью списка b и равно b[ i ][C[ j ]], т.е. имеет место равенство:
Np[ i ][s[ j ][ i ]]=b[ i ][С[ j ]].
Получение изоморфных схем инверсией
Для реализации этого способа получения изоморфных схем достаточно вспомнить (смчасть 1), что для нумерации всех возможных способов инвертирования использовалось кодирование - 1 наличие инверсии переменной в данном варианте и 0 - если переменная не инвертируется. В булевой алгебре именно так определяется операция "исключающее или". Т.е. при j-м способе инвертирования, i-е состояние исходной схемы (номер компоненты C) трансформируется в состояние номер i^j ("исключающее или" i и j) изоморфной схемы с вектором возбуждения Ni[ j], при этом значение возбуждения не измениться, т. е. имеет место равенство:
Ni[ j ][ i^j ]=C[ i ].
Замечания к программной реализации на Питоне
В обоих случаях изоморфизма, использование полученных равенств во вложенных циклах по i и по j определит список всех изоморфных схем, полученных перестановками или инверсиями переменных, из исходной, заданной вектором C возбуждений. Для получения списка всех изоморфных схем для С надо сначала применить один из этих методов, а затем применить второй ко всем схемам, полученным первым. Порядок их применения не влияет на полученный результат, но опыт показал, что использование перестановок первыми несколько ускоряет процесс. Теперь ряд уточнений, необходимых для понимания общей структуры алгоритма.
Первое - получение вектора С возбуждений для любой из N последовательных схем из n элементов, т. е., вычисление С для любого I (0=<I<N).Такие алгоритмы также известны и заключаются в последовательном повторении двух операций: получение остатка от деления чисел I и (n + 1)
C[i]=I%(n + 1)
и уменьшения I делением c округлением вниз на те же (n + 1) -
I=I//(n+1).
Число повторений этих операций определяется числом компонент вектора C, т. е. равно G.
Второе. Пусть программа перебирает номера I последовательных схем по возрастанию - от 0 до N. Когда вычисляется список изоморфных для очередной последовательной схемы, то возможна ситуация, что этот список не уникален, т. е. уже было порожден другой схемой, рассмотренной раньше. Тогда этот список (будем и дальше называть его не уникальным) содержит и ту схему, что была уже рассмотрена, а соответствующий ей номер I (т.е. вектор С возбуждений) меньше текущего. Итак, признаком уникальности списка изоморфных схем является то, что вектор С возбуждений, порождающей его схемы, является минимальным в этом списке. Используя этот признак программа учитывает только уникальные списки изоморфных схем, исключая из рассмотрения все остальные, т.е. избегает дублирования этих списков. изоморфных. Определение минимального члена списка - задача для начального курса любого языка программирования (Питон не является исключением), поэтому рассматриваться не будет. Отметим действенность обсуждаемого признака при любом порядке перебора схем. Это обстоятельство делает возможным применение параллельных вычислений для ускорения работы программы. А предположив перебор номеров I в порядке убывания, можно получить альтернативный признак уникальности: максимальность вектора С возбуждений порождающей схемы для списка изоморфных ей схем.
Чем на более раннем этапе используется признак уникальности списков, тем эффективнее работа программы, поэтому он применяется уже на первом этапе построения списка изоморфных схем, что не исключает необходимости использования его и на втором, результирующем этапе.
Третье. Построенные списки изоморфных схем могут содержать повторяющиеся элементы(см. приведенный первой части пример). Тогда следует подсчитать число различных схем в каждом таком списке. Задача усложняется двухмерностью этих списков - для одномерных Питон предлагает метод, основанный на преобразовании списка (list) во множество (set) - в последнем повторяющиеся элементы исключаются по определению, и получение длины последнего стандартной функцией len(). Для двухмерных списков приходится применять традиционные методы, используя стандартную функцию equal() для выявления факта повторного вхождения каждой схемы в список изоморфных, а на основе этого - подсчитывать число различных схем в списке.
Полученные таким образом данные и являются целью работы программы.
Во-первых, сложив все эти числа, полученные в результате перебора всех допустимых I, получим общее число N последовательных схем из n элементов. Таким образом, достижение этой суммой
указанного предела, может служить условием "досрочного" завершения работы программы.
Во-вторых, подсчитав количество, полученных таким образом, списков изоморфных схем, как раз и определим искомое число различных (не изоморфных) последовательных схем из n элементов.
В-третьих, появляется возможность рассортировать списки изоморфных последовательных схем по длине, что интересно с точки зрения понимания структуры этого феномена.
В заключение отметим, что упомянутая возможность распараллеливания вычислений была использована для реализации программы с помощью инструмента CUDA от компании NDIVIA для языка Питон, который позволил организовать вычисления с использованием графической карты (GPU), дающей существенное ускорение по сравнению с работой только на центральном процессоре (CPU).
На рисунке показаны результаты работы программы для n = 2 и 3, которые не требуют пояснений.
