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

, К, Беляев,Г.Мудла ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ А ВТОРСНОМУ СВИДЕТ(56) Авторское свидетельство СССР У 995093, кл, С 06 Р 15/20, 1981.Авторское свидетельство СССР В 446057, кл. С 06 Г 15/20, 1972. (54) УСТРОЙСТВО ДЛЯ НУМЕРАЦИИ ПЕРЕСТАНОВОК НАТУРАЛЬНОГО РЯДА ЧИСЕЛ И НУЛЯ(57) Изобретение относится к автома тике и вычислительной технике, Целью изобретения является расширение области применения эа счет вычисления номера перестановки. Изобретениевпервые реализует непосредственныйалгоритм вычисления номера перестановки по ее кодированному представлению и позволяет значительно сократить время поиска нумерованных объектов при одновременном уменьшении объемов памяти, необходимых для хранения элементов изображений. Устройство для нумерации перестановок содержит входную информационную шину 1 иэ(п)-й кодовой группы для подключения всех кодов элементов перестановки степени и, кроме нулевого, (и)блока понижения степени перестановки2, (п) умножителей 3 на константу,многовходовый сумматор 4, выходнуюинформационную шину 5 номера перестановки. 2 ил.Изобретение относится к автомати,ке и вычислительной технике и можетбыть использовано при создании высокопроизводительных специализированных устройств для решения комбинаторных задач,Целью изобретения является расширение области применения за счет вычисления номера генерируемой перестановки,На фиг, 1 представлена блок-схемаустройства; на фиг. 2 - структурная,схема блока понижения степени перестановки, 15Устройство содержит вход 1 элементов массива перестановки, блоки2,-2понижения степени перестанов,ки, где и - количество элементов вперестановке, умножители 3-3 , на 2 Оконстанту, многовходовой сумматор 4,выход 5.Блок понижения степени перестанов"ки содержит блоки 6-6; памяти, гденомер блока понижения степениперестановок,Устройство осуществляет вычисление номера перестановки степени снумерацией элементов от О до (п),Принцип работы предлагаемого уст- ЗОройства основан на разбиении некоторого множества перестановок Л степени и на классы мощностью (и) такимобразом, что крайний слева. элементперестановки равняется номеру класса 35при этом имеет место следующее соотношение:и = п(п - 1) ,В результате такого разбиенияклассы будут пронумерованы числами 4 Оот О до (п), Номер класса, к которому будет отнесена заданная перестановка, обозначим С Продолжая процесс, получаем соответственно С и(и) и т.д.д 5Процесс понижения степени перестановки при переходе к множеству перестановок меньшей степени состоит вперенумерации элементов исходной перестановки,ГОТаким образом, понижение степениперестановки иа единицу состоит вусечении исходной перестановки слевана один элемент и уменьшении значений оставшихся элементов на единицу,, если это значение превышает значениеотбрасываемого элемента.Значение крайнего слева элементаперестановки является номером класса С, который для данного преобразования имеет смысл управляющей информаУстройство работает следующим образом.Коды элементов перестановки поступают на вход 1 устройства, при этом на входе 1,1 представляет собой номер класса С,. В блоке 2.,происходит преобразование перестановки степени (п) в перестановку степени (и) под управлением кода С Код на (и) выходе блока 2.1 соответствует номеру класса С, который управляет процессом уменьшения степени перестановки в блоке 2 и т.д,Кодь номеров классов С , где 1 = 1, (п) поступают также на умножители на константу 3 1, которые выполняют умножение Сна величину (ис)Коды с выходов умножителей на коэффициент три суммируются в многовходовом сумматоре 4, на выходе которого формируется код номера перестановки, который поступает на выход 5.Формула изобретенияУстройство для нумерации перестановок натурального ряда чисел и нуля, содержащее многовходовый сумматор, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет вычисления номера генерируемой перестановки, в него ввецены иблока понижения степени перестановки, где п - количество переставляемых чисел, и иумножителей на константу, при этом значение константы 1-го умножителя на константу равно(3 = 1,2п), причем -й блок понижения степени перестановки (1 = 1,2,п) содержит 1. Улов памяти, входы кодов элементов массива перестановок с первого по (и)-й устройства соединены с первыми адресными входами соответственно с первого по (и)-й узлов памяти (п)-го блока понижения степени, вторые адресные входы узлов памяти которого объединены и соединены с входом (и)-го элемента массива перестановок устройства и входом (и)-го умножителя на константу, выход 1-го узла памяти 1-го блока понижения степени перестановки (к = 1,2. , 1-1;1 = 2,3 и) соединен с первым адресным входом К-го узла памяти141 Составитель А.ЗоринРедактор Г.Волкова Техред А.Кравчук Корректор И.Эрдейи Заказ 4155/47 Тираж 704 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий113035, Москва, Ж, Раушская наб., д, 4/5 Производственно-полиграФическое предприятие, г. Ужгород, ул. Проектная, 4(1-1)-го блока понижения степени перестановки, выход 1-го узла памяти1-го блока понижения степени перестановки соединен с вторыми адреснымивходами всех узлов памяти (1-1)-гоблока понижения степени перестановкии входом 1-го умножителя на константу, выход первого узла памяти первоЬ 731 4го блока понижения степени перестановок соединен с входом первого умножителя на константу, выходы умножителей на константу с первого по 5(и)-й соединены с соответствующимивходами многовходового сумматора, выход которого соединен с выходом устройства.