Устройство для перебора сочетаний, перестановок и размещений Советский патент 1988 года по МПК G06F7/06 

00 00 00 00 00

|

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

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

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

Устройство содержит генератор 1 тактовых импульсов, блок 2 формирования перестановок, блок 3 формирования сочетаний, п узлов 4 выделения первой единицы, каж,ць1й из которых состоит из группы 5 элементов ИЛР1 и группы 6 элементов И, п- групп 7 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и п элементов И-ИЛИ 8, выходы 9,

Принцип работы устройства состоит в следующем.

В режиме перебора перестановок сигналы снимаются с выходов блока 2 формирования перестановок. При этом очередность появления импульса в пределах каждой серии из п тактовых импульсов на выходах блока 2 определяет каждую новую перестановку. Так,, при формировании перестановок из 3-х элементов каждая серия из 3-х тактовых импульсов формирует последова- тельно&:ть импульсов на выходах блока 2 в таком виде: 1,2,3; 2,1,3; 2,3,1; 3,1,2; 1,3,2, т.е. приведен гые последовательности означают, что в первой последовательности первый импульс появляется на первом выходе,- второй- на ртором и третий - на третьем, во второй последовательности первый импульс появляется на втором выходе, второй - на первом и третий - на третьем и т.п.

В режиме перебора сочетаний сигналы снимаются с выхода блока 3. При этом перебор сочетаний из п по m означает, что перебираются такие всевозможные комбинации, в которых на m выходах.блока 3 будут 1, а на n-m выходах - О. .Так, всевозможными сочетаниями из А по 2 будут следующие комбинации: 1100, 1010, 0110, 1001, 0101,.001 К

0

5

0

5

0

5

0

5

0

5

В режиме ереборп рятмеш€ чнй устройство рлботяот следуилцим ( бразом.

Сигналы в этом с.пучле снимаются с вь:ходов 9. Блоком 3 формирования сочетаний выбирается сочетание элементов И-И.11И 8, а блок 2 формирования перестановок осуществляет все перестлповкн очередности появления им|тульсов на выходах выбранных элементов И-ИЛИ 8. Например, формирование размещений из 4 по 3 осуществляется следующим образом. Предложим, что в блоке 3 зафиксирована такая комбинация единичных сигналов на его выходах - 1101. Первый узел 4 выделения первой единицы и все последующие узлы 4 совместно с соединенными с ними группами 7 элементов ИСК. ПОЧАЮ- 1ДЕЕ ИЛИ осуществляет расслоение сочетаний, т.е. на выходах соответствующих узлов 4 появляются унитарные коды. Так, для рассматриваемого случая на выходах первого узла 4 зафиксируется код 1000. Этот код поступает на входы 1-й группы 7 элементов ИСЮПОЧЛЮЩЕЕ ИЛИ, на другие входы которых поступает полное сочетание с выходов блока 3. Поэтому через первый элемент ИСКЛЮЧАЮЩЕЕ ИЛИ единичный сигнал не проходит и на входы второго узла 4 поступает код 0101. В свою очередь, элементы Ш1И 5 и 6 второго узла 4 вьщеляют только первую 1 этого кода, а остальные просеивают. Поэтому на выходах второго узла 4 появляется код 0100. Этот код и код 0101 с выходов элементов ИCK. ИЛИ 7 первой группы поступают на входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 2-й группы. Поэтому на выходе 3-го узла 4 появляется код 0001. На выходах 4-го узла 4 формируется нулевой код 0000. Таким образом, единичные сигналы присутствуют на 2-м входе первого элемента И-ИПИ, на 4-м входе второго элемента И-1ШИ и на 6-м входе четвертого элемента И-ИЛИ. Последовательность перестановок, формируемая на выходах блока 2 в виде очередности появления импульсов в каждой серии из 3-х импульсов, проходит на выходы 1-го, 2-го и 4-го элементов И-ИЛИ. Эта последовательность имеет вид: 1,2,4; 2,1,4; 2,4,1; 4,2, 1; 1,4,2. После -перебора всех щести перестановок при сочетании 1101 с выхода блока 2 на блок 3 поступает сигнал, по которому в нем формируется сочетание 1011, Поэтому в слудую- щем цикле перебора перестановок единичные сигналы в соответствующем порядке появляются на выходах 1-го, 3-го и Д-го элементов И-НЛИ. Так происходит до тех пор, пока не переберутся все. размещения .и на выходе блока 3 не появится сигнал окончания перебора.

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

Устройство для. перебора сочетаний, перестановок и размещений, содержащее блок формирования перестановок и.п групп элементов И, причем тактовый вход устройства соединен с тактовым входом блока формирования перестановок, отличающееся тем, что, с целью повышения быстродействия при формировании сочетаний и размещений, оно содержит блок формирования сочетаний, п групп элементов ИЛИ (п - число элементов перебора) , п-1 групп элементов ИСКТПОЧАЮЩЕЕ ИЛИ и п элементов И-ИЛИ, причем выход признака окончания формирования перестановок блока формирования перестановок, соединен с входом запуска блока формирования сочетаний, выход

признака окончания формирования сочетаний которого является одноименным выходом устройства, выходы размещений которого соединены с выходами элементов И-ШШ, (2К-1)-е входы которых (, п) соединены с К-м выходом блока формирования перестановок, 2К-Й вход (i-ro элемента И-ИЛИ (i

1, п) соединен с выходом i-ro элемента И К-й группы, выход 1-го элемента j-и группы (, п-1) соединен с иервым входом i-ro элемента ИСКЛЮЧАЮЩЕЕ ШШ 1-й группы (, п), второй вход i-ro элемента ИСКЛЮЧАЮЩЕЕ ИЛИ р-й группы (, п) соединен с выходом i-ro элемента ИСКЛЮЧАЮЩЕЕ ИПИ предыдущей группы, второй вход i-ro элемента ИСКЛЮЧАЩЕЕ ИЛИ

первой группы соединен с 1-м выходом блока формирования сочетаний и с соответствующими входами элементов ИЛИ первой группы и элементов И первой группы, выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1-й группы соеди- iBH с соответствующими входами элементов ИЛИ и первыми входами элементов И 1-й группы, вторые входы которых соединены с выходами элементов

ИЛИ 1-й группы.

Изобретение относится к вычислительной технике и позволяет значительно повысить быстродействие при формировании сочетаний и размещений. Устройство содержит генератор I тактовых иь1пульсов, п узлов 4 выделения первой едини1Уз1, каждый из которых состоит из группы 5 элементов ИЛИ и группы 6 элементов И, п - 1 групп 7 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и п элементов И-ИЛИ 8, выходы 9. В режиме перебора перестановок сигналы снимаются с выходов блока 2 формирования перестановок, в режиме перебора сочетаний сигналы снимаются с выходов блока 3 формирования сочетаний,в режиме перебора размещений сигналы снимаются с выходов 9. Блоком 3 выбирается сочетание элементов И-ИПИ 8, а блок 2 осуществляет все перестановки очередности появления импульсов на выходах выбранных элементов И-ИЛИ 8. 1 ил. 1C (Л