Устройство для перебора сочетаний
УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ по авт. св. № 903891, о тличающееся тем, что, с целью расширения области применения за счет обеспечения перебора сочетаний из k по п для любых п и k т. оно содержит группу элементов запрета и элемент ИЛИ, причем -й вход задания количества элементов соединен с третьим входом соответствующего элемента И первой группы и управляющим входом соответствующего элемента запрета группы, информационньй вход которой соединен с выходом соответствующего элемента И второй группы , выходы элементов запрета группы и .последнего элемента И второй группы соединены с соответствующими входами элемента ИЛИ, выход которого является выходом окончания работы
СОЮЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИН
4(51) С 06 F 15/31
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (61) 903891 (21) 3648566/24-24 (22) 03.10.83 (46) 15.02.85. Бюл. ¹- 6 (72) В.А. Лукоянов (53) 681.3(088.8) (56) 1. Авторское свидетельство СССР
¹ 903891, кл. G 06 F 15/31, 1980 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ IIFPEBOPA
СОЧЕТАНИЙ по авт, св. № 903891, о тл и ч а ю щ е е с я тем, что, с целью расширения области применения за счет обеспечения перебора сочетаний из 1 по п для любых и и 1 тп, „„SU„„ « 27 А оно содержит группу элементов запрета и элемент ИЛИ, причем E-й вход задания количества элементов соединен с третьим входом соответствующего элемента И первой группы и управляющим входом соответствующего элемента запрета группы, информационный вход которой соединен с выходом соответствующего элемента И второй группы, выходы элементов запрета группы и .последнего элемента И второй группы соединены с соответствующими входами элемента ИЛИ, выход которого является выходом окончания работы (0 = 1, 2, ..., m-1, m — максимальное количество элементоц).
1 140127
Изобретение относится к вычислительной технике и может быть использовано в устройствах, решающих комбинаторные задачи, связанные с перебором сочетаний.
По основному авт. св. Р 903891 известно устройство для перебора сочетаний, содержащее тп-разрядный регистр, группу из (m-2) элементов .задержки, элемент И, триггер, первую группу из (m-, 1) элементов И, вторую группу из ш элементов И, третью группу из (m 1) элементов И, четвертую группу из (m-2) элементов И, первую
15 группу из (m-1) элементов ИЛИ, вторую группу из (m-2) элементов ИЛИ, причем вход устройства подключен к первому входу первого элемента И второй группы, к первому входу первого эле70 мента. И третьей группы и к нулевому входу триггера, нулевой выход которого соединен с первым входом элемента И, а единичный вход — с выходом элемента И, второй вход которого подключен к выходу первого элемента ИЛИ второй группы и к первому входу первого элемента И четвертой группы, второй вход которого подключен к единичному выхоцу триггера, второй вход
i-го элемента И второй группы (i
Г, т) подключен к единичпому выходу i-ro разряда регистра и к первому входу j-го элемента И четвертой группы (j = 1, m-2), выход i ão элемента И второй группы (i g m) подклю-З5 чен к первым входам 3 х элементов И и ИЛИ первых групп соответственно (1, m-1), второй вход E-го элемента ИЛИ первой группы подключен к выходу 1-ro элемента И третьей группы и к первому входу (5+1) -го элемента И третьей группы, второй вход 2-ro элемента И третьей группы подключен к нулевому выходу i-ro разряда регистра и к второму входу -го элемента И первой группы, выход которого. подключен к первому единичному входу i-ro разряда регистра, второй единичный вход которого подключен к выходу j-ro элемента И чет- 0 вертой группы и к второму входу (3+1)-ro элемента И четвертой группы, нулевой выход i-го разряда регистра (i y m) подключен к выходу
1-го элемента И второй группы и к первому входу j-ro элемента ИЛИ второй группы, второй вхоц которого подключен к выходу 1-го элемента задержки группы, вход которого подключен к выходу (j+1)-го (j тп-3) элемента
ИЛИ второй группы, выход m-го элемента И второй группы подключен к выходу окончания перебора сочетаний устройства и к нулевому входу m-ro разряда регистра, вход .(m-2)-го элемента задержки группы подключен к нулевому входу (m-i)-ro разряда регистра (1) .
Однако данное устройство позволяет перебирать сочетания из m по и, только для фиксированных значений т.
Если же возникает необходимость изменять число m то следует либо увеличить число триггеров и других логических элементов, либо уменьшить их до требуемого числа. Поэтому область использования известного . устройства в объектах вычислительной техники ограничена.
Цель изобретения — расширение области применения устройства за счет обеспечения перебора сочетаний из k и п для любых и и k 6< m.
Поставленная цель достигается тем, что устройство для перебора сочетаний содержит группу элементов запрета и элемент ИЛИ, причем 1-й вход задания количества элементов подключен к третьему входу соответствующего элемента И первой группы и к управляемому входу соответствующего элемента запрета группы, информационный вход которой соединен с выходом соответствующего элемента И второй группы, выходы элементов запрета группы и последнего элемента И второй группы соединены с соответствующими входами э.пемента ИЛИ, выход которого является выходом окончания работы (g = 1 2, ..., m 1, m— максимальное количество элементов).
На чертеже приведена схема устройства для перебора сочетаний.
Устройство для перебора сочетаний содержит первый регистр, .образованный из m триггеров 1, первую группу элементов И 2, вторую группу элементов И 3, первую группу элементов
ИЛИ 4, третью группу элементов И 5, четвертую группу элементов И 6, группу элементов 7 задержки, группу элементов ИЛИ 8, триггер 9, элемент
И 10, входы ii задания количества элементов, элемент ИЛИ 12, группу элементов ЗЛЛРЕТ 13, выход 14 оконСоставитель А. Клюев
Редактор Л. Авраменко Техред А.Бабинец
Корректор О. Билак
Заказ 265/38 Тираж 710
ВНИИПИ Государственного комитета СССР . по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5
Подписное
Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4
3 11 чания работы, шину 15 входного сигнала.
Устройство для перебора сочетаний работает следующим образом.
Для полного перебора всех возможных сочетаний используется метод, основанный на образовании каждого нового сочетаний из предыдущего путем замены крайней справа в первом регистре комбинации "01" на "10" и переписи всех единиц, расположенных правее, в крайние правые позиции.
Перед началом работы производится начальная установка триггеров 1 в нулевое состояние, а затем запись единиц в и крайние справа триггеры регистра 1 и подача на (k-1) крайних справа входов 11 задания количества элементов единиц. Разрешающие потенциалы с входов 11 обеспечивают прохождение импульсов перевода триггеров 1 первого регистра в единичное состояние с выходов (k-1) крайних справа элементов И 3 второй группы на первые входы (k 2) крайних справа элементов И 2 первой группы. В то же время потенциал с крайних выходов 11, поступая на управляющие входы (k-1) крайних спра40127 4 ва элементов ЗАПРЕТ 13, запрещает прохождение импульсов окончания перебора сочетаний с выходов (k-!) крайних справа элементов И 3 второй группы на входы элемента ИЛИ 12.
Таким образом, обеспечивается перебор всех возможных сочетаний из k по и. Как только триггеры 1 первого регистра от (k-n)-го до k-ro
lO окажутся в единичном состоянии, то следующии импульс пройдет с k-го элемента И 3 второй группы через
k-й элемент ЗАПРЕТ 13, который изза отсутствия запрещающего потенциала с k-го входа 11 будет открыт, поступит на элемент ИЛИ 12. С выхода 14, таким образом, будет снят сигнал окончания перебора. Одновременно импульс с выхода k-ro элемента И 3 второй группы не сможет пройти на выход (k- 1) элемента И 2 первой группы, так как на третий его вход не будет подаваться разрешающий потенциал.
Таким образом; предлагаемое устройство для перебора сочетаний производит перебор сочетаний из 1 по и для любых и и k < m что существенно расширяет область применения устзо
