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

держащий группы элементов И 3 - 3 , и элементы ИЛИ f , блок управления 5, блок переключателей 6, две группы элементов ИЛИ 1 -1- , , две группы элементов И , группу элементов сравнения 1Ц-11, информационные входы 10,-10 j, выходы перестановок i, , счетчик 15, дешифратор 16, элемент РШИ 17, регистр 18, генератор 19 тактовых имИзобретение относится к цифровой вычислительной технике и может быть использовано для решения задач комбинаторного характера.

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

На|фиг.1 приведена функциональная схема устройства для перебора сочетаний, размещений и перестановок для случая пяти переставляемых элементов; на фиг.2 - функциональная схема блока управления.

Устройство для перебора сочетаний, размещений и перестановок (фиг. и 2) содержат первую группу li-l/ регистров, коммутатор 2, состоящий из групп ,, элементов И и элементов ИЛИ 4,-45, блок 5 управления, блок 6 переключателей, первую группу ,

.элементов ИЛИ, первую группу элементов И, вторую группу элементов ИЛИ, информационные входы устройства , вторую группу регистров llj-llj, вторую группу 12 ;125 элементов И, группу элементов сравнения, вьгходы ,. перестановок, счетчик 15, дешифратор

16, элемент ИЛИ 17, регистр 18, генератор 19 тактовых импульсов, делитель 20, элементы 21-23 задержки, вход 24 установки начального состояния, выход 25 окончания генерирования, счетчик 26, счетчик 27 и элемент ИЛИ 28, группу ,, элементов И, группу

элементов ИЛИ, элемент ИЛИ 31, триггеры 32 ,-32, элементы 33 и 33 «i запрета, последовательно соепульсов, делитель 20, три элемента задержки 21-23, вход 24 начальной установки, выход 25 окончания генерирования, счетчики 26,27, элемент ИЛИ 28, выходы сочетаний 35i-35, выход 36. Устройство работает в трех режимах: генерирования перестановок, генерирования размещений и генерирования сочетаний. -1 з.п. ф-лы, 4 табл .2 ил.

диненные регистры сдвига (число разрядов в регистре 34, сдвига равно пяти, а в регистре 34 -двум, в регистре 342 - трем, в регистре 5 34 э - четырем), выходы 35,- 35 .со- .четаний устройства, выход 36. Входы и -ВЫХОДЫ блока 5 управления (фиг.2) расположены в строгом соответствии с их расположением на фиг.1; коэффи- 0 циенты пересчета счетчиков 26 и 27 - п и (п-1) соответственно.

Описание соединений и генерируемые перестановки приведены в табл. 1-4.

5 Устройство для перебора сочетаний, размещений и перестановок может работать в трех режимах: генерирование перестановок, генерирование размещений и генерирование сечетаний.

0

1. Генерирование перестановок. -

Для генерирования перестановок по входам 10 в регистрах II записываются исходные элементы, например числа 1,

5 2,3,4,5, причем запись этих чисел в регистры может производиться в любом порядке. Для удобства будем считать, что числа записаны в возрастающем порядке, начиная с верхнего регистра

011. На-вход 24 подается сигнал уста-, новки в начальное состояние блока 5 и счетчиков 15, 26, 27.

Первый тактовый импульс с выхода делителя 20 производит перепись элементов, т.е. чисел 1,2,3,4,5, из ре5 гистра 11 в соответствующие регистры 1 и одновременнЬ устанавливает единицу на первом выходе блока 5. Благодаря этому задержанный элементом 21 первый тактовый импульс, поступая на

входы всех группы

13632324

мент ИЛИ 31 устанавливает в исходное состояние триггер 32.

Далее аналогичным образом по так товым импульсам.генератора 19 начинается сравнение чисел в элементах 13 -13j сравнения. Сигнал последовательно, появляется на выходах , ,22 и 23 первый тактовый импульс, поэлементов

И коммутатора 2, переписывает числа из регистра регистра 1 .

1 в регистр 112 J из в регистр Па, из регистра 13 в регистр 11, из регистра 1 в регистр HS а из регистра 1 у в регистр 11,. Задержанный элементами

з f Одновременно по сигналам с дешифратора 16 переписываются числа 2, 1,3,4,5 из регистров 11 -11 у в регистр 18о Таким образом, параллельная форма представления перестановок в регистрах преобразуется в последовательную фор- ;му в регистре 18 и пространственно-

ступая на второй и третий входы бло- ка 5, никаких изменений не производит.

Тактовые импульсы с генератора 19 тактовых импульсов, частота которых в п раз выше, чем с выхода делителя 20 (п-число элементов в перестановках) , поступая на вход счетчика 15, суммируются. Так как выходы счетчика 15 соединены со всеми элементами

13, при поступлении каждого тактового импульса на этот счетчик в одном из элементов 13 сравнения происходит сравнение кодов счетчика 15 и соответствующего регистра 11. На выходе 14 того элемента 13 сравнения, где произошло совпадение, появляется сигнал, кроме того, производится перепись содержимого соответствующего регистра 11 через элементы И 12 и ИЛИ 17 на выходной регистр 18.

После этого на выходе делителя 20 появляется в торой импульс, которы переписьтает числа из регистров 11 5 в регистры 1 -1 g соответственно. Этот же импульс,проходит на вход регистра 34 и появляется на первом выходе блока 5 управления. Происходит аналогичное действие. Получаемые перестановки в заданной последовательности представлены в табл.4.

Пятый импульс с выхода делителя

20проходит на выход регистра 34i блока 5 и появляется на втором его выходе, переводит в единичное состояние триггер 32 и поступает на вход регистра 34 j,.

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

21перёписьшает числа 2,3,4,5,1 из регистра Ij в регистры 11 llj (соответственно 2,1,3,4,5). Этот же импульс, пройдя через элемент 22 задержки, поступает на второй вход блока 5 и через открытый элемент И 29

и элемент ИЛИ 30 сбрасывает регистр 34 в исходное состояние, а пройдя через элемент 23 задержки, поступает на третий вход блока 5 и через эле

Далее аналогичным образом по так товым импульсам.генератора 19 начинается сравнение чисел в элементах 13 -13j сравнения. Сигнал последовательно, появляется на выходах ,

Q

s

0

з f Одновременно по сигналам с дешифратора 16 переписываются числа 2, 1,3,4,5 из регистров 11 -11 у в регистр 18о Таким образом, параллельная форма представления перестановок в регистрах преобразуется в последовательную фор- ;му в регистре 18 и пространственно- /

временную форму последовательности появления сигналов на выходах 14, - . 145 элементов 1.3,,- 13 сравнения.

5

0

элементов

После перебора всех 120 перестановок на выходе 25 регистра 34 + появляется сигнал окончания работы. 2. Генерирование размещений. При генерировании размещений работа не отличается от режима генерирования перестановок. Различие заключается лишь в том, что перед началом работы числа, отличные от нуля, нужно занести не во все регистры 11, а лишь в некоторые. Так, например, при генерировании размещений из 5 по 2 в любые два регистра необходимо записать числа, отличные от нуляоСрав- нение чисел происходит лишь в тех

5 элементах 13 сравнения, на которые поступают из регистров 11 не нулевые числа. Поэтому за каждый цикл пересчета счетчиком 15 тактовых импульсов с генератора 19 сигнал появляет0 ся на выходах только двух схем 13 , сравнения из пяти. Поскольку числа в регистрах 11 в каждом цикле меняются, то к моменту появления сигнала конца работы устройства (на выходе 25 блока

5 5) перебираются всевозможные комбинации пар элементов 13 сравнения, в которых происходит сравнение чисел, и на соответствующих выходах 14 появляются сигналы. Все эти комбинации пар элементов сравнения являются размещениями из 5 по 2. Таким образом, получаем все размещения из 5 по 2 в форме пространственно-временной последовательности появления сигналов на выходах 14,

0

5

3, Генерирование сочетаний, В режиме генерирования сочетаний информация снимается с выходов эле-

ментов И . Начальная установка такая же, как и в режиме генерирования перестановок. Переключателем 6 задается число элементов из общего числа, которые должны участвовать в формировании сочетаний, например, если замкнут первый контакт переключателя, то формируются сочетания из 5 по 4, если второй - из 5 по 3, если третий - из 5 по 2. В табл.4 все .сочетания из 5 по 2 обведены тонкой линией в кружок (1.2, 1.3, 1.4, 1.5, 2,3, 2„4, 2.5, 3.4, 3.5, 4.5), а все сочетания из 5 по 3 отмечены (1.2„3, 1.2..4, 1о2„5, 2.3.5, 2.4.5, 3.4.5, 1.3.4, 1.4.5, 1.3„5)„ Сочетания из 5 по 4 расположены в первых пяти столбцах (1.2.3.4, 1.2„3.5, 1.3.4„6, 2.3.4.5, 1.2.4.5).

Сигналом окончания работы служит сигнал 25, который поступает на выход со счетчика 26 при формировании сочетаний из 5 по 2 или со счетчика 27 при формировании сочетаний из 5 по 4.

Таким образом, предлагаемое устройство для перебора сочетаний, размещений и перестановок позволяет при формировании сочетаний значительно сократить время вычислений, а именно: при формировании сочетаний из 5 по 2 и из 5 по 3 - в 5 раз, а при формировании сочетаний из 5 по 4 - в 24 раза.

Формула изобре н и я 1.Устройство для перебора сочетаний, размещений и перестановок,содержащее две группы регистров, блок управления, блотс переключателей.

10

15

20

25

30

35

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

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

чик, дешифратор, две группы элементов ИЛИ, две группы элементов И и первый элемент ИЛИ, причем информационные входы коммутатора соединены с выходами регистров первой группы и с первыми входами элементов И первой группы, вторые входы которых- соединены с выходами элементов ИЛИ первой группы, второй вход последнего элемента И первой группы соединен с первым выходом блока переключателей и первыми входами элементов ШШ первой группы, вторые и третьи входы

45

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

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

5

0

5

0

5

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

40 пятый выходы которого соединены

45

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

7 .

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

2. Устройство по П.1, о т л и.- чающееся тем, что коммутато

Описание соединений в коммутаторе между входами коммутатора и входами элементов ИЛИ и И групп

коммутатора

Таблица 2

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

Выходы

элементов

ИЛИ

Выходы элементов И

n ZrillllllHIIiLE

1

2 3 4 5

8

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

Таблица 1

Т а б л и ц а 3

Описание соединений между выходами элементов И группы коммутатора и входами элементов ИЛИ второй группы .

Выходы элементов И элементов

:..... J IiriEMIiEDZI iZZ

13 .2

2123

3123

421

S .

.

.Табдица4

Генерируемые перестановки

-к-

15432254312541335412 3 542 1

2154 3 1 2 543325 4 1235 41 135 42

321 5-4 31 254 1 3 2 5 4 123 5 421 3 5 4

4321543 1254 13254 1 23 5 421 35

5432 1 5 431 254132541 2354213

Изобретение относится к цифровой вычислительной технике и может быть использовано для решения комби- наторских задач. Цель изобретения - повышение быстродействия при генерировании сочетаний путем устранения выборок повторяющихся сочетаний. Устройство содержит две группы регистров 1,-1 J ,11 -1 1 J, ко1 утатор 2, со- tifi i (Л со 05 оо ю

Редактор А.Маковская

Составитель О.Береэикова Техред М.Дидык

Заказ 6364/42тираж 671

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектн1; 4

Корректор М.Демчик

Подписное