Устройство для перебора сочетаний

, 100 ц 11061 САНИЕ СКОМУ СВ ИЗОБРЕТЕНИЯ ТЕЛЬСТ И АВТО ото- ерво- оеди 4 ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(56) 1. Авторское свидетельство СССР М 634285, кл, й 06 Г 15/32, 1975,2. Авторское свидетельство СССР % 525948, кл, б 06 Р 7/00, 1973.3, Авторское свидетельство СССР И 0 374606, кл, Я 06 Р 15/32, 1970 (прототип ).(54) (57) УСТРОЙ).,ТВО,ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ, содержащее первый рас. пределитель импульсов, генератор такто вых импульсов, четыре группы элементов И; о т л и ч а ю ш е е с я тем, что, с целью упрощения, оно содержит два накапливающих сумматора, второй распределитель импульсов, два триггера, группу элементов ИЛИ, три элемента НЕ, три элемента И, два элемента ИЛИ, формирователь импульсов, причем выход генератора тактовых импульсов соединен с информационным входом первого распределителя импульсов и первыми входами первого и второго элементов И, выходы первого распределителя импульсов соединены соответственно с первыми входами элементов И первой и второй групп; вторые входы которых соединены соответственно с выходами разрядов первого и второго накап-ливающих сумматоров, входы разрядов которых соединены соответственно с выхода ми элементов И второй группы и элемен- . тов ИЛИ первой группы, первые входы элементов ИЛИ первой группы соединены соответственно с выходами элементов И третьей группы и соответствующими входами первого элемента ИЛИ, выход рого соединен с единичным входом го триггера, нулевой вход которого ен с последним выходом первого распределителя импульсов, выход перва о триггера соединен с первымвходом третьего лемента И, второй вход которого соедиен с входом первого элемента НЕ, вторым входом второго элемента И и выходом второго триггера, нулевой и единичный входы которого соединены соответсъвенно с последним выходом первого ра пределителя импульсов и выходом первого элемента И, второй вход которого соединен с выходом второго элемента НЕ,вход которого соединен с выходам второго элемента ИЛИ и первыми входами элементов И третьей группы, вторые входыкоторых соединены соответственно с вы-..ходами второго распределителя, вход которого соединен с выходом второго элемента И, входы сброса первого и второраспределителей импульсов соединены свыходом формирователя импульсов, входкоторого соединен с выходом третьегоэлемента И, третьими входами элементоИ второй группы и входом третьего элемента НЕ, выход которого соединен с третьими входами элементов И первой третьей групп, вторые входы элементовИЛИ первой группы соединены соответственно с выходами элементов И четвертойгруппы первые входы которых соединенысоответственно с выходами элементов Ичетвертой группы: первые входы которыхсоединены соответственно с выходамиэлементов И первой группы и соответствующими входами второго элемента ИЛИвторые входы элементов И четвертойгруппы соединены с выходом первогоэлемента НЕ,780 2пульсов, генератор тактовых импульсов, четыре группы элементов И, содержит два накапливакяцих сумматора, второй рас пределитель импульсов, два триггера, группу элементов ИЛИ, три элемента НЕ, три элемента И, два элемента ИЛИ, формирователь импульсов, причем выход генератора тактовых импульсов соединен с информационным входом первого распределителя импульсов и первыми входами первого и второго элементов И, выходы первого распределителя импульсов соединены соответственно с первыми входами элементов И пЕрвой и второй групп, вторые входы которых соединены соответственно с выходами разрядов первого и вто. рого накапливающих сумматоров, входы разрядов которых соединены соответственно с выходами элементов И второй группы и элементов ИЛИ первой группы, первые входы элементов ИЛИ первой груп. пы соединены соответственно с выходами элементов И третьей группы и соответствующими входами первого элементов ЮЛИ, выход которого соединен с единичным входом первого, триггера, нулевой вход кото рого соединен с последним выходом первого распределителя импульсов, выход первого триггера соединен с первым входом третьего элемента И, второй вход которого соединен с входом первого элемента НЕ, вторым входом второго элемента И и выходом второго триггера, нулевой и единичный входы которого соединены соответственно с последним,выходом первого распределителя импульсов и выходом первого элемента И, второй вход которого соединен с выходом второго элемента НЕ, вход которого соединен с выходом второго элемента ИЛИ и первыми входами элементов И третьей группы, вторые входы которых соединены соответственно с выходами второго распределителя, вход которого соединен с выходом второго элемента И, входы сброса первого и второо распределителей импульсов 1 соединены с выходом формирователя импульсов, вход которой соединен с выходом третьего элемента И, третьими входами элементов И второй группы и вхо- . дом третьего элемента НЕ, выход которого соединен с третьими входами элементов И первой и третьей группы, вторые входы элементов ИЛИ первой группы соединены соответственно с выходами элементов И четвертой группы, первые входы которых соединены соответственно с выходами элементов И первой группы и соответствукщими входами второго эле 1 1008Изобретение относится к вычислительной технике и может быть использованов специализированных моделируквцих уст-.ройствах для решения задач синтеза сетей связи, транспортных сетей, вычисления характеристик графов.Известно устройство для перебора сочетаний, содержащее регистры сдвига,распределитель импульсов, дешифратор,триггер, элементы И, элементы задержки,1 фсчетчик1 .Недостатками данного устройства является сложность и низкое быстродействие.Известно устройство для перебора со- фчетаний, содержащее распределитель им- .пульсов, генератор тактовых импульсовблок .памяти, два блока перестановок,триггер, элементы И, элементы задержки 2,20Недостатком данного устройства является сложность.Наиболее близким к предлагаемому является устройство для перебора сочетаной, содержащее распределитель импульсов 25генератор тактовых импульсов, И счетчиков, (И) группу элементов И, (й+2) элемента ИЛИ, И элементов запрета 2(И)элементов задержки, причем выход переноса 1 -го счетчика, кроме последнего, Зфчерез 1 -й элемент запрета и первый(1+1)-й элемент ИЛИ соединены с входом (1+1)-го счетчика, а также с соответствующим входом распределителя импульсов и через второй-й элемент ИЛИи первый -й элемент задержки с первыми входами элементов И 1 -й группы,вторые входы которых соединены соответственно с выходами . 1 -го счетчика, авыходы - с входами (1+1)-го счетчика,выход первого 1-го элемента задержкичерез второй 1-й элемент задержки ипервый 1 -й элемент ИЛИ соединены свходом 1 -го счетчика, а через второй(1-1)-й элемент ИЛИ - входом перво 43го (-1)-го элемента задержки, выходпереноса последнего счетчика соединенс входом установки распределителя импульсов, вход первого счетчика черезпервый элемент запрета и первый элементИЛИ подклЬчен к выходу генератора тактовых импул.ьсов (1=1-И) 31,Недостатком данного устройства является его сложность при больших М и МЦель изобретения - упрощение устройства для перебора сочетаний,Поставленная цель достигается тем,что устройство для перебора сочетаний,содержащее первый распределитель им750 .4 3 1008мента ИЛИ, втррые входы элементов Ичетвертой группы соединены с выходомпервого элемента НЕ.На чертеже представлена схема устройства для перебора сочетаний,Устройство для перебора сочетаний содержит сумматор 1, группу элементов И2, группу элементов И 3, группу элементов ИЛИ 4, сумматор 5, элемент ИЛИ 6,элемент НЕ 7, элемент И 8, триггер 9, 16распределитель 10 импульсовгенератор11 тактовых импульсов, элемент И 12,распределитель 13 импульсов, элементИЛИ 14, триггер 15, элемент И 16,элемент НЕ 17, группу элементов И 18, 15формирователь импульсов 19, элементНЕ 20 и элементы И 21,Перебор сочетаний иэ М по Ч производится следующим образом,Исходным сочетанием является со 26четание,в котором Й единиц записано вправых (младших) разрядах, Йпя получения очередного сочетания подсчитывается число Ь подряд стоящих нулей вмладших разрядах, начиная с нулевого до 25первой единиць 1 и число .К подряд стоящих единиц после нулей справа до первого нуля в сташеу разряде, Вычисляется число д: 2 +2 -1, где = К, инаходится сумма ДФЬ,где Ап- преды - 30дущее сочетание, тем . самым определяется очередное сочетание. Перебор про -дапжается до появления подряд единиц влевых (старших) разрядах.Рассмотрим на прмере перебор сочетаний из "5" по 2". Число сочетанийбудетСс= др-р=о Исходное сочетание А и 00011, здесь40 Ь О, К=2, следовательно, Ь = 2 или в двоичной системе 00010". суммируя ис- . ходную комбинацию и Ь получаем очередную комбинацию "00101",Д, =ОООО 1 Д = ОО 110Ь =ООО 11 А = 01001454 = 00001 Д = О 1 О 1 О, Ь"- 00010 Д 6 =0110066" 00101Д 1 = 10001Д =ОООО 1 А 9 = 10010Ьйф 00010 А 9 = 10100Ь= ОО 1 ОО А = 11 ОООТащм образом, псаучены все десять -очетаний.Для перебора всех сочетаний из М поМ,где Й изменяется от (М) до 1, наЯ до взять исходную комбинацию у которой во всех разрядах записаны единицы, Возьмем М"- М=5, т.е. А=11111, Ь ф 10000 Д =01111. Йалее перебор осуществляется как в вышеописанном примере, т.е. перебор из "5 по,"4". После окончания3 перебора иэ ф 5" по 4" получается комбинация "11110. Для этой комбинации Ь =01001 и новое сочетание 11110 + 01001 = 00111. Далее осуществляется перебор из 5 по 3 и т. д. до поаучения комбинации 10000. Для нее Ь= =10000 .и следующее сочетание 10000+ +10000=00000, т.е. наличие во всех разрядах нулей. говорит о конце перебора всех сочетаний.Устройство рля перебора сочетаний работает следующим образом.В исходном состоянии триггеры .9 и 15 находятся в нулевом состоянии,. в пер-вом сумматоре записано исходное соче тание, у которого Я единиц записаны в младших, крайних правых разрядах. Так как триггеры 9 и 15 находятся в нулевом состоянии, то на выходе элемента И 16 нулевой потенциал, следовательно, нулевой потенциал и на первых входах элементов И 18, на выходе элемента НЕ 17 единичный потенциал, который приложен к первым. входам элементов И 2 и 3, На выходе элемента НЕ 20 единичный потенциал, который подается на все вторые входы элементов И 21, От распределителя 10 импульсов последователь но подаются импульсы на третьивходы, 1 элементов И 2, .вторые входы которых :,подключены к нулевым выходам разрядов сумматора 1, где записано исходное со- четание. Если в некоторых младших разрядах, начиная с нулевого, последовательно было записано Ц, нулей, то единицы (так как выходы инверсные) через элементы И 21, ИЛИ 4 перепишутся в соответствующие младшие разряды сумматора.5. При нахождении первой единицы посленулей в сумматоре 1 в соответствующий разряд сумматора 5 запишется нуль. Таким образом в сумматоре 5 будет записано число 1 4 что равно 2 ф Нулевой потенци с выхода соответствующего элемента И 2 подается на вход элемента ИЛИ 6, на выходе которого бу дет нулевой потенциал, на выходе эле мента НЕ 7 - единичный потенциал. Этот единичный импульс, воздействуя на единичный вход триггера 9, переводит его в единичное состояние, тем самым на первомвходе элемента И 12 будет единичный потенциал и через элемент станут проходить тактовые импульсы от генера-. тора импульсов, которые запускают распределитель 13 импульсов, Кроме того,5 1008 нв выходе элемента НЕ 20 будет нулевой потенциал, который подается на все вторые входы элемента И 21. Следовательно, информация с сумматора 1 не будет подаваться через элементы И 21 на З сумматор 5, Под воздействием импульсов вырабатььвемых распределителем 10 им- пульсов, будет продолжаться опрос состояний разрядов сумматора 1, Начинается подсчет числа единиц после Ь нулей и 0 вычисление числа 2=2. . Заметим, чток. первая единица у нас использовалась для вычисления. 2 -1, следовательно, число подсчнтываемых единиц будет уже на одну меньше, Твк как используются инверсные выходы разрядов сумматора 1, точерез элемент ИЛИ 6 последовательно во времени т.рч помощи распределителя 13 . импульсов и через элементы И 3, ИЛИ 4 ссстояния разрядов сумматора 1, взя тые с инверсных. выходов будут записываться в сумматор 5, начиная с младшего разряда, тем самым в сумматоре 5 будет происходит суммирование, Допустим после Ь нулей шло К единиц, так 23 как одна единица уже пропущена, то к числу, записанному в сумматор, будет прибавляться число ", после К еди 00 "Ониц в сумматоре 1 отыскивается первый нуль, инвертируется и в сумматор запи- З 0 сывается единица. Следовательно, в сумматоре 5 к чисду (2 -1) прибавляется число Р.-,а это и есть ни что иное как100. О2(, Таким образом, в счмматоре 5 выполняется операция (2 ф+2 -1). При об-наружении первого нуля после К единиц этот инвертированный нуль (т, е, единица) через элемент ИЛИ 14 воздействует на единичный вход триггера 15, Оба триг 750 й.гера 15 и 9 находятся в единичном сос стоянии. На выходе элемента И 16 поя: - вится единичный потенциал, который переводит через формирователь импульсов 19 распределители импульсов 10 и 13 в исходное состояние(закрывает элементы И 2 и 3 и открывает элемент И 18, Импульсы с распределителя 10 импульсов воздействуют на третьи входы элементов И 18 и тем самым информация иэ сумматора 5 подается последовательно, начиная с младшего разряда, на входы сумматора 1, в котором осуществляется сложение содержимого сумматора 5, т,е. велнчины Ь с содержимым сумматора 1, т.е, с предыдущим сочетанием, Таким образом, в сумматоре 1 формируется очередное сочетание. При появлении импульса на последнем выходе распределителя 10 импульсов заканчивается процесс суммирования, Этот импульс переводит триг геры 9 и 1 5 и нулевое состояние и начинается новый цикл вычисления следующего сочетания, Сигналом о переборе всех сочетаний является появление И единиц подряд в старших разрядах сумматора 1, Лля перебора всех сочетаний из М по К где Й меняется от М до 1 необходимо в сумматор. записать исходную комбинацию -",-, Полный перебор эаканчиваетяМ "мпри появлении в сумматоре 1 всех нулей. Данное устройство значительно проще, содержит меньше элементов по сравнению с прототипом, особенно при больших М и й Меньшее количество элементов требуется уже при М = 4 (под типовым элементом понимаем одну интегральную сборку: триггер, элемент И и элемент ИЛИ),