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

 

Изобретение относится к вычислительной технике и может использоваться в вычислительных машинах, решаюпщх комбинаторные задачи. Целыо изобретения является расширение функциональных возможностей за счет обеспечения формирования всех возможных сочетаний из m злементов по п для заданных значений m и п. Устройство для перебора сочетаний содержит группу элеме гон И 1, регистр 2, четыре группы элементов И 3-6, две группы элементов ИЖ 7 и 8, группу 10 элементов задержки, элементы ИЛИ 9, элементы И 11, триггеры 12, элементы.И 13, триггеры 14-16, элементы И 17-23, элементы НЕ 24 и 25, элементы ИЛИ 26 и 27, элементы 28-31 задержки, переключатели 32, переключатель 33, перес ключатель 39 режимов. 1 ил. (Л 36,

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„.SU 2 41 7 A t (51)4 G 06 F 15 20

Д ъ,, Ф

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3848687/24-24 (22) 30.01.85 (46) 15.10 ° 86. Бюл, Ф 38 . (72) В.М.Полищук, Н.И.Крылов и В.В.Соколов .(53) 681. 325 (088. 8) (56) Авторское свидетельство СССР

У 634285, кл. С 06 Р,15/32, 1975.

Авторское свидетельство СССР

N 903891, кл. G 06 Г 15/31, 1980. (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ (57) Изобретение относится к вычислительной технике и мошет использоваться в вычислительных машинах, решающих комбинаторные задачи. Целью изобретения является расширение функщиональных возмо кностей эа счет обеспечения формирования всех возможных сочетаний иэ ш элементов по п для заданных значений m и п. Устройство для перебора сочетаний содерзит группу элеме .гон И 1, регистр 2, четыре группы элементов И 3-6, две группы элементов ИЛИ 7 и 8, группу 10 элементов задержки, элементы ИЛИ 9, элементы И 11, триггеры 12, элементы.И

13, триггеры 14-16, элементы И 17-23, элементы НЕ 24 и 25, элементы ИЛИ 26 и 27, элементы 28- 31 задержки, переключатели 32, переключатель 33, пере- р ключатель 39 рекимов. 1 ил. ®

1264197

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

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

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

Устройство содержит элементы И 1, регистр 2, элементы И 3, элементы И

4, элементы ИЛИ 5, элементы И 6, элементы ИЛИ 7, элементы И 8, элементы

ИЛИ 9, элементы 10 задержки, элементы И 11 триггеры 12, элементы И 13, триггеры 14-16, элементы 17-23, элементы НЕ 24 и 25, элементы ИЛИ 26 и

27, элементы 28-31 задержки, переклю- 20 чатели 32, двухсекционный переключатель 33, вход 34 начальной установки, вход 35 тактового сигнала, информацйонный выход 36, выход 37 сигнала окончания перебора, выход 38 сигнала

25 окончания перебора, переключатель 39 режимов„

При переборе сочетаний каждое очередное состояние образуется из предыдущего путем замены крайней справа З0 комбинаций "01 íà "10 и переписи всех единиц, расположеннМх правее, в крайние правые позиции. При этом в первоначальном состоянии все единицы должны располагаться в крайних справа 35 позициях. В последнем же состоянии они переходят в крайние слева позиции. Например, при m = 5 и п = 3 устройством вырабатываются сочетания

1. 00111 6. 10101 . 40

2. 01011 7. 10110

3. 01101 8. 11001

4. 01110 9. 11010

5. 10011 10. 11100

Устройство работает следующим образом.

Перед началом работы для перебора сочетаний из m элементов по и переключатель 33 устанавливается в тп-ное положение. Замыкаются контакты пере ключателей 32, соответствующих m младшим (правым) разрядам устройства.

После этого на вход 34 подается сигнал, который устанавливает B нулевое состояние триггеры 14 и 12, а затем с задержкой на элементе 31 задержки через замкнутые контакты переключателя 32 устанавливает п крайние справа триггеры 12 в единичное состояние.

Устройство может работать в двух режимах. В первом режиме обеспечивается перебор сочетаний для данного фиксированного значения п, при этом переключатель 39 режимов устанавливается в положение, обеспечивающее соединение выхода элементов И 20 с выходом 37. Во втором режиме обеспечивается перебор всех сочетаний для значений п = k, m.- В этом случае переключатель 39 устанавливается в положение, обеспечивающее соединение выхода элемента И 20 с входами элементов И 21 и 22.

Устройство в первом режиме работает следующим образом.

Первый сигнал, поступающий по входу 35, проходит через открытый элемент И 18, устанавливает триггер 14 в единичное состояние и поступает на вход элементов ИЛИ 27, Сигнал с выхода элементов ИЛИ 27 устанавливает в нулевое состояние триггер 15 и триггеры регистра и с задержкой на элементе 30 через элементы И 11 и ИЛИ 7 переписывает содержимое триггеров 12 в триггеры регистра 2. Этот же сигнал, задержанный на элементе 29 задержки, поступает через элемент ИЛИ

26 на входы элементов И 1 и выдает на информационный выход 36 первое из формулируемых сочетаний (элемент 29 задержки обеспечивает задержку сигналов на время прохождения сигнала че- рез элемент задержки, элемент И 11, элемент ИПИ 7 и переходных процессов в триггере регистра 2).

При поступлении очередного сигнала на вход 35 он проходит через открытый элемент И !7 и устанавливает триггер 16 в нулевое состояние, о6еспечивая тем самым разрешающий потенциал на входе элемента И 23 и запрещающий — на входе первого элемента И

8. Этот же сигнал поступает на входы первого элемента И 4 и первого элемента И 6. При единичном состоянии триггеров регистра 2 на входах. элементов И 4 и 8 находятся разрешающие потенциалы, а на входах элементов И

3 и 6 — запрещающие потенциалы. При нулевом состоянии триггеров регистра

2, наоборот, на входах элементов И

4 и 8 находятся запрещающие потенциалы, а на входах элементов И 3 и 6—

РазреЖающие, 1264

Если r (r = 1, 2, ..., ш) крайние справа триггеры регистра 2 находятся в единичном состоянии, то тактовый сигнал проходит последовательно элементы И 4 и ИЛИ 5 и устанавливает эти триггеры в нулевое состояние, а

r+1-й триггер регистра 2 через открытый элемент И 3 — в единичное состояние, и поступает на входы элементов

ИЛИ 9, что обеспечивает формирование на выходе первого элемента ИЛИ 9 се рии из r импульсов (элементы 10 заДержки обеспечивают временную растяжку серии импульсов, необходимую для стабильности переходных процессов при 15 дальнейшей работе),. Первый импульс серии, пройдя через элемент И 23, устанавливает триггер 16 в единичное состояние, чем обеспечивается подача на вход первого элемента И 8 разреша- 2О ющего потенциала. Второй импульс серии, пройдя первые элементы И 8 и

ИЛИ 7, устанавливает первый триггер регистра 2 в единичное состояние, чем обеспечивается прохождение третьего импульса серии через второй элемент

И 8 и установка в единичное состояние второго триггера регистра 2, а с каждым очередным импульсом серии установка очередного по порядку тригге- 30 ра регистра 2 по r-1-й триггер включительно. На этом заканчивается такт формирования очередного сочетания, которое снимается с единичных выходов триггеров регистра 2 и выдается черезЗ5 элементы И 1 на информационный выход устройства этим же управляющим сигналом, задержанным к этому времени на элементе 28 задержки и прошедшим через открытые элементы И 19 и ИЛИ 26.

° . Если (r = 1, 2, ..., ш-а) крайние правые триггеры регистра 2 находятся в нулевом состоянии, то тактовый сигнал, пройдя r открытых элементов И 6,. поступает через r-й элемент ИЛИ 5 иа открытый г+1-й элемент И 4.и в даль нейшем выполняет аналогичные дейст Вия °

Если в текущем сочетании в крайней справа позиции имеется комбинация 50

"01", то при формировании очередного сочетания она преобразуется в комбинацию "10".

После того, как сформированы и выданы все сочетания из m элементов Ы по и для данного значения и (при

m C ш „ ) очередным тактовым сигналом будет сформировано следующее со197 четание, при котором m+t-й триггер регистра 2 находится в единичном состоянии. Сигнал из этого триггера через замкнутые клеммы соответствующей секции переключателя 33 поступает на вход элемента И 20 и через элемент

НЕ 24 — на вход элемента И 19, чем обеспечивается запрет прохождения задержанного на элементе 28 задержки сигнала через элемент И 19 и разрешение его прохождения через элемент И

20. С выхода элемента И 20 сигнал подается через замкнутые контакты переключателя 39 на выход 37, сигнализируя тем самым об окончании работы устройства в данном режиме.

Во втором режиме устройство до появления сигнала на выходе элемента И

20 работает аналогично. Начиная с этого момента сигнал с выхода элемента И 20 поступает на входы элементов

И 21 и 22.

Так .как обычно n (m, то с единичного выхода m-го триггера 12 через замкнутые контакты соответствующей секции переключателя 33 на вход элемента И 2t подается запрещающий потенциал, а на вход элемента И 22 через элемент НЕ 25 — разрешающий потенциал. Сигнал проходит через элемент И 22 и поступает на входы элементов И 13 и вход элемента ИЛИ 27.

Поскольку первые и справа триггеры 12 находятся в единичном состоянии, то на входах первых п справа элементов

И 13 находятся разрешающие потенциалы, Поэтому сигнал, поступающий на входы элементов И 13, устанавливает в единичное состояние n+1-й триггер

12 и подтверждает единичные состояния предццущих триггеров 12, чем обеспечивается увеличение значения и на единицу, Этот же сигнал проходит элемент ИЛИ 27 и с его выхода обеспечивает выполнение действий, аналогичных для первого режима работы, В дальнейшем процесс повторяется.

После того, как сформировано и выдано последнее из формируемых сочетаний, т.е. когда значение п станет равным m, на входе элемента И 21 находится разрешающий потенциал, а на ,входе элемента И 2? — запрещающий.

Поэтому сигнал с выхода элемента И

20 через элемент И 21 поступает на выход 38, сигнализируя тем самьж об окончании работы устройства в данном режиме.

1264197

Для обеих режимов в случае, когда

m < m,„, и п крайние слева триггеры регистра 2 находятся в единичном сос.тоянии (последнее из формируемых сочетаний при данном n) при поступлении очередного тактового сигнала на выходе последнего элемента И 4 появляется сигнал, который устанавливает триггер 15 в единичное состояние, потенциал с единичного выхода которого подается через замкнутые контакты переключателя 33 на элементы И 19 и 20, управляя их работой.

Формула изобретения

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

m-1 элементов И, вторую группу m элементов И, третью группу m-1 элементов И, четвертую группу m-2 элементов

И, первую группу m-1 элементов ИЛИ„ вторую группу m-2 элементов ИЛИ, группу m-2 элементов задержки, первый 5 элемент И и первый триггер, единичный вход которого подключен к выходу первого элемента И, первый вход которого подключен к выходу первого элемента

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

И четвертой группы (j = 2, 3, ш-2), выход i-ro элемента И второй группы (i Ф m) подключен к первым

40 входам f.-х элементов И и ИЛИ первых групп соответственно (I = 1, 2, ш-1), второй вход t-ro элемента ИЛИ первой группы подключен к выходу f-ro элемента И третьей группы и к первому

45 входу 7+1-ro элемента И третьей группы, второй вход 7-го элемента И третьей группы подключен к нулевому выходу i-го разряда регистра и к второму входу t-го элемента И первой группы, выход которого подключен к

50 единичному входу первого разряда ре( гистра, нулевой вход i-го разряда ре. гистра (i P m) подключен к выходу -го элемента И второй группы и к первому входу j-ro элемента ИЛИ вто- 55 рой группы, второй вход которого подключен к выходу j-го элемента за-. держки группы, вход которого подключен к выходу j+1-го (j 4 m-3) элемента ИЛИ второй группы, выход m ro элемента И второй группы подключен к нулевому входу ш-ro разряда регистра, вход ш-2-го элемента задержки группы подключен,к нулевому входу m-1-го разряда регистра, о т л и ч а ю щ ее с я тем, что, с целью расширения функциональных возможностей за счет обеспечения формирования всех возможных сочетаний из ш элементов по п для заданных значений m и п, в него введены группа триггеров, пятая группа ш-1 элементов И, шестая и седьмая группы m элементов И, третья группа

m-2 элементов ИЛИ, второй, третий,, четвертый, пятый, шестой и седьмой элементы И, первый и второй элементы

ИЛИ, второй и третий триггеры, первый и второй элементы НЕ, первый, второй, третий и четвертый элементы задержки, группа ш переключателей, переключатель режимов, двухсекционный переключатель, причем входы переключателей группы соединены с первыми единичными входами триггеров группы, единичные выходы которых, кроме ш-го соответственно, соединены с первыми входами элементов И пятой группы и с первыми входами элементов И шестой группы, выходы .i-х элементов И четвертой группы (i = 1, 2,, m-2) соединены с вторыми входами i+1-х элементов И четвертой группы и с первыми входами i--x элементов ИЛИ третьей группы, вторые входы i-х элементов ИЛИ третьей группы соединены с выходами i-х элементов И шестой группы, выходы элементов ИЛИ третьей группы соединены с вторыми единичными входами i-х разрядов регистра, выходы ш-1-го и m-ro элементов И шестой группы соединены соответственно с информационными входами разрядов регистра, первые входы элементов И седьмой группы соединены соответственно с единичными выходами разрядов регистра, выходы элементов И седьмой группы являются информационным выходом устройства.„ входы первой секции двухсекционного переключателя в порядке возрастания ньмеров соединены соответственно с единичными выходами триггеров группы, начиная с первого триггера, выход первой секции двухсекционного переключателя соединен с входом первого элемента НЕ и с первым входом третьего.элемента И, входы

1264197

Составитель .А.Жеренов

Техред М. Ходанич Корректор C.×åðíè

Редактор И.Касарда

Заказ 5564/5O Тираж 671 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5,Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4 второй секции двухсекционного переключателя в порядке возрастания номеров соединены соответственно с единичными выходами разрядов регистра, начиная со второго разряда, m-й вход второй секции двухсекционного переключателя соединен с единичным выходом второго триггера, а выход соединен с входом второго элемента НЕ и с первым входом четвертого элемента И, выход первого элемента НЕ соединен с первым входом второго элемента. И, выход второго элемента НЕ соединен с первым входом пятого элемента И, первые входы шестого и седьмого элемен- 15 тов И соединены с входом тактовых сигналов устройства,.второй вход шестого элемента И соединен с нулевым выходом третьего триггера, второй вход седьмого элемента И соединен с единичным выходом третьего триггера, выход шестого элемента И соединен с единичным входом третьего триггера и с первым входом первого элемента ИЛИ, выход которого соединен с нулевым р входом триггера, с входами сброса разрядов регистра, через первый элемент задержки — с вторыми входами элементов И шестой группы и через второй элемент задержки — с первым входом второго элемента ИЛИ, выход которого соединен с вторыми входами элементов И седьмой группы, вход начальной установки устройства соединен с нулевым входом третьего триггера, с нулевыми входами триггеров группы и через третий элемент задержки — с входами переключателей группы, выход седьмого элемента И соединен с вторым входом первого элемента

И второй группы, с первым входом первого элемента И третьей группы, с нулевым входом первого триггера и через четвертый элемент задержки — с вторыми входами четвертого и пятого элементов И, выход второго элемента И соединен с вторым входом первого элемента ИЛИ и с вторыми входами элементов И пятой группы, выходы i-х эле-. ментов И пятой группы (i = 1,2,...

m-1) соединены соответственно с информационными входами +1-х триггеРов группы выход четвертого элемента

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