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

пы, причем первый вход (гп-1)-го эле мента И четвертой группы соединен с выходом (т-2)-го элемента И четвертой группы, второй вход (m-l)-ro элемента И четвертой группы соединен с единичным выходом (т-2)-го разряда регистра устройства, первый вход , т-го элемента И четвертой группы соединен с выходом (m-l)-ro элемента И четвертой группы, второй вход т-го элемента И четвертой группы соединен с единичным выходом (m-l)-ro разряда регистра, выход т-го элемента И четвертой группы подключен к второму единичному входу т-го разряда регистра и к второму выходу окончания перебора сочетаний устройства, . первый вход (m-l)-ro элемента ИЛИ второй группы подключен к выходу

56205

(гп-1)-го элемента И второй группы, а первые входы т-го и (т+1)-го элементов ИЛИ второй группы подключены к выходу т-го элемента И второй группы, вторые входы т-го и )-ro элементов ИЛИ второй группы соединены с выходами т-го и (m-l)-ro элементов задержки группы соответственно, входы которых соединены с выходами (т+1)-го и т-го элементов ИЛИ второй группы соответственно, выход (ni-l)-ro элемента ИЛИ второй группы соединен с входом (т-2)-го элемента задержки группы, второй вход (m+l)-ro элемента ИЛИ второй группы подключен к выходу ()-го -элемента задержки группы, входл, которого подключен к выходу т-го элемента И второй . группы.

УСТРОЙСТВО ДЛЯ ПЕРЕВОРА 5СОЧЕТАЛИЙ, содержащее т-разрядный регистр, первую группу из (m-l) элементов И, вторую группу из m элементов И, третью группу из (m-l) элементов И, четвертую группу из (т-2) элементов И, первую группу из (m-l) элементов ИЛИ, вторую группу из (т-2) элементов ИЛИ, группу из (т-2) элементов задержки, элемент И и триггер, причем вход устройства подключен к первому входу первого элемента И второй группы, к первому входу первого элемента И третьей группы и к нулевому входу триггера, единичный вход которого подключен к выходу элемента И, первый вход которого подключен к нулевому выходу триггера, второй вход элемента И подключен к выходу I первого элемента ИЛИ второй группы и к первому входу первого элемента И четвертой группы, второй вход которого подключен к единичному выходу триггера, второй вход i-ro элемента И второй группы (,2,...,т) подключен к единичному выходу j-ro разряда регистра и к первому входу элемента И четвертой группы (,3,..j m-2), выход i-ro элемента И второй fi... - -С -Л- fi%-.; 11 «.... ,., f-I 5 -i J .-s .v; 5J- . . ,.I группы (i йп) подключён к первьт входам 1-ых элементов И и ИЛИ первых групп соответственно ( 1 1,2,...,m-l), второй вход 1-го элемента ИЛИ первой группы подключен к выходу 1-го элемента И третьей группы и к первому входу

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

Известно устройство для перебора сочетаний, содержащее регистры, счетчик, дешифратор, триггер, элементы И, элементы задержки и распределитель импульсов ГП .

Недостатками известного устройства являются его сложность, невысокое быстродействие и слабая приспособленность к схемным изменениям при увеличении разрядности устройства. I

Наиболее близким по технической

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

второй вход - к выходу первого элемента ИЛИ второй группы и к первому входу первого элемента И четвертой группы, второй вход которого подключен к единичному выходу триггера, второй вход -го элемента И второй группы (i 1,2,...,m) подключен к единичному выходу i-го разряда регистра и к первому входу j-ro элемента И.четвертой группы ( ,3,....т-2), выход

i-ro элемента И второй группы () подключен к первым входам -ых элементов И и ШШ первых групп соответственно (1 1,2, .. .,т-1),, второй вход 1-го элемента ИЛИ первой группы подключей к выходу 1-го элемента И третьей группы и к первому входу ()-го элемента И третьей группы, второй вход. 1-го элемента И третьей группы подключен к нулевому выходу i-го разря/ia регистра соответственно, который подключен к второму входу 1-го элемента И первой группы, выход которого подключен к первому единичному входу разряда регистра, второй единичный вход которого подключен к выходу j-ro элемента И четвертой

групп1 1 и к 11ХОДУ (j-t-l)-ro элемента И чет1 ертой 1руипы, нулевой вход i-ro разряда регистра (ij) подключен к выходу i-ro элемента И второй группы и к первому входу j-ro элемента ИЛИ второй группы, второй вход которого подключен к выходу j-r элемента задержки группы, вход которого подключен к выходу (j-t-l)-ro элемента ИЛИ второй группы, выход т-го элемента И второй гругн пы подключен к выходу окончання перебора сочетаний устройства и к нулевому входу т-го разряда регистра 2 .

Недостатком известного устройства является то, что область его применения ограничена, поскольку устройство позволяет получить все сочетания из т элементов по п для фяпссированного значения п. На практике часто возникает необходимость получения всех сочетаний из т элементов по п при произвольном изменении значения п от I до т.

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

,m, I

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

группы (,2,...,т) подключен к единичному выходу j-ro разряда рьгистра и к первому входу j-ro элемента И четвертой группы (,3,..., m-2), выход i-ro элемента И второй группы (.i) подключен к первым входам 1 -ых эле(лентов И и ИЛИ первых групп соответственно (,2,,.., т-1),.второй вход 1-го элемента ИЛИ первой группы подключен к выходу 1-го элемента И третьей группы и к первому входу (1+1)-го элемента И третьей группы, второй вход 1-го элемента И третьей группы подключен к нулевому выходу 5-го разряда регистра соответственно, который подключен к второму входу I-го элемента И первой группы,, выход которого подключен к первому единичному входу разряда регистра, второй единичный вход которого подключен к выходу j-r элемента И четвертой группы и к второму входу (j+l)-ro элемента И четвертой группы, нулевой вход 1-гО раряда регистра (т) подключен к вьпсоду i-го элемента И второй группы и к первому входу j-ro элемента ИЛИ второй группы, второй вход которого подключен к выходу j-ro. элемента задержки группы, вход которого подключен к выходу (j+l)-ro () элемента ИЛИ второй группы, выход т-го элемента И второй группы подключен к первому выходу окончания перебора сочетаний устройства и к нулевому входу т-го разряда регистра, дополнительно содержит (т-1)-ый ит-ы элементы И четвертой группы (т-1)-ый rt-ый и (т41)-ый элементы ИЛИ второй группы, (п1-1)-ый, т-ый и (т4-1)-ый элменты задержки группы, причем первый вход (т-1)-го элемента И четвертой .группы соединен с выходом (т-2)-го элемента И четвертой группы, второй вход (т-1)-го элемента И четвертой группы соединен с единичным выходом (т-2)-го разряда регистра устройства первый вход ш-го элемента И четвертой группы соединен с выходом (т-1)-го Элемента И четвертой группы, второй вход т-го элемента И четвертой группы соединен с единичным выходом (т-1)-го разряда регистра, гааход т-г элемента И четвертой группы подключен к второму единичному входу т-го разряда регистра и к втopo fy выходу окончания перебора сочетаний устройства, первый вход (т-1)-го элемента ШЖ второй группы подключен к выходу (m-l)ro элемента И второй группы, а первые входы т-го н (тФ1)го элементов ИЛИ второй группы подключены к выходу т-го элемента И второй 5 группы, вторые входы т-го и ()го элементов ИЛИ второй группы соединены с выходами и ()го элементов задержки группы соответственно, входы которых соединены с выхода-О ми (rrt-f-f/ ro и т-го элементов ИЛИ второй группы соответственно,выход (m-l)-ro элемента ИЛИ второй группы соединен с входом (т-2)го элемента задеряски группы, второй вход (m-bl)-ix55 элеме.кта. ИЛИ второй группы подключе к выходу (m+l)-го элемента задержк группы,, вход которого подключен к в ходу гп-го элемента И второй группы На чертеже представлена схема пр лагаечого устройства Устройство содержит регистр, образоваш ый триггерами 1, и распределитель импульсов, образо:вз,нньт эхшментами И 2, элементамк И Зз элементами ИЛИ.4, элементами И 5э элементами И бз элемента ми 7 задерлски, элементами ИЛИ Sj триггером 9§ элементом И 10, шину П входного импу-льса; шину 12 первого {сигнала окончания перебора, Ш5-1К37 13 второго Сигнала окончания перебора. При ггереборе сочетаний каждое очередное состояние образуется из предыдущего путем замены крайней справа комбинации 01 на 0 и переписи всек единицjрасположенных правее3 в крайние правые позиции.- При этом в первоначальном состоянии все единицы должны располаг ся в крайних справа позициях, в последнем же состоянии они переходят в крайние слева позиции Например, при и устройством вырабаты ваются.сочетания; 10 П О 100J 1010 Устройство может работать в двух режимах. В первом режиме обеспечива ется перебор сочетаний из m элементов по п для фиксированного значени п, а во втором ддтя n,m, В первом перед началом ра боты ,|дпя перебора псех сочетаний из m элементов по п производится установка всех триггеров 1 регистра в нулевое состояние, а затем запись, единиц в п крайние справа триггеры (п 1,2,...,т-1). Каждый раз при поступлении входно го импульса по шине 11 триггер 9 распределителя импульсов устанавливается в нулевое состояние, обеспечивая тем самым разрешающий потенциал на управляющем входе элемента И 10 и запрещающий - на управляющем входе элемента И ГО и на управляющем входе первого элемента И 6 четвертой группы. Этот же импульс поступает -на информационные входы первого элемента И 3 второй группы и первого элемента И 5 третьей группы. При единичном состоянии триггеров 1 регистра на управляющих входах элементов И 3 и 6 второй и четвертой групп находятся разрешающие потенциалы, а на управляющих входах элементов И 2 и 5 - запрещающие потенциалы, при нулевом состоянии триггеров 1 регистра, наоборот, на управляющих входах элементов И 3 и 6 находятся запрещающие потенциальи а на управляющих входах элементов И 2 и 5 - разрешающие Если г (,2,,..,т) крайние справа триггеры 1 находятся в единичном соотоЯНИН, то входной импульс проходит последовательно элементы И 3 вто рой группы и или 4 первой группы и устанавливает эти триггеры в нулевое состояние, а ()-ьш триггер 1 через открытый элемент И 2 первой группы в единичное состояние и, кроме того J поступает на входы элементов ИЛИ 8 второй группы, что обеспечивает формирование на выходе первого элемента ИЛИ 8 второй группы серию из г импульсов (элементы 7 задержки обеспечивают временную растяжку серии импульсов., необходимую для стабильности переходных процессов при дальнейшей работе). Первый импульс серии, пройдя через элемент И JO, устанавливает триггер 9 распределителя импульсов в единичное состояние, чем обеспечивается подача на управляющий вход первого элемента И 6 четвертой группы разрешающего потенциала. Второй импульс серии, пройдя первый элемент И 6 четвертой группы, уста- , навливает первый триггер 1 регистра в единичное состояние, чем обеспечивается прохождение третьего импульса серии через второй элемент И 6 четвертой группы и установка в единичное состояние второго, триггера 1 регистра, а с каждым очередным импульсом серии - установка очередного по порядку триггера I регистра включительно (г-1)-ый триггер. На этом заканчивается такт фбрмирова- ния очередного сочетания, которое снимается с единичный входов (а|, ал, ...,a|q) триггеров 1 регистра.

Если г (,2,...,m-n) крайние правые триггеры 1 регистра находятся в нулевом состоянии, то входной импульс, пройдя г открытых элемен-г тов И 5 третьей группы, поступает через г-ый элемент ИЛИ 4 первой Группы на открытый (г+1)-ый элемент И 3 второй группы и в дальнейшем выпол ; няет действия, аналогичные описанным : Если в текущем сочетании в крайней справа позиции имеется комбинация 01, то при формировании очередного сочетания она преобразуется в комбинацию 10, что соответствует сдвигу единицы на один разряд влево. Если п крайние слева триггеры 1 регистра находятся в единичном состоянии (последнее из формируемых сочета кий), то при поступлении очередного входного импульса с выхода последнего элемента И 3 второй группы шедается по шине 12 первого сигнала окончания перебора.

Во втором режиме перед началом работы производится установка всех триггеров 1 регистра в нулевое сое-. тояние, а затем запись единицы в первый крайний справа триггер. В дальнейшем устройство работает аналогично вьшеописанному до перемещения единицы в крайний слева триггер регистра.

Очередной входной импульс, по ступиввшй по шине П, пройдет все открытые элементы И 5 третьей группы, (т-1)-ый элемент ИЛИ 4 первой группы и открытый (т-1)-ый элемент И 3 второй группы, с выхода которого он поступит на установку т-го i триггера регистра в ноль и на шину 12 (в данном режиме сигнал с шины 12 не воспринимается как сигнал окон5 чания перебора). Одновременно этот сигнал поступает на первые входы т-го И (т+1)-го элементов ИЛИ 8 второй группы, а также через элемент 7 задержки на второй вход (т+1)-го

О элемента ИЛИ 8 этой же группы. Последнее обеспечивает формирование на выходе первого элемента ИЛИ второй группы серии из трех сигналов, , первый из которых установит в ничное состояние триггер 9, а последующие - в единичное состояние первый и второй крайние справа триггеры 1 регистра. После этого начинается цикл формирования сочетаний из 20 m элементов по п при .

В дальнейшем каждый раз при поступлении входного сигнала, когда .И крайние слева триггеры 1 регистра находятся в единичном состоянии,

25 эти триггеры сбрасываются в нулевое .состояние, а на выходе первого элемента ИЛИ 8 второй группы формируется серия из п -2 импульсов, которые йбеспечивают вышеописанным об30 разом установку в единичное состояние tt+l крайних справа триггеров регистра. Если все триггеры 1 регистра окажутся в единичном состоянии (последнее из формируемых сочё,е тание)., то при поступлении очередного входного импульса с выхода последнего элемента И 6 четвертой груп- пы выдается по шине 13 сигнал, который для данного режима является

дд сигналом окончания перебора.

Технико-экономический эффект от использования предлагаемого устройства состоит в расширении области применения, поскольку оно в отличие от известного позволяет формировать сочетания из m элементов по п не только для фиксированных значений

П, но и для ,т.