Устройство для перебора сочетаний Советский патент 1985 года по МПК G06F17/10 

Изобретение относится к вычислиельной технике и может быть испольовано в устройствах, решающих коминаторные задачи, связанные с перебоом сочетаний.5

По основному авт. ев, № 903891 известно устройство для перебора со- етаний, содержащее т-разрядный регистр, группу,из (т-2) элементов задержки, элемент И, триггер, первую rjpynny из (nirt) элементов И, вторую группу из m элементов И, третью группу из () элементов И, четвертую группу из (т-2) э.лементов И, первую группу из (т-1) элементов ИЛИ, вторую группу из (т-2) элементов ИЛИ, причем вход устройства подключен т первому входу первого элемента И второй группы, к первому входу первого элемента-. И третьей группы и к ну-левому входу триггера, нулевой выход которого соединен с первым входом элемента И, а единичный вход с выходом элемента И, второй вход которого подключен к выходу первого элемента ИЛИ второй группы и к первому входу первого элемента И четвертой группы, второй вход которого подключен к единичному выходу триггера, второй вход

30 i-ro элемента И второй группы (i Г, т) подключен к единичному вы- ходу i-ro разряда регистра и к первому входу J-го элемента И четвертой группы (j 1, m-2), выход i-ro элемента И второй группы (1 т) подклю-35 чен к первьи входам -х элементов И и ИЖ первых групп .соответственно t (), второй вход Е-го элемента ИЛИ первой группы подключен к выходу f-ro элемента И третьей группы и к первому входу (С+1)-го элемента И третьей группы, второй вход -го элемента И третьей группы подключен к нулевому выходу i-ro разряда регистра и к второму входу -го элемента И первой группы, выход которого подключен к первому единичному входу i-ro разряда регистра, второй единичный вход которого подключен к выходу j-ro элемента И чет- 50 вертой группы и к второму входу (j + 1)-ro элемента И четвертой группы, нулевой выход i-ro разряда регистра (i т m) подключен к выходу i-ro И второй группы и к 55 первому входу j-ro элеме 1та ИЛИ второй группы, второй вход которого подключен к выходу j-ro элемента заде.ржкй группы, вход которого подключен к выходу (j + 1)-ro (j 7 m-3) элемента ИЛИ второй группы, выход ш-го элемента И второй группы подключен к выходу окончания перебора сочетаний устройства и к нулевому входу т-го разряда регистра, вход.(т-2)-1О элемента задержки группы подключен к нулевому входу (т-1)-го разряда регистра l .

Однако данное устройство позволяет перебирать сочетания из m по п, только для фиксированных значений т. Если же возникает необходимость изменять число т, то следует либо увеличить число триггеров и других логических элементов, либо уменьшить их до требуемого числа. Поэтому область использования известного . устройства в объектах вычислительной техники ограничена.

Цель изобретения - расширение области применения устройства за счет обеспечения перебора сочетаний из k и п для любых пи k m.

Поставленная цель достигается тем, что устройство для перебора сочетаний содержит группу элементов запрета и элемент ИЛИ, причем Ч-й вход задания количества элементов подключен к третьему входу соответствующего элемента И первой группы и к управляемому входу соответствующего элемента запрета группы, информационный вход которой соединен с выходом соответствующего элемента И второй группы, выходы элементов запрета группы и последнего элемента И второй группы соединены с соответствующими входами элемента ИЛИ, выход которого является выходом окончания работы ( 1,2j ..., , m максимальное количество элементов).

На чертеже приведена схема устройства для перебора сочетаний.

Устройство для перебора сочетаний содерлсит первый регистр, .образованный из m триггеров 1, первую группу элементов И 2, вторую группу элементов И 3, первую группу элементов ИЛИ 4, третью группу элементов И 5, четвертую группу элементов И 6, группу элементов 7 задержки, группу элементов ИЛИ 8, триггер 9, элемент И 10, вхорд 11 задания количества элементов, элемент ИЛИ 12, группу элементов ЗАПРЕТ 13, выход 14 окон3

чания работы, шину 15 входного сигн ла.

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

Для полного перебора всех возможных сочетаний используется метод, осн.ованный на образовании каждого нового сочетаний из предыдущего путем замены крайней cnpiaBa в первом регистре комбинации 01 на 10 и переписи всех единиц, расположенных правее, в крайние правые позиции.

Перед началом работы производится начальная установка триггеров 1 в нулевое состояние, а затем запись единицв п крайние справа триггеры регистра 1 и подача на (k-1) крайних справа входов 11 задания количества элементов единиц. Разрешающие потенциалы с входов 11 обеспечивают прохождение импульсов перевода триггеров 1 первого регистра в единичное состояние с выходов (k-1) крайних справа элементов И 3 второй группы на первые входы (k-2) крайних справа элементов И 2 первой группы. В то же время потенциал с крайних выходов 11, поступая на управляющие входы (k-1) крайних спра401274

ва элементов ЗАПРЕТ 13, запрещает прохождение импульсов окончания перебора сочетаний с вькодов (k-l) крайних справа элементов И 3 второй 5 группы на входы элемента ИЛИ 12. Таким образом, обеспечивается перебор всех возможных сочетаний из k по п..-Как только триггеры 1 первого регистра от (k-n)-ro до k-ro

10 окажутся в единичном состоянии, то следующий импульс пройдет с k-ro элемента И 3 второй группы через k-й элемент ЗАПРЕТ 13, который изза отсутствия запрещающего потенци 5 ала с k-ro входа 11 будет открыт, поступит на элемент ИЛИ 12. С выхода 14, таким образом, будет снят сигнал окончания перебора. Одновременно импульс с выхода k-ro элемента И 3 второй группы не сможет пройти на выход (k-1) элемента И 2 первой группы, так как на третий его вход не будет подаваться разрешающий потенциал.

25 Таким образомi предлагаемое устройство для перебора сочетаний производит перебор сочетаний из k по п для любых п и k т, что существенно расширяет область применения уст3Q ройства.

УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ по авт. св. № 903891, о тличающееся тем, что, с целью расширения области применения за счет обеспечения перебора сочетаний из k по п для любых п и k т. оно содержит группу элементов запрета и элемент ИЛИ, причем -й вход задания количества элементов соединен с третьим входом соответствующего элемента И первой группы и управляющим входом соответствующего элемента запрета группы, информационньй вход которой соединен с выходом соответствующего элемента И второй группы, выходы элементов запрета группы и .последнего элемента И второй группы соединены с соответствующими входами элемента ИЛИ, выход которого является выходом окончания работы