ГЕНЕРАЦИЯ N-ОЙ ПЕРЕСТАНОВКИ В ЛЕКСИКОГРАФИЧЕСКОМ ПОРЯДКЕ

Броницкая Наталья Анатольевна

канд. физ.-мат. наук, ННУ им. В. А. Сухомлинского, г. Николаев

Е-mail: natbron@mail.ru

Дармосюк Валентина Николаевна

канд. физ.-мат. наук, ННУ им. В. А. Сухомлинского, г. Николаев

Бережецкая Виктория Геннадиевна

студентка, ННУ им. В. А. Сухомлинского, г. Николаев

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

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

Многие прикладные задачи сводятся к нахождению оптимального решения среди очень большого конечного числа вариантов. В большинстве случаев единственный способ отыскать решение состоит в переборе всех возможных вариантов и сравнении их между собой. Исходя их выше сказанного, необходимо уметь строить алгоритмы перебора различных комбинаторных объектов − последовательностей, перестановок, подмножеств и т. д. [1]

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

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

Схема перебора всегда будет одинакова [1]:

• во-первых, надо установить порядок на элементах, подлежащих перечислению (в частности, определить, какой из них будет первым, а какой последним);
• во-вторых, научиться переходить от произвольного элемента к непосредственно следующему за ним (т. е. для заданного элемента x₁ строить такой элемент x₂, что x₁<x₂ и между x₁ и x₂ нет других элементов).

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

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

Существует много методов, приемов и алгоритмов для нахождения (построения) следующей в лексикографическом порядке перестановки. Перестановка − это упорядоченный набор элементов, в котором порядок имеет значение. Как известно количество различных перестановок из n элементов равно в точности n!.

Наиболее известны два алгоритма генерации перестановок — рекурсивный и алгоритм лексикографического порядка перестановок. Стандартная библиотека шаблонов STL языка программирования С++ содержит реализованный алгоритм нахождения следующей в лексико­графическом порядке перестановки next_permutation [4], который упрощает написание некоторых программ. Но каждая комбинаторная задача требует индивидуального подхода, когда возникает необхо­димость найти особенный алгоритм на основе уже известных.

Рассмотрим комбинаторную задачу, которая предлагалась на Всеукраинской студенческой олимпиаде по программированию, I этап, Тренировочный турнир, 19 апреля 2012 г. и вызвала значительные затруднения у участников олимпиады. Ее особенностью является то, что нужно генерировать не обычную (в общепринятом понимании) наименьшую лексикографически перестановку, а удовлетворяющую дополнительному условию — состоящую из двух чередующихся множеств с разным количеством элементов. Этот факт несколько затрудняет использование общеизвестных алгоритмов, но при этом побуждает к поиску других путей решения. Они должны быть к тому же оптимальными, поскольку в задаче предполагается применение алгоритма не один раз, а некоторое количество Т тестовых случаев при ограничении времени в 1 с.

Троллинг. [5] В языке троллей 5 согласных звуков {h, k, m, r, t} и 3 гласных {a, o, u}. Каждое слово начинается с согласной буквы, при этом в слове не может быть подряд две гласные или согласные.

N троллей по очереди называют самое короткое слово, которое еще не назвал никто из предыдущих троллей. Если вариантов несколько, то тролль выбирает наименьшее лексикографически. Лексикографический порядок h<k<m<r<t<a<o<u. При этом слова сравнивают сначала по первой букве. Если первые буквы одинаковые, то по второй и т. д.

Найти слово, которое назовет N-ый тролль.

Формат входных данных. В первой строке содержится единственное число 1≤T≤100, количество тестовых случаев. В каждой из последующих T строк содержится одно число 1≤N≤1000000000(1e9) − количество троллей.

Для каждого числа N из входных данных выведите в отдельной строке ответ на задачу в соответствии с форматом, показанным в примере.

Примеры.

Примечание. Порядок слов такой: h, k, m, r, t, ha, ho, hu, ka, ko, …

Предложенную задачу нельзя решать полным перебором, учитывая ограничения в условии, а нужно искать оптимальные пути решения. Нами предлагается следующий алгоритм решения этой задачи, не содержащее переборов вообще и для каждого тестового случая работающий за O(k), где k — длина искомого слова (1≤k≤15).

Для решения задачи нужно выяснить длину k слова названого N-м тролем и номер искомого k-буквенного слова в лексикографическом порядке среди всех слов с соответствующим количеством символов.

Количество k-символьных слов ищем по формуле размещений с повторениями . На первое место можно выбрать букву пятью способами (множество согласных букв по условию задачи содержит 5 символов), на второе — тремя (множество гласных букв по условию задачи содержит 3 символа), на третье — снова пятью (символы могут повторяться), на четвертое — тремя и т. д. Таким образом, мы подсчитываем и храним в массиве количество k-буквенных слов: 1-буквенных — 5, 2-буквенных − 5×3=15, 3-буквенных − 5×3×5=75, 4-буквенных − 5×3×5×3=225 и т. д. По условию задачи максимальное количество троллей − 1000000000, тогда максимальная длина слова, сказанного последним троллем слова — 15 символов, 1≤k≤15.

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

После определения длины k искомого слова применяем следующий алгоритм:

1. Количество k-буквенных слов записываем в переменную x.
2. Повторяем следующий пункт ровно k-1 раз.
3. x делим на 5 (для нечетного шага) или на 3 (для четного шага) и по остатку определяем искомую согласную (гласную) букву, а частное снова запоминаем в x.
4. Последнюю букву получаем как последнее частное, которое хранится в x, но нужно учитывать четность шага для определения будет ли эта буква гласной или согласной.

При делении на 5 остатки получаем в пределах [0;4] и из соответствующей строки "thkmrt" выводим согласную букву по описанному выше остатку. Аналогично с делением на 3 и строкой "uaou".

Теперь приводим код программы на языке программирования С++. В программе используется контейнер string стандартной библиотеки шаблонов STL, хотя можно рассматривать и константный массив символов.

int main()

{

string g="uaou";

string p="thkmrt";

int T;

cin>>T;

for(int j=0;j<T;j++)

{

int sum=0,n;

cin>>n;

int x=1,k=0; bool f=true;

while(sum<n)

{

if(f)x*=5;else x*=3;

f=!f;

sum+=x;

k++;

}

n=n-sum+x;

f=false;

cout<<"Case #"<<j+1<<": ";

for(int i=1;i<k;++i)

{

if(!f){x/=5.0;cout<<p[ceil((double)n/(double)(x))];n%=(x);}

else{x/=3.0;cout<<g[ceil((double)n/(double)(x))];n%=(x);}

f=!f;

}

if(!f)cout<<p[n]<<endl;else cout<<g[n]<<endl;

}

}

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

Список литературы:

1. Булычев В. А. Методы программирования: переборные алгоритмы [электронный ресурс] — Режим доступа. — URL: http://algolist.manual.ru/ maths/combinat/sequential.php (дата обращения: 06.05.2012)
2. Липский В. Комбинаторика для программистов. — М.: Мир,1988. —213 с.
3. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. − М.: Мир, 1980. — 476 с.
4. Information on the C++ language [электронный ресурс] — Режим доступа. − URL: http://www.cplusplus.com/reference/algorithm/next_permutation (дата обращения: 07.05.2012)
5. I этап Всеукраинской студенческой олимпиады по программированию. Южный регион [электронный ресурс] — Режим доступа. — URL: http://ejudge.crimea.edu (дата обращения: 19.04.2012)