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

(19) 1) 4 О 06 Г 15/ ПИСАНИЕ ИЗОБРЕТЕНИ 3,. и ВИле 4) УСТРОЙСТВО ДЛЯЙ, РАЗМЕЩЕНИЙ И7) Изобретенией вычислительно ПЕРЕБОРА СОЧЕРЕСТАНОВОКосится к цифроехнике и может ТА на) ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Ленинградский электротехничкий институт им,В,И,Ульянова (Ле(56) Авторское свидетельство СССВ 643883, кл, 6 06 Г 15/20, 1977Авторское свидетельство СССРВ 1124319, кл, 6 06 Г 15/20, 198 быть использовано дл наторских задач, Цел повышение быстродейс ровании сочетаний пу выборок повторяющихс ройство содержит две ров 1 1 ,11 -11 , кот решения комбиизобретения -ия при генерим устранениясочетаний. Уструппы регистутатор 2, со,2 ил. 13632 держащий группы элементов И 3, - 3и элементы ИЛИ 4-4, блок уйравления 5, блок переключателей 6, две группы элементов ИЛИ 71-7 , 9-9, две группы элементов И 8,-8 ,12-12 группу элементов сравнения 11,-11 , информационные входы 10,-10, выходы перестановок 14, -14, счетчик 15, дешифратор 16, элемент ИЛИ 17, регистр 18, генератор 19 тактовых им Изобретение относится к цифровой вычислительной технике и может быть использовано для решения задач комбинаторного характера.Цель изобретения - увеличение бысч тродействия при формировании сочетаний путем устранения выборок повторяющихся сочетаний,Нафиг.1 приведена функциональная схема устройства для перебора сочетаний, размещений и перестановок для случая пяти переставляемых элементов; на фиг.2 - функциональная схема блока управления.Устройство для перебора сочетаний, размещений и перестановок (Фиг,1 и 2) содержат первую группу 1,-1. регистров, коммутатор 2, состоящий из групп 3,-3элементов И и элементов ИЛИ 4 -4 5, блок 5 управления, блок 6 переключателей, первую группу 7, -7 ,элементов ИЛИ, первую группу 8,-8элементов И, вторую группу 9 -9элементов ИЛИ, информационные входы устройства 10, -10, вторую группу регистров 11, -11 , вторую группу 12, - 12 элементов И, группу 13 -13элементов сравнения, выходы 14 -14 перестановок, счетчик 15, дешифратор 16, элемент ИЛИ 17, регистр 18, генератор 19 тактовых импульсов, делитель 20, элементы 21-23 задержки, вход 24 установки начального состояния, выход 25 окончания генерирования, счетчик 26, счетчик 27 и элемент ИЛИ 28, группу 29-29элементов И, группу .30 -30 э элементов ИЛИ, элемент ИЛИ 31, триггеры 32,-32 , элементы 33 и 33запрета, последовательно соединенные регистры 34,-34 сдвига(число разрядов в регистре 34 сдвига равно пяти, а в регистре 34-двумв регистре 34 2 - трем, в регистре 5 34 э - четырем), выходы 351 в 35 ,со .четаний устройства, выход 36. Входы и . выходы блока 5 управления (фиг,2)расположены в строгом соответствиис их расположением на фиг,1; коэффи циенты пересчета счетчиков 26 и 27 -и и (и) соответственно,Описание соединений и генерируемыеперестановки приведены . в табл. 1-4.Устройство для перебора сочетаний,размещений и перестановок может работать в трех режимах: генерированиеперестановок, генерирование размещений и генерирование сечетаний.201, Генерирование перестановок.Для генерирования перестановок повходам 1 О в регистрах 11 записываютсяисходные элементы, например числа 1,25 2,3,4,5, причем запись этих чисел врегистры может производиться в любомпорядке. Для удобства будем считать,что числа записаны в возрастающемпорядке, начиная с верхнего регистра11На .вход 24 подается сигнал уста-,новки в начальное состояние блока 5и счетчиков 15, 26, 27,Первый тактовый импульс с выходаделителя 20 производит перепись элементов, т.е, чисел 1,2,3,4,5, из реЗ 5,гистра 11 в соответствующие регистры1 и одновременнд устанавливает единицу на первом выходе блока 5. Благодаря этому задержанный элементом 21первый тактовый импульс, поступая навходы всех группы 3 -3 элементовмИ коммутатора 2, переписывает числа из регистра 1, в регистр 11, из регистра 1 в регистр 11, из регист 5 ра 1 З в регистр 11, из регистра 1 в регистр 11, а из регистра 1 в регистр 11,. Задержанный элементами 22 и 23 первый тактовый импульс, поступая на второй и третий входы блока 5, никаких изменений не производит. Тактовые импульсы с генератора 19 тактовых импульсов, частота которых в и раз вышее, чем с выхода делителя 20 (и-число элементов в перестановках), поступая на вход счетчика 15,суммируются. Так как выходы счетчика 15 соединены со всеми элементами 13, при поступлении каждого тактового импульса на этот счетчик в одном из элементов 13 сравнения происходит сравнение кодов счетчика 15 и соответствующего регистра 11. На выходе 14 того элемента 13 сравнения, где произошло совпадение, появляется сигнал, кроме того, производится перепись содержимого соответствующего регистра 11 через элементы И 12 и ИЛИ 17 на выходной регистр 18,После этого на выходе делителя 15 го 30 20 появляется второй импульс, который переписывает числа из регистров 11 - 11в регистры 1;1соответственно. Этот же импульс, проходит на вход регистра 34 и появляется на первом выходе блока 5 управлейия. Происходит аналогичное действие, Получаемые В соответствии с этим задержанный пятый импульс с выхода элемента 21 переписывает числа 2,3,4,5,1 из регистра 1,-1 в регистры 11-11 (соответственно 2,1,3,4,5). Этот же импульс, пройдя .через элемент 22 за 50 держки, поступает на второй вход блока 5 и через открытый элемент И 29 и элемент ИЛИ 30 сбрасывает регистр 34, в исходное состояние, а пройдя через элемент 23 задержки, поступает на третий вход блока 5 и через эле 55 перестановки в заданной последовательности представлены в табл,4. 40Пятый импульс с выхода делителя 20 проходит на выход регистра 341 блока 5 и появляется на втором его выходе, переводит в единичное состояние триггер 32 и поступает на вход 45 регистра 34. мент ИЛИ 31 устанавливает в исходноесостояние триггер 32, .Далее аналогичным образом по тактовым импульсам. генератора 19 начинается сравнение чисел в элементах13 -13 сравненияСигнал последовательно. появляется на выходах 144 ф 14 З 14Одновременно посигналам с дешифратора 16 переписываются числа 2, 1,3,4,5 из регистров11 -11 в регистр 18, Таким образом,параллельная форма представленияперестановок в регистрах 11,-11преобразуется в последовательную фор,му в регистре 18 и пространственновременную форму последовательностипоявления сигналов на выходах 14,- 14элементов 1.3, - 13 сравнения.После перебора всех 120 перестановок на выходе 25 регистра 34по-является сигнал окончания работы.2, Генерирование размещений.При генерировании размещений работа не отличается от режима генерирования перестановок, Различие заключается лишь в том, что перед началомработы числа, отличные от нуля, нужно занести не во все регистры 11,а лишь в некоторые. Так, например,при генерировании размещений из 5 по2 в любые два регистра необходимо записать числа, отличные от нуля.Сравнение чисел происходит лишь в техэлементах 13 сравнения, на которыепоступают из регистров 11 не нулевыечисла. Поэтому за каждый цикл пересчета счетчиком 15 тактовых импульсов с генератора 19 сигнал появляется на выходах только двух схем 13сравнения из пяти. Поскольку числа врегистрах 11 в каждом цикле меняются,то к моменту появления сигнала концаработы устройства (на выходИ 25 блока5) перебираются всевозможные комбинации пар элементов 13 сравнения, вкоторых происходит сравнение чисел,и на соответствующих выходах 14 появляются сигналы, Все эти комбинациипар элементов сравнения являются размещениями из 5 по 2, Таким образом,получаем все размещения из 5 по 2 вформе пространственно-временной последовательности появления сигналов на выходах 14 3. Генерирование сочетаний. В режиме генерирования сочетанийинформация снимается с выходов эле13632 32 5ментов И 8,-8. Начальная установкатакая же, как и в режиме генерирования перестановок, Переключателем 6задается число элементов из общегочисла, которые должны участвовать вформировании сочетаний, например,если замкнут первый контакт переключателя, то формируются сочетания из5 по 4 если второй - из 5 по 3 есЭ У10ли третий - из 5 по 2. В табл.4 всесочетания из 5 по 2 обведены тонкойлинией в кружок (1.2, 1.3, 1,4, 1.5,2,3, 2,4, 2.5, 3.4, 3.5, 4.5), авсе сочетания из 5 по 3 отмечены +(1,2,3, 1,2,4, 1,2,5, 2,3,5, 2,4,5,3,4.5, 1.3.4, 1.4.5, 1.3.5). Сочетания из 5 по 4 расположены в первыхпяти столбцах (1,2,3,4, 1,2,3,5,1,3,4.6, 2,3,4,5, 1,2.4,5).20Сигналом окончания работы служитсигнал 25, который поступает на выходсо счетчика 26 при формировании сочетаний из 5 по 2 или со счетчика 27при формировании сочетаний из 5 по 4. 25Таким образом, предлагаемое устройство для перебора сочетаний, размещений и перестановок позволяет приформировании сочетаний значительносократить время вычислений, а именно: З 0при формировании сочетаний из 5 по2 и из 5 по 3 - в 5 раз, а при формировании сочетаний из 5 по 4 - в24 раза.Ф о р м у л а и з о б р е тле н и я351.Устройство для перебора сочетаний, размещений и перестановок, содержащее две группы регистров, блокуправления, блох переключателей,группу элементов сравнения, делитель, 40три элемента задержки, первый счетчик, дешифратор, две группы элементов ИЛИ, две группы элементов И ипервый элемент ИЛИ, причем информационные входы коммутатора соединены 45с выходами регистров первой группыи с первыми входами элементов И первой группы, вторые входы которыхсоединены с выходами элементов ИЛИпервой группы, второй вход последнего элемента И первой группы соединенс первым выходом блока переключателейи первыми входами элементов ИЛИ первой группы, вторые и третьи входыкоторых соединены с вторым и третьимвыходами блока переключателей, выходыэлементов И первой группы являютсявыходами сочетаний устройства, тактовый вход которого соединен с тактовым входом первого счетчика и входом делителя, выход которогб соединен с входами разрешения приема регистров первой группы, первым входом блока управления и входом первого элемента задержки, выход которого соединен с входом второго элемента задержки, выход которого соединен с вторым входом блока управления и входом третьего элемента задержки, выход которого соединен с третьим входом блока управления, четвертый вход которого соединен с входом установки начального состояния устройства и входом установки первого счетчика, выход которого соединен с входом дешифратора и первыми входами элементов сравнения группы, вторые входы которых соединены с ин. формационными входами регистров первой группы, первыми входами элементов И второй группы и выходами ре. гистров второй группы, входы которых соединены с выходами элементов ИЛИ второй группы, первые входы которых соединены с информационными входами устройства, выходы перестановок ко.торого соединены с выходами элементов сравнения группы, выходы дешифратора соединены с вторыми входами элементов И второй группы, выходы которых соединены с входами первого элемента ИЛИ, выход которого соединен с входом регистра, выход которот о является выходом устройства, выход окончания генерирования которого соединен с первым выходом блока управления, второй, третий, четвертый и пятый выходы которого соединены с одноименными управляющими входами коммутатора, выходы которого соединены с соответствующими входами элементов ИЛИ второй группы, о т л и - ч а ю щ е е с я тем, что, с целью увеличения быстродействия при формировании сочетаний путем исключения выборок повторяющихся сочетаний, в него введены второй элемент ИЛИ и второй и третий счетчики с коэффици- Фентом пересчета (и) 1 и и соответственно (и-количество элементов перебора), причем выход делителя соединен с входами блока переключателей, первый выход которого соединен со счетным входом второго счетчика, вход сброса которого соединен с входом установки начального состояния устройства и входом сброса третьего1363232 Таблица 1 Описание соединений в коммутаторе между входамикоммутатора и входами элементов ИЛИ и И группкоммутатора Входы Входы элементов ИЛИ Входы элементов Итатора 1 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 1 1 1 2 2 3 2 2 3 4 Таблица 2 Описание соединений н коммутаторе между выходами элементов ИЛИ и входами элементов И групп коммутатора Выходы элементов И1 2 3 4 5 6 7 8 9 10 11 Выходы счетчика, счетный вход которого соединен с выходом второго элемента ИЛИ, первый и второй вхо ды которого соединены с вторым5 и третьим выходами блока переключателей, выходы второго итретьего счетчиков соединены с выходом окончаниягенерирования устройства.2, Устройство по п,1, о т л и - .10 ч а ю щ е е с я тем, что коммутатор содержит и элементов ИЛИ и и группэлементов И, причем информационныевходы коммутатора соединены с первыми входами элементов И соответствую"щих групп, вторые и третьи входыкоторых соединены с соответствующимиуправляющими входами коммутатора ивыходами элементов ИЛИ, входы которыхсоединены с соответствующими управляющими входами коммутатора.О 1363232 Та блица 3 Описание соединений между выходами элементов И группы коммутатора и входами элементов ИЛИ второй группы устройства1363232 Составитель О.БерТехред М.Дидык ва Редактор А.Маковс ректор М.Демчик Тираж 671дарственного комит изобретений и откр Ж, Раушская наб аказ 6364/4 писное ВНИИПИ Госу по делам 113035, Москва, а СС 4/ 4 роиэводственно-полиграфическое предприятие, в.Ужгород, ул.Прое