Генератор перестановок

союз соВетскихСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 1674151 5)5 6 06 Г 15 ОПИСАНИЕ ИЗОБРЕТЕН нсти ГОСУДАРСТВЕ ННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР К АВТОРСКОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство СССРМ 922755, кл. 0 06 Е 15/20, 1981,Авторское свидетельство СССРМ 1190388, кл. 6 06 Р 15/20, 1984.(54) ГЕНЕРАТОР ПЕРЕСТАНОВОК (57) Изобретение относится к области авто. матики и вычислительной техники и может быть использовано для решения задач автоматизированного конструирования радиоэлектронной и вычислительной аппаратуры. Цель изобретения - повышение быстродействия генератора. Генератор содержит счетчик 3, триггер 11, элементы И 6, 8, 7, элемент 4 задержки, одновибратор 5, блоки 21 - 25 формирования последовательных кодов сочетаний, Введение блоков формирования последовательных кодов сочетаний позволяет исключить перебор повторяющихся перестановок элементов. 1 з.п. ф-лы, 2 ил.Изобретение относится к автоматике и вычислительной технике и может быть использовано для решения задач автоматизированного конструирования радиоэлектронной и вычислительной аппаратуры,Цель изобретения является повышение быстродействия генератора.На фиг, 1 представлена функциональ,ная схема генератора (и = 5), на фиг. 2 - функциональная схема блока формирования последовательных кодов сочетаний,Генератор содержит тактовый вход 1, блоки 21-2 формирования последовательных кодов сочетаний, счетчик 3, элемент задержки 4, одновибратор 5, элементы И 6, 7, 8, выход 9 окончания работы генератора, информационные выходы 10, триггер 11, вход 12 начальной установки,Блок 2 формирования последовательных кодов сочетаний содержит элемент задержки 13, регистр 14, узел 15 формирования параллельных кодов сочетаний, элементы И 16, регистр 17, регистр сдвига 18, элементы И 19, 20, 21, ИЛИ 22.Принцип работы устройства состоит в следующем,Пусть и - число переставляемых элементов (разрядность перестановки),= 12, , и - индекс элементов перестановки, ги - число элементов с индексом в перестановке. Тогдапричем итк =- 0 означает отсутствие элемента с индексом К, итк1наличие повторяющихся элементов.В изобретении используется ускоренный алгоритм перестановок, исключающий перестановки повторяющихся элементов,Это достигается перебором сочетанийп 1Си, указывающих позиции повторяющихся элементов в перестановке из и элементов, Можно положитьй 1= ий+ = и - пц1=1Последовательность сочетаний по каждому в формируется в устройстве соответствующим блоком 2, Сочетание представляется Ц-разрядным двоичным кодом, пц разрядов которого имеют единичное значение и определяют позиции элементов сочетания. Код начального сочетания содержит единицы в ги левых позициях из Мь код последнего сочетания - в в; правых позициях из Ц, что используется как признак окончания перебора, Так как все блоки 2 имеют разрядность и, то и - М правых неиспользуемых разрядов должны быть заполнены единицами,Рассмотрим алгоритм работы устройства при и = 6, в 1 = 3, гиг =- 1, гпз = 2, Из5 сказанного выше следует, что в работе алгоритма будут участвовать три блока формирования сочетаний (21, 2 г, 2 з) из шести (нафиг, 1 представлено только пять блоков 2;).зСоответственно, К 1 = 6, Си 1 = С 6 = 20;п 1 гюг=6 - 3=3, Смг =С з=3;зИз = 6 - (3 + 1) = 2, Сиз = Сг = 1.Общее число неповторяющихся перестановок из шести элементов при указанных условиях оказывается равнымС 6 СзС г=20 3 1=60,Формирование перестановки осуществляется следующим образом.Просматриваем первый разряд первогосочетания (блок 21), Если он содержит "1", тов первую позицию перестановки помещаемэлемент с номером 1, если содержит "0", топереходим к первому разряду второго сочетания (блок 2 г), Если он содержит "1", то впервую позицию перестановки помещаемэлемент с номером 2, если содержит "0", топереходим к первому разряду третьего сочетания й т.д, Вторая позиция перестановкизаполняется аналогичным образом, но приэтом из просмотра исключаются ранее просмотренные разряды всех сочетаний при заполнении первой позиции перестановки, ит,д. Исходную перестановку следует записать в таком виде1 1 1 2 3 3Затем блоком 21 формируется новое сочетание, а второй и третий блоки сохраняют40 прежние состояния. Получение нового сочетания блоком 2 г происходит лишь после перебора всех сочетаний первым блоком,Получение нового сочетания в блоке 2 з возможно лишь после перебора всех сочетаний45 первым и вторым блоками, и т.д.Таким образом, двадцати первым сочетаниям блока 2 и неизменным (исходным)сочетаниям второго и третьего блоков будутсоответствовать перестановки (в левом50столбце - сочетания, в правом - перестановки):1,111000 1112332,110100 1121333,101100 1211334011100 2111335.110010 1123136.101010 1213137011010 2113138.100110 1231139010110 213113. 11.110001 11233112.1 0 1 0 0 1 1 2 1 3 3 113011001 21133114.100101 123131 515010101 21313116001101 23113117.100011 12331118010011 21331119.001011 231344 1020.0 0 0 1 1 1 2 3 3 1 1 1.При появлении единичной комбинациив правых разрядах первого сочетания дается разрешение на формирование новогосочетания в блоке 2 г и восстановление исходного состояния в первом блоке. При получении 21-й перестановки в блоках 21, 2 г, 2 збудут установлены такие коды:1.111000 2010 3,11,а сама перестановка будет иметь вид - 1 1 1 2032 3.Следующие 20 перестановок формируются аналогично первым 20-ти, Приполучении 41-й перестановки будут зафиксированы коды сочетаний: 251.111000 2.001 3.11,а перестановка будет иметь вид - 1 1 1 3 32. На 60-й перестановке будут зафиксированы коды сочетаний:1,000111 2,001 3.11, 30а сама перестановка будет такой: 3 3 2 1 1 1.Появление всех единиц в правых разрядах сочетаний по всем блокам (21, 2 г, 2 з)свидетельствует об окончании работы алгоритма. Приведенный алгоритм позволяет 35получить перебор всех возможных перестановок с любым количеством повторяющихся элементов без повторяющихсяперестановок в последовательности,Формирование перестановок устройством осуществляется в последовательновременной форме. Это значит, чтопоследовательность появления единиц навыходах 10 устройства определяет позицииэлементов, а номер элемента определяется 45номером выхода устройства, на котором появляется единичный сигнал.Получение новой перестановки состоитиз двух этапов; формирование новых внутренних состояний блоков 2 и передача их 50через регистры сдвига 18 на выходы 10 устройства. При этом формирование новыхвнутренних состояний блоков 2 осуществляется за один такт, а передача состояний навыходы 10 устройства через регистры 18 за 55и тактов.При поступлении тактовых импульсовна входы регистров 18 информация в нихсдвигается влево, причем появление единицы на первом разряде одного регистров 18 запрещает поступление тактовых импульсов на все остальные регистры 18, стоящие правее этого регистра (фиг. 1), Записывая единицы в правые разряды любого из блоков 2 до начала его работы, можно изменять количество его разрядов, участвующих в работе. В этом случае единицы в правых разрядах будут фиктивными, не участвующими в сочетаниях, и их попадание на входы сдвиговых регистров 18 следует исключить. Это осуществляется с помощью регистров 17. В нижние разряды этих регистров записываются нулевые потенциалы, количество которых равно количеству единиц, установленных в правые разряды соответствующего блока 2, Поступая на вторые входы элементов И 16, они запрещают прохождение через них информации. Модуль счетчика 3 равен числу элементов с учетом повторений), участвующих в перестановках.Работу устройства рассмотрим на примере 5-ти переставляемых элементов, два из которых имеют номер 1, До начала работы устройства нужно установить разрядность кодов сочетаний и записать в них соответстуующую информацию. Блок 21 будет формировать сочетания из множества С 5 = 10, поэтому в первый регисто 14 нужно гзаписать код 11000. Второй блок будет формировать сочетания из множества Сз = 3, поэтому число его разрядов нужно уменьшить с 5 до З-х, записывая две единицы в его правые разряды, Во второй регистр 14 в результате должен быть записан код 10011. Третий блок будет формировать сочетания из множества Сг = 2, а число его разрядов нужно уменьшить с 5 до 2-х путем записи трех "1" в его правые разряды. Поэтому в третий регистр 14 нужно записать код 10111. Четвертый блок должен формировать сочетания из множества С 1 = 1, а число1его разрядов нужно уменьшить с 5 до 1, Поэтому в четвертый блок нужно записать код 11111. Так как элемент с номером 5 не используется в перестановках, то в пятый блок следует записать все "1", т.е. в пятый регистр 14 нужно записать код 11111. В нижние разряды регистров 17 записываются нули, количество которых равно количеству единиц, записанных в правые разряды регистров 14, Поэтому в первый регистр 17 записывается код 11111, во второй регистр 17 записывается код 11100, в третий. - 11000, в четвертый - 10000, в пятый - 00000. Триггер 11 путем подачи на вход 12 единичного сигнала устанавливается в единичное сОстояние.Первый тактовый импульс, поступая с тактового входа 1 устройства на счетчик 3, вызывает появление на его выходе единич20 25 30 40 45 50 ного сигнала, которцй через открытый элемент И 19, элементы ИЛИ 22 и элементы задержки 13 всех блоков 2 поступает и вызывает запись в них информации с регистров 14. В (1 - 5)-м блоках 2 будут записаны соответствено коды: 11000; 10011; 10111;11111;11111, Крометого, задержанный пер-. вый тактовый импульс, пройдя элемент задержки 4, сбросит триггер 11 и, поступая на вход "Запись" регистров сдвига 18 всех блоков 2, переписывает в них информацию, поступающую через элементы И 16. Так в регистр 18 первого блока 2 будет записан код 11000, в регистр 18 второго блока 2 - код 10000, в регистр 18 третьего блока 2 - код 10000, в регистр 18 четверого блока 2 - код 10000, а в регистр.18 пятого блока 2 - код 00000. Единичный сигнал с последовательного выхода регистра 18 блока 21 (первая позиция сочетания) проходит через первый элемент И 8 на выход 10 устройства, что соответствует появленгво в первой позиции перестановки элемента с номером один, Этим же сигналом запрещается прохождение информации через другие элементы И 8.Второй тактовый импульс, отформированный одновибратором 5,по амплитуде и длительности, поступит через первый элемент И б на сдвигающий вход регистра 18 в блоке 21. Остальные элементы И б закрыты единичным сигналом с информационного выхода блока 21 (первая позиция сочетания), В результате сдвига в регистре 18 на информационном выходе блока 21 появится единица, соответствующая второй позиции сочетания, а на выходе 10 первого элемента И 8 - сигнал, соответствующий элементу с номером 1 на второй позиции перестановки,Третий тактовый импульс. вызовет сдвиг только в первом регистре 18 и появление нуля на информационном выходе блока 2 ъ Состояние остальных блоков 2 не изменится. Теперь старшей окажется единица на информационном выходе блока 22 (первая позиция сочетания), и сигнал появится на выходе 10 второго элемента И 8 - элемент с номером 2 на третьей позиции перестановки.Четвертый тактовый импульс вызовет сдвиг в блоках 21, 22 (открыты первый и второй элементы И б), и т,д. На шестом такте появигся сигнал переполнения счетчика 3, который, пройдя через элемент И 20 на синхронизирующий вход узла 15 в блоке 21, вызовет перехоц к новому сочетанию, Через время, равное задержке на элементе 4, новое сочетание перег 1 ишется в регистр 18. Состояние остальных блоков 2 остается неизменным,До перехода к последнему сочетанию в блоке 21 работа устройства выполняется аналогично. При обработке последнего сочетания на выходе узла 15 появляется сигнал окончания перебора, запирающий элемент И 20 и отпирающий И 21, Очередной сигнал переполнения счетчика 3 проходит через элементы И 21, ИЛИ 22, блока 21 и через элемент И 20 блока 22 на вход синхронизации узла 15, вызывая переход к новому сочетанию в блоке 22.Через время, равное задержке элемента И 13, в блоке 21 восстанавливается начальный код сочетания, хранимый регистром 14,Аналогично на последующих этапах подключаются к работе остальные блоки 2,Сигналы окончания работы блоков 2 объединяются элементом И 7 в сигнал окончания работы устройства на выходе 9,Формула изобретения 1, Генератор перестановок, содержащий счетчик, триггер, элемент задержки, две группы по и эгементов И (и - число переставляемых элементов), о т л и ч а ющ и й с я тем, что, с целью повышения быстродействия, он содержит п блоков формирования последовательных кодов сочетаний, одновибратор и элемент И, причем счетный вход счетчика и вход одновибратора объединены с тактовым входом генератора, выход переполнения счетчика соединен с входом элемента задержки и входом синхронизации перебора сочетаний первого блока формирования последовательных кодов сочетаний, выход элемента задержки соединен с.нулевым входомтриггера и входом синхронизации начальной установки разрядов последовательного кода каждого блока формирования последовательных кодов сочетаний, выхододновибратора соединен с прямым входом каждого элемента И первой группы, выход 1-го ( = 1, и) элемента И первой группы соединен со сдвигающим входом 1-го блока формирования последовательных кодов сочетаний, информационный выход -го ) = 1, 1, и - 1) блока формирования последовательных кодов сочетаний соединен с )-м инверсным входом К-го (К =) + 1, и) элемента И первой и второй групп, информационный выход 1-го блока формирования последовательных кодов сочетаний соединен с прямым входом -го элемента И второй группы, выходы элементов И второй группы являются информационными выходами генератора, единичный вход триггера являетс.я входом начальной установки генератора, выход триггера соединен с входами начальной установки всех блоков формирования последовательных кодов сочетаний, выход начала перебора сочетаний )-го блока формирования последовательных кодов сочетаний соединен с входом синхронизации перебора сочетаний ) + 1)-го блока формирования последовательных кодов сочетаний, выход окончания перебора сочетаний 1-го блока формирования последовательных кодов сочетаний соединен с 1-м входом элемента И, выход элемента И является выхоом окончания работы генератора,2, Генератор поп. 1, отлича ющийс я тем, что каждый блок формирования последовательных кодов сочетаний содержит узел формирования параллельных кодов сочетаний, два регистра, регистр сдвига, группу элементов И, три элемента И, элемент ИЛИ, элемент задержки, причем входы первого и второго регистров являются входами задания числа элементов в сочетании и числа разрядов в коде сочетания соответствующего блока формирования последовательных кодов сочетаний, выход первого регистра соединен с информационным входом узла формирования параллельных кодов сочетаний, информационные выходы которого и второго регистра поразрядно через соответствующие элементы И группы подключены к информационному параллельному входу регистра сдвига, последовательный выход которого является информационным выходом соответствующего блока формирования последовательных кодов сочетаний, первые входы первого и второго элементов И, а также прямой вход третьего элемента И объединены и 5 являются входом синхронизации перебора сочетаний блока формирования последовательных кодов сочетаний, выходы первого и второго элементов И соединены с входами элемента ИЛИ, выход которого яв ляется выходом начала перебора сочетанийблока и через соответствующий элемент задержки подключен к управляющему входу записи узла формирования параллельных кодов сочетаний, выход третьего элемента 15 И соединен с синхронизирующим входомузла формирования параллельных кодов со. четаний в том жеблоке формирования последовательных кодов сочетаний, выход окончания перебора сочетаний узла фор мирования параллельных кодов сочетанийявляется выходом окончания перебора сочетаний блока формирования последовательных кодов сочетаний и соединен с вторым входом второго элемента И и инвер сным входом третьего элемента И в том жеблоке формирования последовательных кодов сочетаний, управляющий вход записи и сдвигающий вход регистра сдвига являются входом синхронизации начальной уста новки разрядов кода сочетания и сдвигающим входом соответствующего блока формирования последовательных кодов со чета ни й.1674151 Составитель В. Байковредактор К, Крупкина Техред М.Моргентал Коррект ороль роизводственно издательский комбинат "Патенг", г род, ул.Гагари каз 2924 Тираж 387 ВНИИПИ Государственного комитета 113035, Москва, Жпо изоб -35, Рау Подписноеениям и открытиям при ГКкая наб., 4/5