Устройство для перебора сочетаний, перестановок и размещений

(51) 4 С Об Е 15/2 АНИЕ ИЗОБРЕТ Н АВТОРС н ех ОСУДАРСТНЕННЫИ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ СВИДЕТЕЛЬСТВУ(71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) В.М.Глушань и М.В.Рыбальченко (53) 681,325. 5(088,8)(56) Авторское свидетельство СССР643883, кл. С 06 Р 7/00, 1977.Авторское свидетельство СССР124319, кл, С 06 Р 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ, ПЕРЕСТАНОВОК И РАЗМЕЩЕНИЙ (57) Изобретение относится к вычислительной технике и позволяет значительно повысить быстродействие при формировании сочетаний и размещений. Устройство содержит генератор 1 так товых импульсов, и узлов 4 вьщелени первой единицы, каждый иэ которых состоит из группы 5 элементов ПИ и группы б элементов И, и - 1 групп 7 элементов ИСКЛ)ОЧА 1 ОЩЕЕ ИЛИ и п элеме тов И-ИЛИ 8, выходы 9. В режиме пер бора перестановок сигналы снимаются с выходов блока 2 формирования пере становок,в режиме перебора сочетани сигналы снимаются с выходов блока 3 формирования сочетаний,в режиме пер бора размещений сигналы снимаются с выходов 9, Блоком 3 выбирается соче тание элементов И-ИЛИ 8, а блок 2 осуществляет все перестановки очере ности появления импульсов ка выхода выбранных элементов И-ИЛИ 8. 1 ил.Изобретение относится к вычислительной технике и может быть использовано в специализированньх вычислительных устройствах, предназначенных для повышения эффективности систем автоматизированного проектирования при решении задач конструирования радиоэлектронной и вычислительной аппаратуры. 1 ОЦелью изобретения является повышение быстродействия устройства при формировании сочетаний и размещений.На чертеже приведена структурная схема устройства,цля перебора сочетд-15 ний, перестановок и размещений для и=4.Устройство содержит генератор 1 тактовых импульсов, блок 2 формирования перестановок, бпок 3 формирования сочетаний, и узлов 4 выделения первой единицы, каждый иэ которых состоит из группы 5 элементов ИЛИ и группы б элементов И, игрупп 7 элементов ИСКЛ 1 ОЧЛ 1 ОЩЕЕ ИЛИ и и элементов И-ИЛИ 8, выходы 9.Принцип работы устройства состоит в следующем.В режиме перебора перестановок сигналы снимаются с выходов блока 2 формирования перестановок. При этом очередность появления импульса в пределах каждой серии иэ и тактовых импульсов на выходах блока 2 определяет каждую новую перестановку. Так при Формировании перестановок иэ 3-х элементов каждая серия из 3"х тактовых импульсов формирует последовательность импульсов на выходах блока 2 в таком виде: 123; 23; 2,3,1;40 3,1,2; 1,3,2, т.е приведенные последовательности означают что в первой по-ледовательности первый импульс появляется на первом выходе, второй - на втором и третий - на третьем, во45 второй последовательности первый импульс появляется на втором выходе, второй - на первом и третий - на третьем и т.п.В режиме перебора сочетаний сигналы снимаются с выхода блока 3. При этом перебор сочетаний из и по щ означает, что перебираются такие всевозможные комбинации, в которых на ш выходах, блока 3 будут 1", а на и-ш выходах - "0". Так, всевозможны ми сочетаниями из 4 по 2 будут следующие комбинации: 1100, 1010, 0110,1001, 01 0,. 0011. В режиз переб,рд рдзмеегнй устройств рдботдс г следующимбрдзом.Сигндлы в этом случде снимд)птся с выходов 9, Влоком 3 Формирования сочетаний выбирается сочетание элементов 1-ЮИ 8, а блок 2 Формирования перестановок осуществляет все перестдновки очередности появления импульсов нд выходах выбранных элементов И-И.И 8. Например, формирование размещений из 4 по 3 осуществляется следующим образом, 1 редложим, что в блоке 3 здфиксировапд такая комбинация единичных сигналов нд его выходах - 101, Первый узел 4 выделения первой единицы и все последующие узлы 4 совместно с соединенными с ними группами 7 элементов ИСК.ПОЧЛОЕЕ ИЛИ осуще твляет расслоение сочетаний, т.е. на выходах соответствующих узлов 4 появляются унитарные коды. Так, для рассматриваемого случая на выходах первого узлаздфиксируется код 1000. Этот код поступает на входы 1-й группы 7 элементов ИСКЛ 1 ОЧЛОЕЕ ИЛИ, на другие входь 1 которых поступает полное сочетание с выходов блока 3. Поэтому через первый элемент ИСКЛОЧЛОЕЕ ИЛИ единичный сигнал не проходит и нд входы второго узла 4 поступает код 0101. Б свою очередь, элементы ИЛИ 5 и 6 второго узла 4 выделяют только перв ую 1 этого код д, д о с т дл т ны епросеивают . Поэтому на выходах второго узла 4 появляется код 0100. Этот код и код 0101 с выходов элемейтов ИСКПОЧЛОЩЕГ ИЛИпервой группы поступают на входы элементов ИСКЛОЧЛ 1 ОЩЕЕ ИЛИ 2-й группы, Поэтому на выходе 3-го узла 4 появляется код 0001. На выходах 4-го узла 4 формируется нулевой код 0000. Таким образом, единичные сигналы присутствуют на 2-м входе первого элемента И-ИЛ 1, на 4-м входе второго элемента И-И 1 И и на б-м входе четвертого элемента И-ИЛИ. Последовательность перестановок, формируемая на выходах блока 2 в виде очередности появления импульсов в каждой серии из 3-х импульсов, проходит на выходы 1-го, 2-го и 4-го элементов И-ИЛИ, Эта последовдтельность имеет вид: 1,2,4; 2,1,4; ,41; 4,2, 1; 1,4,2. После перебора всех шести перестановок при сочетании 1101 с вьгхода блока 2 на блок 3 поступает сигнал, по которому в нем формирует1388887 ся сочетание 1011. Поэтому в слудующем цикле перебора перестановок единичные сигналы в соответствующемпорядке появляются на выходах 1-го,3-го и 4-го элементов И-ИЛИ, Так происходит до тех пор, пока не переберутся все размещения и на выходе блока 3 не появится сигнал окончания перебора. Формула изобретения Составитель О.БерезиковаТехред М.Ходанич Корректор Г,Решетник Редактор Е.Копча Заказ 1582/51 Тираж 704 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 Устройство для.перебора сочетаний, перестановок и размещений, содержащее блок формирования перестановок и п групп элементов И, причем тактовый вход устройства соединен с тактовым входом блока формирования перестановок, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия при формировании сочетаний и размещений, оно содержит блок формирования сочетаний, и групп элементов ИЛИ (п - число элементов перебора), пгрупп элементов ИСКЛ 10 ЧАЮЩЕЕ ИЛИ и п элементов И-ИЛИ, причем выход признака окончания формирования перестановок блока Формирования перестановок, соединен с входом запуска блока формирования сочетаний, выход признака окончания формирования сочетаний которого является одноименным выходом устройства, выходы размещений которого соединены с выходами элементов И-.ИЛИ, (2 К)-е входы которых (К=1, п) соединены с К-м выходом блока формирования перестановок, 2 К-й вход (1-го элемента И-ИЛИ (1= =1, и) соединен с выходом 1-го элемента И К-й группы, выход 1-го элемента 3-й группы (3=1, и) соединен с первым входом -го элемента ИСКЛ 10- ЧАЮЩЕЕ ИЛИ 1-й группы (1=2, и), вто рой вход 1-го элемента ИСКЛЮЧАЮЩЕЕИЛИ р-й группы (р=3, и) соединен с выходом 1-го элемента ИСКЛОЧА 1 ОЩЕЕ ИЛИ предыдущей группы, второй вход 1-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 20 первой группы соединен с 1-мвыходом блока формирования сочетаний и с соответствующими входами элементов ИЛИ первой группы и элементов И первой группы, выход элемен та ИСКЛОЧА 10 ЩЕЕ ИЛИ 1 - й группы соеди.ен с соответствующими входами элементов ИЛИ и первыми входами элементов И 1 - й группы, вторые входы кото - рых соединены с выходами элементов 30 ИЛИ 1-й группы.