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

 

Изобретение относится к автоматике и вычислительной технике. Целью изобретения является расширение области применения за счет вычисления номера перестановки. Изобретение впервые реализует непосредственньй алгоритм вычисления номера перестановки по ее кодированному представлению и позволяет значительно сократить время поиска нумерованных объектов при одновременном уменьшении обьемов памяти, необходимых для хранения элементов изображений. Устройство для нумерации перестановок содержит входную информационную шину 1 из (п-1)-й кодовой группы для подключения всех кодов элементов перестановки степени п, кроме нулевого, (п-2) блока понижения степени перестановки 2, () умножителей 3 на константу, многовходовый сумматор 4, выходную информационную шину 5 номера перестановки . 2 ил. (О (Л

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

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

РЕСПУБЛИН

1 А1 (19) (И) (51)4 G 06 F 15/20

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

H А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4175932/24-24 (22) 05 ° 01.87 (46) 23.08.88. Бюл. № 31 (71) Институт кибернетики им.В.M.ÃëóøêîBà (72) Л.Е.Горша, А.К.Беляев, В.И.Гриценко и Б.Г.Мудла (53) 681.325 (088.8) (56) Авторское свидетельство СССР № 995093, кл. G 06 F 15/20, 1981.

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

¹ 446057, кл. С 06 F 15/20, 1972. (54) УСТРОЙСТВО ДЛЯ НУМЕРАЦИИ ПЕРЕСТАНОВОК НАТУРАЛЬНОГО РЯДА ЧИСЕЛ И

НУЛЯ (57) Изобретение относится к автоматике и вычислительной технике, Целью изобретения является расширение области применения эа счет вычисления номера перестановки. Изобретение впервые реализует непосредственный алгоритм вычисления номера перестановки по ее кодированному представлению и позволяет значительно сократить время поиска нумерованных объектов при одновременном уменьшении объемов памяти, необходимых для хранения элементов изображений. Устройство для нумерации перестановок содержит входную информационную шину 1 иэ (и-1)-й кодовой группы для подключения всех кодов элементов перестановки степени и, кроме нулевого, (и-2) блока понижения степени перестановки

2, (п-1) умножителей 3 на константу, многовходовый сумматор 4, выходную информационную шину 5 номера перестановки. 2 ил.

1418731

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

Целью изобретения является расширение области применения за счет вычисления номера генерируемой переста- 10 новки, На фиг. 1 представлена блок-схема устройства; на фиг. 2 — структурная ,схема блока понижения степени перестановки. 15

Устройство содержит вход 1 элементов массива перестановки, блоки 2,-2 „,понижения степени перестанов.ки, где и — количество элементов в перестановке, умножители 3<-3 „, на 20 константу, многовходовой сумматор 4, выход 5.

Блок понижения степени перестановки содержит блоки 6„-6; памяти, где номер блока понижения степени перестановок, Устройство осуществляет вычисление номера перестановки степени с нумерацией элементов от 0 до (n 1).

Принцип работы предлагаемого уст- 30 ройства основан на разбиении некоторого множества перестановок Л„ степени и „a классы мощностью (n 1)t таким образом, что крайний слева. элемент перестановки равняется номеру класса„ при этом имеет место следующее соотношение:

n! = n(n — 1), В результате такого разбиения классы будут пронумерованы числами сф от 0 до (n-1), Номер класса, к которому будет отнесена заданная перестановка, обозначим С,. Продолжая прод цесс, получаем соответственно С и (п-2) и т.д.

Д5

Процесс понижения степени перестановки при переходе к множеству перестановок меньшей степени состоит в перенумерации элементов исходной перестановки. о

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

Значение крайнего слева элемента перестановки является номером класса

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

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

Коды элементов перестановки поступают на вход 1 устройства, при этом на входе i „, ïðåäñòàâëÿåò собой номер класса С,. В блоке 2<„, происходит преобразование перестановки степени (n-I) в перестановку степени (и-2) под управлением кода С,. Код на (n-2) выходе блока 2<„ > соответствует номеру класса С, который управляет процессом уменьшения степени перестановки в блоке 2(„>) H т.д, Kopef номеров классов С „, где k = 1, (n-1) поступают также на умножители на константу 3 „ ), которые выполняют умножение С на величину (n-k)

Коды с выходов умножителей на коэффициент три суммируются в многовходовом сумматоре 4, на выходе которого формируется код номера перестановки, который поступает на выход 5. !

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

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

{i = 1,2,...n-2) содержит i узлов памяти, входы кодов элементов массива перестановок с первого по (n-2)-й устройства соединены с первыми адресными входами соответственно с первого по (п-2)-й узлов памяти (п-2)-го блока понижения степени, вторые адресные входы узлов памяти которого объединены и соединены с входом (и-1)-го элемента массива перестановок устройства и входом (п-1)-го умножителя на константу, выход k-ro узла памяти 1-ro блока понижения степени перестановки (k = 1,2,..., 1-1;

1 .= 2,3,..., n-2) соединен с первым адресным входом k-го узла памяти

141

Составитель А.Зорин

Редактор Г.Волкова Техред A.Êðàâ÷óê

Корректор И.Эрдейи

Заказ 4155/47 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4 (1-1)-го блока понижения степени перестановки, выход 1-го узла памяти

1-го блока понижения степени перестановки соединен с вторыми адресными входами всех узлов памяти (1-1)-ro блока понижения степени перестановки и входом 1-го умножителя íà константу, выход первого узла памяти перво8731 4 го блока понижения степени перестановок соединен с входом первого умножителя на константу, выходы умножителей на константу с первого по

5 (n-1)-й соединены с соответствующими входами многовходового сумматора, выход которого соединен с выходом устройства.