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

Изобретение относится к вычислительной технике и может быть использовано в вычислительных машинах, решающих комбинаторные задачи. Цель изобретения - расширение фун кциональных возможностей за счет обе спечения формирования всех возможных сочетаний из m элементов по п для заданных значений m и п. На чертеже представлена схема ус тройства. Устройство содержит, элементы И 1, регистр 2, элементы ИЗ, элементы И 4, элементы ИЛИ 5, элементы И 6, эле менты ИЛИ 7, элементы И 8, элементы ИЛИ 9, элементы 10 задержки, элементы И -11, триггеры 12, элементы И 13, триггеры 14-16, элементы 17-23, элементы НЕ 24 и 25, элементы ИЛИ 26 и 27, элементы 28-31 задержки, переклю чатели 32, двухсекционный переключатель 33, вход 34 начальной установки, вход 35 тактового сигнала, инфор мационный вькод 36, выход 37 сигнала окончания перебора, выход 38 сигнала окончания перебора, переключатель 39 режимов. При переборе сочетаний каждое оче редное состояние образуется из преды дущего путем замены крайней справа комбинаций 01 на 10- и переписи всех единиц, расположеннЬгх правее, в крайние правые позиции. Лри этом в первоначальном состоянии все единицы должны располагаться в крайних справ позициях. В последнем же состоянии они переходят в крайние слева позиции. Например, при га 5 и п 3 уст ройством вырабатываются сочетания 1.001116. 10101 . . 2.010117. 10110 3.01101 . 8. 11001 4.ото9. 11010 5.1001110. 11100 Устройство работает следующим образом. Перед началом работы для перебора сочетаний из m элементов по п переключатель 33 устанавливается в т-ное положение. Замыкаются контакты пере;ключателей 32, соответствующих m младшим (правым) разрядам устройства После этого на вход 34 подается сигнал, который устанавливает в нулевое состояние триггеры 14 и 12, а затем с задержкой на элементе 31 задержки через замкнутые контакты переключате ля 32 устанавливает п крайние справа триггеры 12 в единичное состояние. Устройство может работать в двух режимах, В первом режиме обеспечивается перебор сочетаний для данного фиксированного значения п, при этом переключатель 39 режимов устанавливается в положение, обеспечивающее соединение выхода элементов И 20 с выходом 37. Во втором режиме обеспечивается перебор всех сочетаний для значений п k, т В этом случае пе- реключатель 39 устанавливается в положение, обеспечивающее соединение выхода элемента И 20 с входами элементов И 21 и 22, Устройство в первом режиме работает следующим образом. Лервый сигнал, поступающий по входу 35, проходит через открытьга элемент И 18, устанавливает триггер 14 в единичное состояние и поступает на вход элементов ИЛИ 27, Сигнал с выхода элементов ШЖ 27 устанавливает в нулевое состояние триггер 15 и триггеры регистра и с задержкой на элементе 30 через элементы И 11 и ИЛИ 7 переписывает содержимое триггеров 12 в триггеры регистра 2. Этот же сигнал, задержанный на элементе 29 задержки, поступает через элемент ИЛИ 26 на входы элементов И 1 и выдает на информационный выход 36 первое из формулируемых сочетаний (элемент 29 задержки обеспечивает задержку сигналов на время прохождения сигнала через элемент задержки, элемент И 11, элемент ИЛИ 7 и переходных процессов в триггере регистра 2). При поступлении очередного сигнала на вход 35 он проходит через открытый элемент И 17 и устанавливает триггер 16. в нулевое состояние, обеспечивая тем самым разрешающий потенциал на входе элемента И 23 и запрещающий - на входе первого элемента И 8, Этот же сигнал поступает на входы первого элемента И 4 и первого элемента И 6, При единичном состоянии триггеров регистра 2 на входах элементов И 4 находятся разрешающие потенциалы, а на входах элементов И 3и 6 - запрещающие потенциалы. При нулевом состоянии триггеров регистра 2, наоборот, на входах элементов И 4и 8 находятся запрещающие потенциалы, а на входах элементов И 3 и 6 разрешающие.

Если г (г 1, 2, ..., т) крайние справа триггеры регистра 2 находятся в единичном состоянии, то тактовый сигнал проходит последовательно элементы И 4 и ИЛИ 5 и устанавливает эти триггеры в нулевое состояние, а г+1-й триггер регистра 2 через открытый элемент И 3 - в единичное состояние, и поступает на входы элементов ИЛИ 9, что обеспечивает формирование на выходе первого элемента ИЛИ 9 серии из г импульсов (элементы 10 задержки обеспечивают временную растяжку серии импульсов, необходимую для стабильности переходных процессов при дальнейшей работе).. Первый импульс серии, пройдя через элемент И 23, устанавливает триггер 16 в единичное состояние, чем обеспечивается подача на вход первого элемента И 8 разрешающего потенциала. Второй импульс серии, пройдя первые элементы И 8 и ИЛИ 7, устанавливает первый триггер регистра 2 в единичное состояние, чем обеспечивается прохождение третьего импульса серии через второй элемент И 8 и установка в единичное состояние второго триггера регистра 2, а с каждым очередным импульсом серии установка очередного по порядку триггера регистра 2 по г-1-й триггер включительно. На этом заканчивается такт формирования очередного сочетания, которое снимается с единичных выходов триггеров регистра 2 и вьщается через элементы И 1 на информационный выход устройства этим же управляющим сигналом, задержанным к этому времени на . элементе 28 задержки и прошедшим через открытые элементы И 19 и ШИ 26.

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

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

После того, как сформированы и выданы все сочетания из m элементов по п для данного значения п (при m га„д ) очередным тактовым сигналом будет сформировано следукицее сочетание, при котором m+1-й триггер регистра 2 находится в единичном состоянии. Сигнал из этого триггера через замкнутые клеммы соответствующей секции переключателя 33 поступает на вход элемента И 20 и через элемент НЕ 24 - на вход элемента И 19, чем обеспечивается запрет прохождения задержанного на элементе 28 задержки сигнала через элемент И 19 и разрешение его прохождения через элемент И 20. С выхода элемента И 20 сигнал подается через замкнутые контакты переключателя 39 на выход 37, сигнализируя тем самым об окончании работы устройства в данном режиме.

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

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

После того, как сформировано и выдано последнее из формируемых сочетаний, т.е. когда значение п станет равн1 т, на входе элемента И 2t находится разрешающий потенциал, а на (Входе элемента И 22 - запре1цакнций.

Поэтому сигнал с выхода элемента И t 20 через элемент И 21 поступает на выход 38, сигнализируя тем самым об окончании работы устройства в данном режиме. . Для обеих режимов в случае, когда m и п крайние слева триггеры регистра 2 находятся в единичном сос.тоянии (последнее из формируемых сочетаний при данном п) при поступлении очередного тактового сигнала на выходе последнего элемента И 4 появляется сигнал, который устанавливает триггер 15 в единичное состояние, потенциал с единичного выхода которого подается через замкнутые контакты переключателя 33 на элементы И 19 и 20, управляя их работой. Формула изобретения Устройство для перебора сочетаний содержащее регистр, первую группу т-1 элементов И, вторую группу m элементов И, третью группу т-1 элемен тов И, четвертую группу т-2 элемелтов И, первую группу т-1 элементов ИЛИ, вторую группу т-2 элементов ИЛИ, . группу т-2 элементов задержки, первыЙ элемент И и первый триггер, единичный вход которого подключен к выходу первого элемента И, первый вход которого подключен к выходу первого элемента ИЛИ второй группы и к первому входу первого элемента И четвертой группы, второй вход которого подключен к единичному выходу первого триггера, первый вход i-ro элемента И второй группы (i If 2, ,..., m) подключен к единичному выходу i-ro разряда регис тра и к первому входу j-го элемента И четвертрй группы (j 2, 3, ... m-2), в.ыход i-ro элемента И второй группы {i Ф т) подключен к первым входам t-x элементов И и ИЛИ первьш групп соответственно (1 1, 2, ..„ т-1), второй вход t-ro элемента ИЛИ первой группы подключен к выходу f-r элемента И третьей группы и к первому входу 1+1-го элемента И третьей грзлп пы, второй вход t-ro элемента И третьей группы подключен к нулевому выходу i-ro разряда регистра и к второму входу t-ro элемента И первой группы, выход которого подключен к единичному входу первого разряда регистра, нулевой вход.i-ro разряда ре гистра (i т) подключен к выходу i-ro элемента И второй группы и к первому входу j-ro элемента ИЛИ второй группы, второй вход которого подключен к выходу j-ro элемента заг держки группы, вход которого подклюен к выходу j-t-1-го (j т-3) элемена ИМ второй группы, выход ш-го элеента И второй группы подключен к нуевому входу т-го разряда регистра, вход m-2-ro элемента задержки группы подключен, к нулевому входу т-1-го разряда регистра, отличающееся тем, что, с целью расширения функциональных возможностей за счет обеспечения формиров1ания всех возможных сочетаний из m элементов по п для заданных значений m и п, в него введены группа триггеров, пятая группа т-1 элементов И, шестая и седьмая группы ш элементов И, третья группа т-2 элементов ИЛИ, второй, третий,, четвёртый, пятый, шectoй и седьмой элементы И, первый и второй элементы ИЛИ, второй и третий триггеры, первый и второй элементы НЕ, первый, второй, третий и четвертый элементы задержки, группа m переключателей, переключатель режимов, двухсекционный переключатель, причем входы переключателей группы соединены с первыми единичными входами триггеров группы, единичные выходы которых, кроме ш-го соответственно, соединены с первыми входами элементов И пятой группы и с первыми входами элементов И шестой группы, выходы i-x элементов И четвертой группы (i 1, 2, ,.. m-2) соединеныС вторыми входами i+1-x элементов И четвертой группы и с первыми входами i-x элементов ИЛИ третьей грзшпы, вторые входы i-x элементов ИЛИ третьей группы соединень с выходами i-x элементов И шестой группы, выходы элементов ИЛИ третьей группы соединены с вторыми единичными входами i-x разрядов регистра, выходы ш-1-го и т-го элементов И шестой группы соединены соответственно с информационными входами разрядов регистра, первые входы элементов И седьмой группы соединены соответствённо с единичными выходами разрядов регистра, выходы элементов И седьмой группы являются информационным вьжодом устройства, входы первой секции двухсекционного переключателя в порядке возрастания нЪмеров соединены соответственно с единичными выходами триггеров грзшпыд начиная с первого триггера, выход первой секции двухсекционного переключателя соединен с входом первого элемента НЕ и. с первым входом третьего элемента И, входы второй секции двухсекционного переключателя в порядке возрастания йоме ров Соединены соответственно с едини чными выходами разрядов регистра, на чиная со второго разряда, т-й вход второй секции двухсекционного переключателя соединен с единичным выходом второго триггера, а выход соединен с входом второго элемента НЕ и с первым входом четвертого элемента И, выход первого элементе НЕ соединен с первым входом второгоэлемента,И, вы ход второго элемента НЕ соединен с первым входом пятого элемента И, пер вые входы шестого и седьмого элементов И соединены с входом тактовых сигналов устройства, второй вход шес того элемента И соединен с нулевым выходом третьего триггера, второй вход седьмого элемента И соединен с единичным выходом третьего триггера, выход шестого элемелта И соединен с единичным входом третьего триггера и с первым входом первого элемента ИЛИ выход которого соединен с нулевым входом триггера, с входами сброса разрядов регистра, через первый элемент задержки - с вторыми входами элементов И шестой группы и через второй элемент задержки - с первьм входом второго элемента ИЛИ, выход которого соединен с вторьми входами элементов И седьмой группы, вход начальной установки устройства соединен с нулевым входом третьего триггера, с нулевыми входами триггеров . группы и через третий элемент задержки - с входами переключателей группы, выход седьмого элемента И соединен с вторым входом первого элемента И второй группы, с первым входом первого элемента И третьей группы, с нулевым входом первого триггера и через четвертый элемент задержки - с вторымя входами четвертого и пятого элементов И, выход второго элемента И соединен с вторым входом первого элемента ИЛИ и с вторыми входами элементов И пятой группы, выходы i-x эле-гментов И пятой группы (i 1,2,,.. m-1) соединены соответственно с информационными входами i+1-x триггеров групп выход четвертого элемента И соединен с входом переключателя режимов, -первый выход которого соединен с первым выходом окончания перебора устройства, второй выход соединен с вторыми входами второго и третьего элементов И, выход пятого элемента И соединен с вторым входом второго элемента ИЛИ, выход третьего элемента И является вторым выхо-, дом окончания перебора устройства.

Изобретение относится к вычислительной технике и может использоваться в вычислительных машинах, решаюпщх комбинаторные задачи. Целыо изобретения является расширение функциональных возможностей за счет обеспечения формирования всех возможных сочетаний из 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,