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

 

Изобретение относится к вычислительной технике и может быть использовано для решения комбинаторных задач при построении специализированньгх вычислительных устройств. Цель изобретения - расширение функциональных возможностей путем формирования сочетаний из N элементов по К, где , и задания автоматического режима полного перебора всех N перестановок . Указанная цель достигается тем, что в устройство, содержащее два регистра 1,2 сдвига N регистров 3 чисел, где N - количество элементов перестановок, реверсивный кольцевой регистр 4 сдвига, N-1 ключей 5, N-3 элементов ИЛИ 14, генератор 7 тактовьгх импульсов и элемент 8 задержки , введены бЛок 9 управления, две группы переключателей 10, 11, К-1 элементов ИЛИ 12 и К групп элементов И 13. 1 з.п. ф-лы, 2 ил., 1 табл. с S сл со о со ьо 00 со

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

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

РЕСПУБЛИК (д1) 4 G 06 F 15/31

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

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

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

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

У 1124319, кл. G 06 F 15/20, 1983.

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

11 - 1180917, кл. G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ ГЕНЕРИРОВАНИЯ

ПЕРЕСТАНОВОК И СОЧЕТАНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано для решения комбинаторных задач при построении специализи„„SU„„1363239 А 1 ров анных вычислит ельных устройств .

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

К, где K(N, и задания автоматического режима полного перебора всех N перестановок. Указанная цель достигается тем, что в устройство, содержащее два регистра 1,2 сдвига N регистров

3 чисел, где N — количество элементов перестановок, реверсивный кольцевой регистр 4 сдвига, N-1 ключей 5, N-3 элементов ИЛИ 14, генератор 7 тактовых импульсов и элемент 8 задержки, введены блок 9 управления, две группы переключателей 10, ll

К-1 элементов ИЛИ 12 и К групп элементов И 13. 1 з.п. ф-лы, 2 ил., 1 табл.

1363239 2

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

Целью изобретения является расширение функциональных возможностей устройства путем обеспечения формирования сочетания из N элементов по

К, где K

На фиг.1 показана блок-схема устройства для N = 4, К = 2,3> на фиг.2 -1, функциональная схема блока управления.

Устройство содержит (фиг.1) два регистра 1 и 2 сдвига, регистры 3 числа, реверсивный кольцевой регистр

4 сдвига, ключи 5, элементы ИЛИ 6, генератор 7 тактовых импульсов, элемент 8 задержки, блок 9 управления, первую группу 10 переключателей, вторую группу 11 переключателей,до- 25 полнительные элементы ИЛИ 12, группы 13 элементов И.

:. Устройство имеет выходы 14 перестановки, выходы 15 сочетания, вход

16 начальной установки, выход 17 Зр признака окончания работы.

Блок 9 управления содержит регистры 18 сдвига, группу 19 триггеров, группу 20 элементов запрета, группу

21 элементов И, группу 22 элементов

ИЛИ, два элемента 23,24 задержки и элемент ИЛИ 25.

Блок 9 управления имеет тактовый

26 вход, выход 27 признака окончания работы, выходы 28, вход 29 начальной 4р установки.

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

Генерирование перестановок. Переставляемые числа находятся в регист- 45 рах 3 числа и считываются по выходам

14, Передача чисел от одного регистра к другому производятся через ключи 5. При наличие сигнала на первом (втором) управляющем входе ключа 5р он пропускает на выход число с первого (второго) информационного входа.

Генерирование перестановок может происходить в двух режимах: первый режим — задание произвольного чередования перестановок (замкнут первый переключатель группы 11; второй режим — автоматически производится полный перебор всех возможных перестановок из N !замкнут второй переключатель группы 11).

Режим <1.Все ключи управляются сигналами с выходов реверсивного регистра 4 сдвига. При этом в реверсивном кольцевом регистре 4 сдвига содержится только одна "1", т.е, сигнал су-. ществует только на одном из выходов реверсивного кольцевого регистра 4 сдвига. Для рассматриваемого случая, когда N = 4, используется трехразрядный реверсивный кольцевой регистр 4 сдвига.

При наличии сигнала на первом выходе реверсивного кольцевого регистра 4 сдвига все ключи 5 открыты по первому управляющему входу и из регистров 3 числа образуется кольцо, которое обозначим К!.

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

Вследствие этого из регистра 3 числа образуется кольцо, которое обозначим К2.

При наличии сигнала на третьем выходе регистра 4 первый и второй ключи 5 закрыты, а третий ключ открыт по второму управляющему входу. Вследствие этого из регистров числа образуется кольцо, которое обозначим

КЗ.

Выбирая то или иное кольцо, т.е.формируя сигнал на том или инбм выходе реверсивного кольцевого регистра 4 сдвига, можно осуществлять заданную перестановку чисел.

Управление реверсивным кольцевым регистром 4 сдвига осуществляется кодами, заносимыми в регистры 1 и 2 сдвига. Эти коды задают характер перестановок, В качестве примера в таблице приведена частная последовательность перестановок, соответствующая ей последовательность состояний реверсивного кольцевого регистра

4 сдвига и первоначальных кедов в регистрах 1 и 2 сдвига.

Режим 2. Все ключи управляются сигналами с выходов блока 9 управления. Если необходим полный перебор всех перестановок, а также при большом значении N задание частной последовательности перестановок кодами регистров 1 и 2 сдвига трудоемко, за-.

Код в регистрах

1 2

1234

010

1423

010

001

1432

2143

100

2314

010

100

4231

4123

010

4132

001

2412

100

010

2341

2134

010

0.4213

100

4321

010

001

4312

100

2431

1243

100

100

3124 .

3412

010 з 1363239 4 мыкание второго переключателя второй - первый регистр. сдвига имеет четыре группы 11 задает автоматический ре- разряда), на вход второго регистра жим. 18 сдвига, устанавливает в "1" пер5

Предварительно по входу 29 началь- вый триггер 19 и, пройдя через эленой установки в блоке 9 управления менты И 2! и ИЛИ 22, устанавливает происходит сброс в "0" регистров 18 в "0" первый регистр 18 сдвига. сдвига и триггеров 19. Четвертый тактовый импульс, пройПервый тактовый импульс поступает дя через алементы 23 и 24 задержки на вход первого регистра 18 сдвига 10 и элемент ИЛИ группы 22 устанавливаи появляется на первом выходе блока ет в "0" первый триггер 19. ключа 5. Происходит перестановка К1. Сигнал, появившийся на втором выБторой.и третий тактовые импульсы ходе блока 9 управления, соединенном производят аналогичные действия. с вторым входом третьего, ключа 5, Четвертый тактовый импульс прохо- 15 производит перестановку КЗ. дит на выход первого регистра 18 Пример частной последовательности сдвига (так как для случая и = 4 перестановок.

Перестановка Состояние регистра 4 сдвига

1363239

Продокл;«нп« таблицы

Код в регистрах

Состояние регистрра 4 сдвига

Перестановка

1 2

3421

1 0

001

3142

010

3214

010

3241

001

1324

100

1342

001

Пятый, шестой и седьмой тактовые импульсы производят перестановку Kl (аналогично первому, второму и третьему тактовым импульсам).

Восьмой тактовый импульс с выхода второго регистра 18 сдвига, имеющего два разряда, проходит на вход третьеro регистра 18 сдвига, появляется на третьем выходе блока 9 управления и производит перестановку К2. Через элемент запрета группы 20 сигнал с второго выхода блока 9 управления устанавливает "1" второй триггер 19, сигнал с выхода которого через вторые элементы И и ИЛИ групп 21 и 22 устанавливает в "0" второй регистр

18 сдвига.

Восьмой тактовый импульс, пройдя через элементы 23 задержки и первые элементы И и ИЛИ групп 21 и 22, устанавливает в "0" первый регистр 18 сдвига, а пройдя через элементы 24 задержки и 22 ИЛИ, сбрасывает первый триггер 19 в "0".

Последующие тактовые импульсы повторяют работу, описанную, выше, Двадцать четвертый тактовый им-. пульс появляется на выходе 17 признака окончания работы, так как в данном случае количество всех перестановок при N = 4 равно N! = 24.

Генерирование сочетаний, При генерировании сочетаний информация считывается с выходов 15 сочетания. Исходная установка такая же, как и в режиме генерирования. перестановок.

Переключателями 10 первой группы

;задается число элементов из общего числа, которые должны участвовать в формировании сочетаний, Например, если замкнут первый переключатель первой группы 10, то формируются сочетания 2 и 4, если замкнут второй, то формируются сочетания 3 и 4.

Режим работы задается переключателями второй группы ll как и при формировании перестановок. В автоматическом режиме перебора все сочетания

30 из 1.no K, где К = Й вЂ” 1, формируются за N тактов работы.

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

l.устройство для генерирования пе35 рестановок и сочетаний, содержащее два регистра сдвига, N регистров числа (где N — количество элементов перестановок), реверсивный кольцевой регистр сдвига, (М-1) ключей, (М-3) элементов ИЛИ, генератор тактовых импульсов и элемент задержки, причем выходы первого и второго регистров сдвига подключены соответственно к входам сдвига вправо и влево реверсивного кольцевого регистра сдвига, первый выход которого подключен к управляющему входу первого ключа, к первому управляющему входу второго

5 ключа и к первому входу первого элемента ИЛИ, второй вход которого подключен к второму управляющему входу второго ключа и к второму выходу реверсивного кольцевого регистра сдвига, выход элемента задержки соединен с -синхровходами всех регистров числа, выход i-ro регистра числа (11,й-2) подключен к первому информационному входу (1+1)-ro ключа, 7 13Ь выход которого соединен с информационным входом (1+1)-го регистра числа, выход (М-1)-го регистра числа подключен к информацинному входу .N-го регистра числа, выход которого соЕдинен с вторыми информационными входами с второго по (N-1) -й ключей и с информационным входом первого ключа, выход которого подключен к информационному входу первого регистра числа, выход j-ro элемента ИЛИ (j = 1, N-З) подключен к первому управляющему входу (j+2)- ãî ключа и к первому входу (j+1 )-го элемента

ИЛИ, второй вход которого подключен к ()+2)-му выходу реверсивного кольцевого регистра сдвига, выход (N-3)"

ro элемента ИЛИ соединен с первым управляющим входом (М-2)-го ключа, (i+1)-й выход реверсивного кольцевого регистра сдвига подключен к второму управляющему входу (i+1)-го ключа, выходы регистров числа являются соответствующими выходами перестановки устройства, о т л и ч а ю щ е е с я тем, что, с целью ресширения функциональных возможностей устройства путем обеспечения формирования сочетаний из М элементов по К, где KlN, а также возможности задания автоматического режима полного перебора всех

М перестановок, устройство содержит блок управления, две группы переключателей, (К =1) дополнительных элементов ИЛИ и К групп элементов И, причем входы переключателей первой группы соединены с выходом эле-, мента задержки, выход (К -1)-ro переключателя первой группы соединен с первыми входами элементов И К-й группы и с первым входом (К-1)-го дополнительного элемента ИЛИ, выход (К-2)-го переключателя первой группы подключен к второму входу (К-1)-го дополнительного элемента ИЛИ, выход которого соединен с первыми входами элементов И (К-1)-й группы и с первым входом (К-3)-ro дополнительного элемента ИЛИ, выход первого переключателя первой группы соединен с вторым входом первого дополнительного элемента ИЛИ, выход которого соединен с первыми входами элементов И первой и второй групп, вторые входы элементов И групп подключены к выходам соответствующих разрядов первых К регистров числа соответственно, а выходы элементов

1r

55 управления, вход начальной установки которого является входом установки устройства, первый выход блока управления подключен к управляющему входу первого ключа, а выходы с второго по (N-1)-й блока управления подключены соответственно к вторым управляющим входам ключей с (М-1)-го по второй, N-й выход блока управления является выходом признака окончания работы устройства.

2. Устройство по п.l, о т л и— ч а ю щ е е с я тем, что блок управления содержит (N-1) регистров сдвига, группу из (М-2) триггеров, группу из (N-3) элементов запрета, группу из (N-2) элементов И, группу из (N-2) элементов ИЛИ, два элемента задержки и элемент ИЛИ, причем первый регистр сдвига содержит М разрядов, а каждый следующий — на единицу меньше, тактовый вход блока подключен к входу сдвига первого регистра сдвига, выход i-го регистра сдвига (i-1,N- 2) соединен с входом сдвига (i+1)-го регистра сдвига, выход (М-1)-го регистра сдвига является

N-м выходом блока, вход начальной установки блока управления подключен к первому входу элемента ИЛИ, первым входам элементов- ИЛИ группы и входу установки в "0"(N-1)-ro регистра сдвига, выход первого разряда первого регистра сдвига является первым выходом блока, выход i-го регистра сдвига (i-1, М-3) соединен с входом установки в "1" i-го триггера группы и первым входом i-ro элемента запрета группы. входы с второго по К-й которого (г де i + К = N - 1) подключены к входам соответственно с (i + 1)-го по (1+K-1)-й регистров сдвига, выход

I-го элемента запрета является (i

И 1-й группы (1-К) являются соответствующими 1-ro выхода сочетания устройства, выход генератора тактовых

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

10 второй группы — к входу элемента задержки и к тактовому входу блока

Составитель И.Захаревич

Техред N.Äèäûê

Корректор М.Пожо

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

Тираж 671

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

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

Заказ 6364/42

Подписное

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

9 1363239 10 подключен к первому входу i-го эле- динен с вторыми входами элементов мента И группы, выход которого соеди И группы и входом второго элемента нен с первым входом 1-ro элемента задержки, выход которого соединен

;ИЛИ группы, выход которого подключен 5 с вторым входом элемента ИЛИ, к входу установки в "0" i-го ре- выход которого соединен с вхогистра сдвига, тактовый вход блока дами установки в "0" триггеров ,через первый эпемент задержки сое- группы.