Формирователь сочетаний из n по m символов

Полезная модель относится к области вычислительной техники и может быть использована в устройствах для решения комбинаторных задач. Содержит генератор тактовых импульсов 5, m регистров на n сдвигов 2, блоки 7 и 8 с m линиям задержки, блок m счетчиков 9, формирователь символа m 4, шину ввода символа n 10, m блоков с n замыкающими ключами 1, блок m размыкающих ключей 3 и m блоков с m замыкающими ключами 6, выходы которых подключены к клеммам вывода сочетаний «», «»,, что обеспечивает расширение функциональных возможностей устройства для перебора (формирования) любого необходимого сочетания из 1, 2, , n по 1, 2, , m символов.

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

Известно устройство для перебора сочетаний, содержащее триггеры, регистры записи, регистры сдвига, элементы И, ИЛИ, И-ИЛИ и временной задержки, генератор тактовых импульсов и четыре клеммы вывода [1], что обеспечивает с помощью минимальных средств осуществлять перебор сочетаний из четырех разрядных двоичных символов.

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

Наиболее близким к заявляемому в качестве прототипа является устройство для перебора сочетаний, которое содержит генератор тактовых импульсов, m регистров на n сдвигов, первый и второй блоки с m линиям задержки и блок m счетчиков, а также содержит пять групп элементов И, две группы элементов ИЛИ и блок сдвига кодов [2]. С помощью шести триггеров, каждый из которых имеет прямой и инверсный выход, формируются сочетания из шести двоичных чисел.

Недостаток прототипа состоит в том, что процедура перебора сочетаний выполняется для заданного и жестко зафиксированного массива символов (чисел) m и n. При изменении значения m или n необходимо изменять схему устройства для перебора (формирования) нового сочетания, что свидетельствует об ограниченных функциональных возможностях прототипа.

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

Целью полезной модели является расширение функциональных возможностей устройства для перебора (формирования) любого необходимого сочетания из 1, 2,, n по 1, 2,, m символов.

Сущность полезной модели заключается в том, что, кроме известных и общих отличительных признаков, а именно: генератора тактовых импульсов, m регистров на n сдвигов, первого и второго блоков с m линиям задержки и блока m счетчиков, предлагаемый формирователь сочетаний из n по m символов содержит формирователь символа m с двумя группами выводов, шину ввода символа n, m блоков с n замыкающими ключами, блок m размыкающих ключей и m блоков с m замыкающими ключами, выходы которых подключены к клеммам вывода сочетаний «», «»,, «», входы m блоков с m замыкающими ключами соединены с соответствующими выходами m блоков с n замыкающими ключами, управляющие входы m блоков с m замыкающими ключами связаны через соответствующие размыкающие контакты блока m размыкающих ключей с выходами линий задержек первого блока m линий задержек и с входами m регистров на n сдвигов, выходы которых подключены к входам соответствующих n замыкающих ключей, управляющие входы которых связаны с шиной ввода символа n, выходы m блоков с n замыкающими ключами подключены через линии задержки второго блока m линий задержки к входам «сброс» соответствующих регистров на n сдвигов и непосредственно подключены к входам счетчиков блока m счетчиков, выходы блока m счетчиков соединены с управляющими входами соответствующих размыкающих ключей блока m размыкающих ключей, первая группа выходов формирователя m символов подключена к одному управляющему входу каждого счетчика блока m счетчиков, к другому управляющему входу которого подсоединена шина ввода символа n, к одному управляющему входу формирователя символа m подключен выход генератора тактовых импульсов, а к другому управляющему входу формирователя символа m подключена цепь для передачи информации о числе сочетаний элементов треугольной матрицы Паскаля.

Новым в предлагаемом устройстве является то, что оно содержит формирователь символа m (4) с двумя группами выводов, шину ввода символа n (10), m блоков с n замыкающими ключами (1) блок m размыкающих ключей (3) и m блоков с m замыкающими ключами (6), выходы которых подключены к клеммам вывода сочетаний «», «»,, «», входы m блоков с m замыкающими ключами (6) соединены с соответствующими выходами m блоков с n замыкающими ключами (1), управляющие входы m блоков с m замыкающими ключами (6) связаны через соответствующие размыкающие контакты блока m размыкающих ключей (3) с выходами линий задержек первого блока m линий задержек (8) и с входами m регистров на n сдвигов (2), выходы которых подключены к входам соответствующих n замыкающих ключей (1), управляющие входы которых связаны с шиной ввода символа n (10), выходы m блоков с n замыкающими ключами (1) подключены через линии задержки второго блока m линий задержки (7) к входам «сброс» соответствующих регистров на n сдвигов (2) и непосредственно подключены к входам счетчиков блока m счетчиков (9), выходы блока m счетчиков (9) соединены с управляющими входами соответствующих размыкающих ключей блока m размыкающих ключей (3), первая группа выходов формирователя m символов (4) подключена к одному управляющему входу каждого счетчика блока m счетчиков (9), к другому управляющему входу которого подсоединена шина ввода символа n (10), к одному управляющему входу формирователя символа m (4) подключен выход генератора тактовых импульсов (5), а к другому управляющему входу формирователя символа m (4) подключена цепь для передачи информации о числе сочетаний элементов треугольной матрицы Паскаля, что обеспечивает расширение функциональных возможностей устройства для любого перебора (формирования) сочетания из 1, 2,, n по 1, 2,, m символов.

Функциональная схема формирователя сочетаний из n по m символов представлена на фиг.1. Математическое отображение треугольной матрицы числа сочетаний Паскаля изображено на фиг.2 и 3.

На фиг.1 обозначено:

1 - блок 1.1, 1.2,, 1.m замыкающих ключей 1, 2,, n;

2 - блок 2.1, 2.2,, 2.m регистров n сдвига с 1, 2,, n выводами у каждого регистра;

3 - блок 3.1, 3.2,,3.m счетчиков повторных заполнений n - х ячеек регистра n сдвига при условии, что n·mN, где N - число сочетаний;

4 - формирователь символа (числа) m;

5 - генератор тактовых импульсов;

6 - блок вывода сочетаний "", "", "",, "" на m выходов с 1, 2,, m замыкающими ключами;

7 - блок линий задержек 7.1, 7.2,. 7.m;

8 - блок линий задержек 8.1, 8.2,, 8.m;

9 - блок счетчиков 9.1, 9.2,, 9.m;

10 - шина включения (ввода задания) символа n;

11 - шина включения (ввода задания) символа m;

12 - выход треугольной матрицы числа сочетаний Паскаля с фиг.2.

В исходном положении входы m блоков 1 замыкающих ключей подключены к соответствующим n выводам блока 2 m регистров n сдвига. Выходы блока 3 размыкающих ключей связаны с управляющими входами замыкающих ключей блока вывода сочетаний "", "", "",, "". Управляющий вход формирователя 4 символа m подсоединен к выходу генератора тактовых импульсов 5. Входы блока 6 замыкающих ключей подключены к выходам блоков 1 замыкающих ключей непосредственно и через линии задержки блока 7 линий задержек подключены к входам «сброс» регистров сдвига 2. Блок 8 линий задержек соединен с одним выходом формирователя символа m 4, другой выход которого 6 связан с одними управляющими входами блока 9 счетчиков, другие управляющие входы которых подключены к шине 10 ввода символа n. При выключении и последующем включении электрического питания элементы блоков 19 принимают исходное положение.

Предлагаемый формирователь сочетаний из n по m символов работает следующим образом.

Формирователь 4 символа m имеет первую и вторую группу m выводов (выходов). С помощью первой группы выводов включаются в работу блок т счетчиков 9.1, 9.2,, 9.m повторных заполнений n - х ячеек регистров сдвига 2.1, 2.2,, 2.m, с помощью второй группы выводов обеспечивается включение m-ого замыкающего ключа из блока 6,1, 6.2,,6.m ключей через соответствующие линии задержки 8.1, 8.2,, 8.m и размыкающие ключи 3.1, 3.2,,3.m, кроме того, через эти линии задержки 8.1, 8.2,, 8.m со второй группы выводов формирователя 4 поступают счетные импульсы на счетные входы регистров сдвига 2.1, 2.2,, 2.m. Значение интервалов времени задержки для каждой линии временной задержки 7.1, 7.2, 7.m и 8.1, 8.2,, 8.m определяется числом соответствующих длительностей тактовых импульсов согласно последовательности: 0, 1, 2,, m. Из этой последовательности следует, что для первых по порядку линий задержек 7.1 и 8.1 время задержки равно 0, для вторых линий задержек 7.2 и 8.2 время их задержки составляет длительность одного тактового импульса, для третьих и последующих линий задержки 7.3, 7.4,, 7.m и 8.3, 8.4,, 8.m время задержек определяется длительностью 2, 3,, m тактовых импульсов. Кроме того, формирователь 4 символа m имеет вход 11 для установки заданного числа (символа) m и вход 12 для задания необходимого числа сочетаний с помощью треугольной матрицы Паскаля (фиг.3). В функциональную схему формирователя 4 входит счетчик числа тактовых импульсов с регулируемым объемом ячеек памяти N+m-1, переполнение которого свидетельствует о том, что все сочетания набраны. Объем N этого счетчика тактовых импульсов устанавливается при выборе значений сочетаний из n по m символов, используя данные матрицы Паскаля (фиг.3).

После того, как с помощью первой группы выходов формирователя 4 символа m и шины 10 задания числа n установили заданные символы (числа) m и n, сформировались цепи подачи счетных импульсов на счетные входы соответствующих регистров сдвига 2.1, 2.2,,2.m и включились в работу соответствующие блоки включения замыкающих контактов 1.1, 1.2,, 1.m, при этом каждый включенный n-ый ключ формирует цепь подключения n-ого вывода регистра сдвига 2.1, 2.2,, 2. на вход обнуления своего регистра сдвига с автоматической задержкой, определяемой порядковым номером этого регистра сдвига 7.1, 7.2,, 7.m, где время задержки равно соответственно 0, 1, 2, длительностям тактовых импульсов, а также с n-ого вывода регистра сдвига 2.1, 2.2,, 2.m устанавливается цепь подачи импульса на вход соответствующего счетчика 9.1, 9.2,, 9.m подсчета числа переполнения этого n-ого разряда регистра сдвига.

На выходах замыкающих ключей каждого из блоков 1.1, 1.2,, 1.m формируются электрические сигналы, которые соответствуют символам (числам): 1, 2, 3,,n, из которых и формируются сочетания , . При этом сочетания =1 и =1 не формируются, так как их значения известны и равны единице.

С появлением первого и последующих по порядку тактовых импульсов на выходах генератора тактовых импульсов 5 эти тактовые импульсы поступают с выхода формирователя 4 на счетные входы тех регистров сдвига 2.1, 2.2,, 2.m, к счетным входам которых подключены с помощью формирователя 4 соответствующие линии задержки 8.1, 8.2,, 8.m. Происходит последовательное заполнение ячеек памяти и перемещение счетного импульса с младшего разряда на старший разряд регистров сдвига 2.1, 2.2,, 2.m. С выходов регистров сдвига 2.1, 2.2, , 2.m импульсы напряжения поступают через замкнутые 1, 2,, n ключи блоков 1.1, 1.2,. 1.m замыкающих ключей на входы блоков замыкающих ключей 6.1, 6.2,, 6.m. Кроме того, с выхода n-ого разряда регистра сдвига 2.1, 2.2,, 2.m поступают импульсы переполнения на вход «сброс» для обнуление своих регистров сдвига с задержками 7.1, 7.2,, 7.m соответственно и на входы счетчиков 9.1, 9.2,, 9.m числа повторов этих переполнений. На выходах блока замыкающих ключей 6.1, 6.2,, 6.m формируется последовательность сочетаний символов, которая подключается с помощью этого блока замыкающих ключей 6.1, 6.2,, 6.m только к соответствующим выходам , блока вывода 6.

В качестве примера формирования сочетаний из n по m символов рассмотрим порядок их получения по мере того, как возрастают задаваемые числа (символы) n и m.

Для формирования сочетаний из n по m=1 символов, когда =1, 2,, n, включаются в работу блоки: 1.1, 2.1, 4, 6.1 и 8.1. Тактовые импульсы с выхода генератора 5 через формирователь 4 и линию задержки с нулевым значением задержки 8.1 заполняют регистр сдвига 2.1, с выводов которого импульсы заполнения ячеек памяти регистра поступают на вход замыкающего ключа 6.1 через соответствующие замыкающие ключи блока 1.1. Замыкающий ключ 6.1 включается в работу с помощью управляющего сигнала, каким является выходной сигнал линии задержки 8.1, который поступает на управляющий вход замыкающего ключа 6.1 через размыкающий ключ 3.1. На выходе замыкающего ключа 6.1 формируется сочетание чисел. Остальные замыкающие ключи 6.2, 6.3,, 6.m разомкнуты и на их выходах сформированных сочетаний не образуется.

Число сочетаний из n по m=1 символов совпадает, согласно матрице Паскаля, со значением символа n и переполнения регистра сдвига 2.1 не происходит, т.к. n·m=n·1N.

Для формирования сочетаний из n по m=2 символов, например, при n=3, когда три сочетания определяются по формуле: =2,1; 3,2 и 1,3, формирователь 4 использует в работе только две линии задержки 8.1 и 8.2. Первый тактовый импульс с выхода генератора 5 через формирователь 4 и линию задержки с нулевым значением задержки 8.1 заполняет первую ячейку регистра сдвига 2.1, с вывода которого импульс заполнения этой первой ячейки памяти регистра 2.1

поступает на все входы блока выводов 6. На выходе «» блока выводов 6 пока сочетания не предъявляются, т.к. замыкающий ключ 6.2 блока выводов 6 еще не включился в работу до появления второго тактового импульса. Второй тактовый импульс с выхода формирователя 4 через нулевую линию задержки 8.1 переводит счетный импульс регистра 2.1 во вторую ячейку памяти. А через линию задержки 8.2 этот второй тактовый импульс запоминается в первой ячейке памяти регистра сдвига 2.2 и подключает через размыкающий ключ 3.2 замыкающий ключ 6.2 к цепям выводов «» блока выводов 6. На выходе «» блока выводов 6 формируется первое сочетание чисел «2,1». Далее третий по порядку тактовый импульс передвигает в регистрах сдвига 2.1 и 2.2 счетные импульсы через линии задержек 8.1 и 8.2 в третью и вторую ячейки памяти соответственно. С выводов этих регистров сдвига 2.1 и 2.2 поступают через замкнутые ключи 6.2 сигналы на выход «» блока выводов 6, которые соответствуют второму сочетанию «3,2» чисел из трех по два. Четвертый тактовый импульс переводит импульс переполнения с третьей ячейки регистра сдвига 2.1 на первую, т.к. n=3 и регистр сдвига 2.1 обнуляется с нулевой задержкой 7.1, а в регистре сдвига 2.2 заполняется третья ячейка памяти. Выходные сигналы с этих ячеек регистров 2.1 и 2.2 поступают через замкнутые ключи 6.2 на выход блока выводов 6, формируя последнее, третье сочетание чисел «1,3», и направляя однократный импульс переполнения в счетчик 9.1, который не оказывает влияния на работу формирователя сочетаний.

Число сочетаний из n по m символов, как упоминалось выше, определяется с помощью треугольной матрицы числа сочетаний Паскаля (фиг.2 и 3). Числовые значения каждого элемента матрицы Паскаля (фиг.3), кроме единиц, определяются как сумма двух верхних значений элементов матрицы.

Для формирования сочетаний из n=4 по m=2 символов, когда =6, соответственно, работа предлагаемого формирователя сочетаний аналогична ранее рассмотренной работе формирователя сочетаний из n=3 по m=2 и при n·mN. не вступают в работу счетчики 9.1, 9.2 переполнения регистров сдвига. Так для n=4 и m=2, когда =2,1; 3,2; 4,3; 1,4; 2,4 и 3,1, четвертый тактовый импульс передвигает в регистрах сдвига 2.1 и 2.2 счетные импульсы в четвертую и третью ячейки памяти соответственно. С выводов этих регистров сдвига 2.1 и 2.2 поступают через замкнутые ключи 6.2 сигналы на выход «» блока выводов 6, которые соответствуют третьему сочетанию «4,3» чисел из четырех по два. Пятый тактовый импульс обнуляет регистр сдвига 2.1 с нулевой задержкой, то есть переводит импульс переполнения с четвертой ячейки регистра сдвига 2.1 на первую, т.к. n=4, а в регистре сдвига 2.2 заполняется четвертая ячейка памяти. Выходные сигналы с этих ячеек поступают через замкнутые ключи 6.2 на выход блока выводов 6, формируя четвертое сочетание чисел «1,4» и на вход счетчика 9.2 числа переполнений. При заполнении четвертой ячейки регистра 2.2 происходит его обнуление с задержкой согласно его порядковому номеру на один тактовый импульс. Шестой тактовый импульс переводит в регистре 2.1 сдвиг счетного импульса на вторую ячейку, а регистре 2.2 происходит его обнуление при заполнении четвертой ячейки с задержкой 7.2 на один такт. Снимаемое напряжение со второй и четвертой ячеек регистров 2.1 и 2.2 соответствует сочетанию «2,4». Седьмой тактовый импульс переводит счетный импульс в регистре 2.1 из второй на третью ячейку, а в регистре 2.2 после его обнуления с задержкой счетный импульс запоминается в первой ячейке. На выходе «» блока выводов 6 сформировалось последнее (шестое) сочетание «3,1» из необходимых шести. Счетчики 9.1 и 9.2 не участвовали в работе, т.к. n·m=4·2=8>N, где N=6 - число сочетаний, и переполнение ячеек регистра сдвига было однократное.

Аналогично для случая, когда n=5 и m=2, пятый тактовый импульс передвигает в регистрах сдвига 2.1 и 2.2 счетные импульсы в пятую и четвертую ячейки памяти соответственно. С выводов этих регистров сдвига 2.1 и 2.2 поступают через замкнутые ключи 6.2 сигналы на выход «» блока выводов 6, которые соответствуют четвертому сочетанию «5,4» чисел из пяти по два (2,1; 3,2; 4,3; 5,4;). Шестой тактовый импульс обнулит с нулевой задержкой 7.1 регистр 2.1 и передвинет регистр 2.2 в пятое положение, что отвечает пятому сочетанию «1,5» из необходимых десяти =10. Седьмой тактовый импульс переместит счетный импульс в регистре 2.1 во вторую ячейку и обнулит с задержкой на один такт регистр 2.2, предъявив шестое сочетание «2,5» на выходе «» блока 6. Восьмой, девятый и десятый тактовые импульсы последовательно переместят счетные импульсы в регистрах 2.1 и 2.2 и с их соответствующих выводов импульсное напряжение поступит на выход «» блока 6 в виде сочетаний «3,1; 4,2; 5,3 и 1,4». Полный набор сочетаний из пяти по два числа имеет вид: 2.1; 3,2; 4,3; 5,4; 1,5; 2,5; 3,1; 4,2; 5,3 и 1,4. Счетчики 9.1 и 9.2 не участвовали в работе, т.к. n·m=5·2=10=N, где N=10 - число сочетаний, и повторение переполнения регистров было однократное.

Далее рассмотрим формирование сочетаний =15, а именно: 2,1; 3,2; 4,3; 5,4; 6,5; 1,6; 2,6; 3,1; 4,2; 5,3; 6,4; 1,5; 3,6; 4,1; 5,2, когда n·m=6·2=12<N, где N=15 - число сочетаний. При формировании сочетаний в регистрах 2.1 и 2.2 были их повторные переполнения, факт появления переполнений которых зарегистрирован в управляемых счетчиках 9.1 и 9.2 числа переполнений. Количество ячеек памяти счетчиков 9.1 и 9.2 задается числами n и m при их вводе. Переполнение счетчика 9.2 вызывает включение размыкающего ключа 3.2. В этом случае после сочетания «1,5» должно сформироваться повторно сочетание «2,6», которое из-за включения размыкающего ключа 3.2 не появилось на выходе замыкающих ключей 6.2 блока выводов 6 сочетаний, так как замыкающие ключи 6.2 не были включены в этот тактовый импульс работы формирователя сочетаний.

Аналогично формируются последующие сочетания ,, когда с помощью размыкающего ключа 3.2 исключаются «лишние» комбинации «2,7», «2,8», соответственно после повторного переполнения регистра сдвига 2.2 и последующего переполнения счетчика 9.2 числа переполнений этого регистра 2.2.

Для формирования сочетаний из n по m=3 включаются в работу регистры сдвига 2.1, 2.2 и 2.3, блоки замыкающих ключей 1.1, 1.2 и 1.3 и линии задержки 8.1, 8.2 и 8.3. Сформированные сочетания предъявляются на выходе «» блока выводов 6. При поступлении первого и второго тактовых импульсов заполнятся два и один разряды регистров 2.1 и 2.2 соответственно. При поступлении третьего тактового импульса на выходе линии задержки 8.3 появится импульс, который заполнит первый разряд регистра 2.3 и включит замыкающие ключи 6.3. Этот третий тактовый импульс передвинет счетный импульс в регистре сдвига 2.1 в третью ячейку, в регистре сдвига 2.2 счетный импульс окажется во втором разряде и на выходе «» блока выводов 6 появится первое сочетание «3,2,1». Далее работа предлагаемого формирователя сочетаний проходит аналогично ранее рассмотренным вариантам перебора сочетаний из n по m=2.

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

Положительный эффект от использования полезной модели состоит в том, что расширяются не менее чем на 3040% функциональные возможности формирователя сочетаний из n по m символов за счет обеспечения функциональной возможности варьировать значения этих n и m символов в широком пределе.

Источники информации:

1. Патент СССР на изобретение 1575198, «Устройство для перебора сочетаний», МПК G06F 7/06, приоритет: 1988.27.04, патентообладатель: Таганрогский радиотехнический институт, авторы: Глушарь В.М и др., (аналог).

2. Авторское свидетельство на изобретение СССР 1658167 «Устройство для перебора сочетаний», МПК G06F 15/20, приоритет: 1988.15.09, авторы: Глушарь В.М. и др., (прототип).

Формирователь сочетаний из n по m символов, содержащий генератор тактовых импульсов, m регистров на n сдвигов, первый и второй блоки с m линиями задержки и блок m счетчиков, отличающийся тем, что содержит формирователь символа m с двумя группами выводов, шину ввода символа n, m блоков с n замыкающими ключами, блок m размыкающих ключей и m блоков с m замыкающими ключами, выходы которых подключены к клеммам вывода сочетаний «», «», «», входы m блоков с m замыкающими ключами соединены с соответствующими выходами m блоков с n замыкающими ключами, управляющие входы m блоков с m замыкающими ключами связаны через соответствующие размыкающие контакты блока m размыкающих ключей с выходами линий задержек первого блока m линий задержек и с входами m регистров на n сдвигов, выходы которых подключены к входам соответствующих n замыкающих ключей, управляющие входы которых связаны с шиной ввода символа n, выходы m блоков с n замыкающими ключами подключены через линии задержки второго блока m линий задержки к входам «сброс» соответствующих регистров на n сдвигов и непосредственно подключены к входам счетчиков блока m счетчиков, выходы блока m счетчиков соединены с управляющими входами соответствующих размыкающих ключей блока m размыкающих ключей, первая группа выходов формирователя m символов подключена к одному управляющему входу каждого счетчика блока m счетчиков, к другому управляющему входу которого подсоединена шина ввода символа n, к одному управляющему входу формирователя символа m подключен выход генератора тактовых импульсов, а к другому управляющему входу формирователя символа m подключена цепь для передачи информации о числе сочетаний элементов треугольной матрицы Паскаля.