Устройство для перебора сочетаний,размещений и перестановок

 

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

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

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

РЕСПУБЛИК (511 4 G 06 F 15/20 (4 ъгрр

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

Н А BTOPCHOMV СВИДЕТЕЛЬСТВУ

3,. и

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4031689/24-24 (22) 03.03,86.. (46) 30.12.87. Бюл. ¹ 48 (71) Ленинградский электротехнический институт им.В.И.Ульянова (Ленина) (72) Т.В.Волченская и В.С.Князьков (53) 681.3 (088.8) (56) Авторское свидетельство СССР

¹ 643883, кл. G 06 F 15/20, 1977.

Авторское свидетельство СССР № 1124319, кл. G 06 F 15/20, 1983.

ÄÄSUÄÄ 1363232 А1 (54) УСТРОЙСТВО ДЛЯ ПЕРЕБОРА СОЧЕТАНИЙ, РАЗМЕЩЕНИЙ И ПЕРЕСТАНОВОК (57) Изобретение относится к цифровой вычислительной технике и может быть использовано для решения комбинаторских задач. Цель изобретения— повышение быстродействия при генерировании сочетаний путем устранения выборок повторяющихся сочетаний. Устройство содержит две группы регистров 1;1 5 111 11 » ко утатор 2, со40 Фf

13632 держащий группы элементов И 3, — 3 „ и элементы ИЛИ 4„-4 > блок уйравления 5, блок переключателей 6, две группы элементов ИЛИ 7„-7, 9„-9 две группы элементов И 8, -8,12„-12 группу элементов сравнения 11,-11, информационные входы 10,-10, выходы перестановок 14, -l4+, счетчик 15, дешифратор 16, элемент ИЛИ 17, регистр 18 генератор 19 тактовых им32 пульсов, делитель 20, три элемента задержки 21-23, вход 24 начальной установки, выход 25 окончания генерирования, счетчики 26,27, элемент

ИЛИ 28„ выходы сочетаний 35,-35, выход 36. Устройство работает в трех режимах: генерирования перестановок, генерирования размещений и генерирования сочетаний. 1 з.п. ф-лы, 4 табл., .2 ил.

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

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

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

Устройство для перебора сочетаний, размещений и перестановок (фиг,1 и

2) содержат первую группу I,-I . регистров, коммутатор 2, состоящий из групп 3,-3 „ элементов И и элементов

ИЛИ 4 „-4 5, блок 5 управления, блок 6 переключателей, первую группу 7> -7 ,элементов ИЛИ, первую группу 8,-8 q элементов И, вторую группу 9 „-9 элементов ИЛИ, информационные входы устройства 10, "10, вторую группу

I регистров 11, -11, вторую группу 12,—

12 элементов И, группу 13 „-13 элементов сравнения, выходы 14 „-14 перестановок, счетчик 15, дешифратор

16, элемент ИЛИ 17, регистр 18, гене« ратор 19 тактовых импульсов, делитель

20, элементы 21-23 задержки, вход 24 установки начального состояния, выход

25 окончания генерирования, счетчик

26, счетчик 27 и элемент ИЛИ 28, группу 29„-29 элементов И, группу .30 -30 э элементов ИЛИ, элемент ИЛИ

31, триггеры 32,-32, элементы 33 и 33 запрета, последовательно соединенные регистры 34,-34 сдвига (число разрядов в регистре 34 сдвига равно пяти, а в регистре 34 -двум в регистре 34 — трем, в регистре

5 34 э — четырем), выходы 351 в 35< со .четаний устройства, выход 36. Входы и . выходы блока 5 управления (фиг,2) расположены в строгом соответствии с их расположением на фиг.l; коэффи10 циенты пересчета счетчиков 26 и 27— и и (и- 1) соответственно.

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

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

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

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

ll. На .вход 24 подается сигнал уста-, новки в начальное состояние блока 5 и .счетчиков 15, 26, 27, Первый тактовый импульс с выхода делителя 20 производит перепись элементов, т.е. чисел 1,2,3,4,5, из реЗ5,гистра 11 в соответствующие регистры

1 и одновременнд устанавливает единицу на первом выходе блока 5. Благодаря этому задержанный элементом 21 первый тактовый импульс, поступая на

1363232 входы всех группы 3 -3 элементов м

И коммутатора 2, переписывает числа из регистра 1, в регистр 11, из регистра 1 в регистр 11>, из регист5 ра lз в регистр ll, из регистра 1„ в регистр 11, а из регистра 1 в регистр 11,. Задержанный элементами .22 и 23 первый тактовый импульс, поступая на второй и третий входы блока 5, никаких изменений не производит.

Тактовые импульсы с генератора 19 тактовых импульсов, частота которых в и раз выше, чем с выхода делителя

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

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

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

После этого на выходе делителя

20

30

20 появляется второй импульс, который переписывает числа из регистров ll

11 в регистры 1;1 соответственно.

Этот же импульс, проходит на вход регистра 34 и появляется на первом выходе блока 5 управлейия. Происходит аналогичное действие. Получаемые

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

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

34, в исходное состояние, а пройдя через элемент 23 задержки, поступает на третий вход блока 5 и через эле55 перестановки в заданной последовательности представлены в табл.4. 40

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

20 проходит на выход регистра 341 блока 5 и появляется на втором его выходе, переводит в единичное состояние триггер 32 и поступает на вход 45 регистра 34g. мент ИЛИ 31 устанавливает в исходное состояние триггер 32, .

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

13 -13 сравнения ° Сигнал последова5 тельно. появляется на выходах 14

14,, 14, 14» 14 z. Одновременно по сигналам с дешифратора 16 переписываются числа 2, 1,3,4,5 из регистров

11 -11 в регистр 18, Таким образом, параллельная форма представления перестановок в регистрах 11,-11 преобразуется в последовательную фор;му в регистре 18 и пространственновременную форму последовательности появления сигналов на выходах 14, - .

14 элементов 1.3, — 13> сравнения .

После перебора всех 120 перестановок на выходе 25 регистра 34 < появляется сигнал окончания работы.

2. Генерирование размещений.

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

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

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

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

3. Генерирование сочетаний.

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

5 ментов И 8,-8 . Начальная установка такая же, как и в режиме генерирования перестановок. Переключателем 6 задается число элементов из общего числа, которые должны участвовать в формировании сочетаний, например, если замкнут первый контакт переключателя, то формируются сочетания из

5 по 4 если второй — из 5 по 3 есЭ У

10 ли третий — из 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. 25

Таким образом, предлагаемое устройство для перебора сочетаний, размещений и перестановок позволяет при формировании сочетаний значительно сократить время вычислений, а именно: З0 при формировании сочетаний из 5 по

2 и из 5 по 3 — в 5 раз, а при формировании сочетаний из 5 по 4 — в

24 раза.

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

l.Óñòðoéñòâo для перебора сочетаний> размещений и перестановок, содержащее две группы регистров, блок управления, блох переключателей, группу элементов сравнения, делитель, 40 три элемента задержки, первый счетчик, дешифратор, две группы элементов ИЛИ, две группы элементов И и первый элемент ИЛИ, причем информационные входы коммутатора соединены 45 с выходами регистров первой группы и с первыми входами элементов И первой группы, вторые входы которых. соединены с выходами элементов ИЛИ первой группы, второй вход последне- 50 го элемента И первой группы соединен с первым выходом блока переключателей и первыми входами элементов ИЛИ первой группы, вторые и третьи входы которых соединены с вторым и третьим выходами блока переключателей, выходы элементов И первой группы являются выходами сочетаний устройства, тактовый вход которого соединен с тактовым входом первого счетчика и входом делителя, выход которогб соединен с входами разрешения приема регистров первой группы, первым входом блока управления и входом первого элемента задержки, выход которого соединен с входом второго элемента задержки, выход которого соединен с вторым входом блока управления и входом третьего элемента задержки, выход которого соединен с третьим входом блока управления, четвертый вход которого соединен с входом установки начального состояния устройства и входом установки первого счетчика, выход которого соединен с входом дешифратора и первыми входами элементов сравнения группы, вторые входы которых соединены с ин. формационными входами регистров первой группы, первыми входами элементов И второй группы и выходами ре . гистров второй группы, входы которых соединены с выходами элементов ИЛИ второй группы, первые входы которых соединены с информационными входами устройства, выходы перестановок ко.l торого соединены с выходами элементов сравнения группы, выходы дешифратора соединены с вторыми входами элементов И второй группы, выходы которых соединены с входами первого элемента ИЛИ, выход которого соединен с входом регистра, выход которо о является выходом устройства, выход окончания генерирования которого. соединен с первым выходом блока управления, второй, третий, четвертый и пятый выходы которого соединены с одноименными управляющими входами коммутатора, выходы которого соединены с соответствующими входами элементов ИЛИ второй группы, о т л и— ч а io щ е е с я тем, что, с целью увеличения быстродействия при формировании сочетаний путем исключения выборок повторяющихся сочетаний, в него введены второй элемент ИЛИ и второй и третий счетчики с коэффициФ ентом пересчета (n-1) 1 и и соответственно (п-количество элементов перебора), причем выход делителя соединен с входами блока переключателей, первый выход которого соединен со счетным входом второго счетчика, вход сброса которого соединен с входом установки начального состояния устройства и входом сброса третьего

1363232

Таблица 1

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

Входы Входы элементов ИЛИ Входы элементов И татора 1 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11

1 1

1 2 2

3 2

2 3 4

Таблица 2

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

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

1 2 3 4 5 6 7 8 9 10 ll

Выходы счетчика, счетный вход которого соединен с выходом второго элемента ИЛИ, первый и второй вхо ды которого соединены с вторым

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

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

1363232

Т а блица 3

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

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

EEI I 111 !

1 2 3 4 5 6 7 8 9 1О 11 2

2 l

Таблица 4

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

1 5 4 3 2 2 5 4 3 1 2 5 4 1 3 3 5 4 1 2 3 5 4 2 1

2 1 5.4. 3 2 5 4 3 3 2 5 4 2 3 5 4 1 1 3 5 4 2

3 2 1 5 4 3 1 2

4 3 2 1 5 4 3 1

5 4 3 2 1 5 4: 3 1 2 5 4 1 3 .2 5 4 1 2 3. 5 4 2 1 3

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

ИЛИ

5 4 1 3 2 5 4 1 2 3 5 4 2 1 3 5 4

2 5 4 1 3 2 5 4 2 3 5 4 2 1 3 5

1363232

ЧЬ2. Z

Составитель О.Березикова

Техред М.Дидык

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

Корректор M-немчик

Тираж 671

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

113035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 6364/42

Подписное

П ои роиэводственно-полиграфическое предприятие, v.Óæãîðîä, ул.Проектная, 4