Расстановка знаков в арифметическом выражении

[Все темы по размещениям]

Задача: 155. Дешифровка выражения(contester.tsure.ru) [Условие]
Предварительные темы:    [Генерация всех размещений с повторениями рекурсивным способом]
                         [Генерация следующего размещения с повторениями]
                         [Подсчет арифметического выражения(обратная польская нотация)]
Дополнительная практика: Задачи для подсчета арифметического выражения (см. занятие 4 - архив)

Итак, имеется корректное арифметическое выражение вида (9?8)?(0?3)?2=-25, вместо знаков ? необходимо поставить одну из 4 операций +,-,*,/ так, чтобы выражение стало правильным. Если такого сделать нельзя, то нужно вывести “No solution.”. Для удобства гарантируется, что в левой части выражения все числа являются цифрами и отсутствуют унарные знаки. В правой же части может быть любое число по модулю не превышающее 10¹⁵.

Опять же для удобства рассмотрим более короткий пример: 2?(3?4)=-10
Алфавит знаков содержит четыре элемент: {+,-,/,*}.
Количество позиций в размещении(количество знаков ? в выражении): 2
Общее количество размещений: 4²=16

Сгенерируем все размещения с повторениями рекурсивным способом и получим все возможные комбинации исходного арифметического выражения:

1. 2+(3+4)=9
2. 2+(3-4)=1
3. 2+(3*4)=14
4. 2+(3/4)=2
5. 2-(3+4)=-5
6. 2-(3-4)=3
7. 2-(3*4)=-10
8. 2-(3/4)=2
9. 2*(3+4)=14
10. 2*(3-4)=-2
11. 2*(3*4)=24
12. 2*(3/4)=0
13. 2/(3+4)=0
14. 2/(3-4)=-2
15. 2/(3*4)=0
16. 2/(3/4)=NAN

* This source code was highlighted with Source Code Highlighter.

Значение NAN обозначает, что в выражении присутствует деление на ноль. Сам подсчет будем делать с помощью перевода в обратную польскую запись, подсчетом значения на лету.
Подсчет значения на лету можно сделать так:

1. string opers = "+-*/";
2. bool calc(INT &f, INT &s, char op, INT &res) {
3.   switch(op) {
4.     case '+' : res = f + s; return true;
5.     case '-' : res = f - s; return true;
6.     case '*' : res = f * s; return true;
7.     case '/' : if (s != 0) {
8.             res = f / s;
9.             return true;
10.           }
11.           return false;
12.   }
13.   return false;
14. }
15. bool calc_last (stack<INT> &val, stack<char> &oper) {
16.   INT s = val.top(); val.pop();
17.   INT f = val.top(); val.pop();
18.   INT r = -1;
19.   if (calc(f,s,oper.top(),r)) {
20.     val.push(r);
21.     oper.pop();
22.     return true;
23.   }
24.   return false;
25. }
26. int prior(char op) {
27.   switch(op) {
28.     case '+':
29.     case '-': return 0;
30.     case '*':
31.     case '/': return 1;
32.   }
33.   return -1;
34. }
35. bool is_num(char c) {
36.   return '0' <= c && c <= '9';
37. }
38. bool calc(const string &expr, INT &res) {
39.   stack<INT> val;
40.   stack<char> oper;
41.   for (int i=0;i<expr.size();++i) {
42.     if (is_num(expr[i]))
43.       val.push(expr[i] - '0');
44.     else if (expr[i] =='(')
45.       oper.push(expr[i]);
46.     else if (expr[i] == ')') {
47.       while (oper.top() != '(') {
48.         if (!calc_last(val, oper))
49.           return false;
50.       }
51.       oper.pop();
52.     }
53.     else { // expr[i] - операция
54.       while (!oper.empty()) {
55.         if (prior(oper.top()) >= prior(expr[i])) {
56.           if (!calc_last(val, oper))
57.             return false;
58.         }
59.         else break;
60.       }
61.       oper.push(expr[i]);
62.     }
63.   }
64.   while (!oper.empty()) {
65.     if (!calc_last(val,oper))
66.       return false;
67.   }
68.   res = val.top();
69.   return true;
70. }

* This source code was highlighted with Source Code Highlighter.

Исходный код: здесь

Отправляем в систему проверки на contester.tsure.ru и получаем вердикт: TLE9. =))
В худшем случае количество операций равно 10, значит общее количество генерируемых размещений будет 4¹⁰=1048576. Получается, что приведенный фрагмент кода подсчета значения выражения на лету будет запускаться более 1 млн. раз. Т.к. в данной задаче нам придется генерировать все размещения, то естественным путем оптимизации исходного решения – минимизировать количество построений обратной польской записи.
Рассмотрим несколько выражений и их обратные польские записи.

Номер     Выражение           Обратная польская запись
1         5*2+3-(7+2)/2       5 2 * 3 + 7 2 + 2 / -
2         5/2-3+(7-2)*2       5 2 / 3 – 7 2 – 2 * + 
3         5+2*3/(7*2)-2       5 2 3 * 7 2 * / + 2 -
4         5-2/3*(7/2)+2       5 2 3 / 7 2 / * – 2 +

Подсчет выражения по обратной польской записи осуществляется за 1 проход.
Т.к. соответствующие операции в выражениях 1 и 2 имеют одинаковые приоритеты, то для них получаются две обратные польские записи, которые можно считать подобными. Тоже самое можно наблюдать для выражений 3 и 4.
Две обратные польские записи назовем подобными, если соответствующие операции имеют одинаковый приоритет.
Все операции можно разбить на две группы:
1. С меньшим приоритетом(0) : + , -
2. С большим приоритетом(1) : * , /

Поэтому изначально можно сгенерировать до 2¹⁰=1024 размещений из приоритетов [0 и 1]. При этом, если на место операции выпадает 0 в размещении это говорит о том, что на ее место будут последовательно поставлены операции с нулевым приоритетом, т.е + или –.
Для выражений с одинаковыми размещениями приоритетов получаются подобные обратные польские записи.

Рассмотрим выражение:              5?2?3?(7?2)?2
Текущее размещение из приоритетов: {1, 0, 0, 0, 1} 
Обратная польская запись:          5 2 [1] 3 [0] 7 2 [0] 2 [1] [0], где [x] – операция с приоритетом x
Как можно заметить, текущая обратная польская запись соответствует 1 и 2 выражению из таблицы.

Далее подумаем, как можно перебрать конкретные знаки, с уже расставленными приоритетами операций.
Для текущего размещения R можно поставить в соответствие два размещения F и S.
При этом длина F равна количеству нулей в размещении R, а длина S – количеству единиц.
Элементы множества F будут состоять из операций с нулевым приоритетом, а S – из элементом с единичным приоритетом.

Номер   Выражение        R              F           S
1       5*2+3-(7+2)/2    {1,0,0,0,1}    {+,-,+}     {*,/}
2       5/2-3+(7-2)*2    {1,0,0,0,1}    {-,+,-}     {/,*}
3       5+2*3/(7*2)-2    {0,1,1,1,0}    {+,-}       {*,/,*}
4       5-2/3*(7/2)+2    {0,1,1,1,0}    {-,+}       {/,*,/}

Все вышеизложенную идею можно описать так. При этом получается, что в худшем случае придется генерировать 2¹⁰=1024 обратных польских записей вместо 4¹⁰=1048576. Благодаря этим преобразованием последнее решение уложилось в 1.5 секунды на сервере проверки.

В целях рефакторинга второй реализации можно скрестить генерацию размещений R и {F,S}.

Получение номера по размещению с повторениями

[Все темы по размещениям]

Теория: Окулов. Дискретная математика. 2008.
Практика: [82. Все строки длины n из k различных символов]

Ранее мы научились генерировать размещение с повторениями по номеру. Как выяснилось вся задача свелась к переводу числа из 10-ой в k-ричную систему счисления. Текущая задача представляет собой обратное действие, следовательно будем переводить “число” из k-ричной в 10-ую систему.

Пусть размещение R = {2, 0, 2, 2, 1, 1, 1, 2}; n = 8; k = 3. Найдем номер этого размещения в лексикографическом порядке.
20221112₃=2*2187+0*729+2*243+2*81+1*27+1*9+1*3+2*1=4374+486+162+27+9+3+2=5063₁₀.

Учитывая, что нумерация всех размещений начинается с 0, получаем что размещение R имеет порядковый номер 5064.

1. typedef unsigned long long ULL;
2. ULL get_num_by_placement_rep(const vector<int> &cur, int n, int k) {
3.   ULL num = 0;
4.   ULL step = 1;
5.   for (int i=cur.size()-1;i>=0;--i) {
6.     num += cur[i] * step;
7.     step *= k;
8.   }
9.   return num;
10. }

* This source code was highlighted with Source Code Highlighter.

Генерация размещения с повторениями по номеру

[Все темы по размещениям]

Теория: Окулов. Дискретная математика. 2008
Практика: [82. Все строки длины n из k различных символов]

Как и ранее алфавитом будем считать первые k цифр начиная с нуля. Длина размещения равна n. Необходимо по номеру сгенерировать размещение с повторениями в лексикографическом порядке.
Для начала давайте рассмотрим все размещения с повторениями для n = 2 и k = 4:

1. 00
2. 01
3. 02
4. 03
5. 10
6. 11
7. 12
8. 13
9. 20
10. 21
11. 22
12. 23
13. 30
14. 31
15. 32
16. 33

Внимательный читатель возможно уже нашел закономерность между порядковым номером и размещением. Если внимательно присмотреться, то можно заметить, что размещения с повторениями это числа в k-ричной системе счисления и их перечисление в лексикографическом порядке полностью совпадает с их перечислением в порядке возрастания.
Проверим наше утверждение на размещении “31”: 31₄=4*3+1=13. Но размещение “31” соответствует 14 размещению. Номер 13 получился, потому что нумерация размещений изначально начинается с 0.
Данная логика отображена в следующей функции:

1. typedef unsigned long long ULL;
2. void gen_placement_rep_by_num(vector<int> &cur, ULL num, int n, int k) {
3.   cur.assign(n,0);
4.   int pos = n - 1;
5.   while (num) {
6.     cur[pos--] = num % k;
7.     num /= k;
8.   }
9. }

* This source code was highlighted with Source Code Highlighter.

Если значения n и k настолько велики, что не помещаются в unsigned long long необходимо использовать длинную арифметику.

Генерация следующего и предыдущего размещения с повторениями

[Все темы по размещениям]

Теория: Окулов. Дискретная математика. 2008.
Практика: [82. Все строки длины n из k различных символов]

Пусть задан алфавит, состоящих из первых k цифр, начиная с 0. Также имеется текущее размещение с повторениями длины n. Найдем следующее размещение с повторениями в лексикографическом порядке.

R_i = {1, 5, 6, 4, 6}; n = 5; k = 7
R_i+1 = {1, 5, 6, 5, 0}

Для генерации следующего размещения будем пользоваться простым правилом:
Перебираем все элементы справа налево. Если текущий элемент равен k-1, тогда обнуляем его и переходим к элементу левее. В противном случае увеличиваем текущий элемент на 1 и заканчиваем генерацию. Если на текущем шаге были перебраны все элемента размещения, но не получилось инкрементировать никакой элемент, значит на текущем шаге мы работали с последним размещением для заданных n и k.

1. bool next_placement_rep(vector<int> &cur, int n, int k) {
2.   int r = 1;
3.   int pos = n-1;
4.   while (pos>=0 && r) {
5.     cur[pos]++;
6.     r = cur[pos] == k;
7.     if (r) cur[pos] = 0;
8.     --pos;
9.   }
10.   return !r;
11. }

* This source code was highlighted with Source Code Highlighter.

Полная реализация: здесь

Генерация предыдущего размещения делается по аналогичной схеме:

1. bool prev_placement_rep(vector<int> &cur, int n, int k) {
2.   int r = 1;
3.   int pos = n-1;
4.   while (pos >=0 && r) {
5.     cur[pos]--;
6.     r = cur[pos] == -1;
7.     if (r) cur[pos] = k-1;
8.     --pos;
9.   }
10.   return !r;
11. }

* This source code was highlighted with Source Code Highlighter.

Генерация всех размещений с повторениями рекурсивным способом

[Все темы по размещениям]

Теория: Окулов. Дискретная математика. 2008
Практика: Все строки длины n из k различных символов

Пусть задан алфавит из K первых цифр, начиная с 0. Необходимо сгенерировать все размещения с повторениями длины N для элементов данного алфавита. Другими словами для N = 2 и K = 4 получаем:

1. 00
2. 01
3. 02
4. 03
5. 10
6. 11
7. 12
8. 13
9. 20
10. 21
11. 22
12. 23
13. 30
14. 31
15. 32
16. 33

Генерация такой последовательности не должно составить большого труда:

1. void gen(int pos) {
2.   if (pos == n) {
3.     for (int i=0;i<n;++i)
4.       printf("%d",cur[i]);
5.     printf("\n");
6.     return;
7.   }
8.   for (int i=0;i<k;++i) {
9.     cur[pos] = i;
10.     gen(pos+1);
11.   }
12. }

* This source code was highlighted with Source Code Highlighter.

Изначально функция gen запускается с параметром 0.
Полное решение: здесь

Генерация размещения без повторений по номеру за O(N*N)

[Все темы по размещениям]

Теория: Окулов. Программирование в алгоритмах. 2004
Практика: [3784. Генерация размещений]

Ранее мы рассмотрели получение номера по размещению за O(N*N). В данной же задаче нужно сделать все с точностью до наоборот:

1. int placement_amount(int n, int m) {
2.   int res = 1;
3.   for (int i = n; i >= n-m+1; --i) {
4.     res *= i;
5.   }
6.   return res;
7. }
8. void gen_placement_by_num(int num, int n, int m, vector<int> &mas) {
9.   vector<bool> usd(n,false);
10.   int _n = n-1, _m = m-1;
11.   for (int i=0;i<m;++i) {
12.     int block_cnt = num / placement_amount(_n,_m);
13.     num -= block_cnt * placement_amount(_n,_m);
14.     int pos = 0;
15.     ++block_cnt;
16.     while (block_cnt) {
17.       if (!usd[pos])
18.         --block_cnt;
19.       ++pos;
20.     }
21.     usd[pos-1] = true;
22.     mas[i] = pos;
23.     --_n; --_m;
24.   }
25. }

* This source code was highlighted with Source Code Highlighter.

При многократном вызове функции gen_placement_by_num можно сделать препроцессинг и не использовать функцию placement_amount.

Получение номера по размещению без повторений за O(N*N)

[Все темы по размещениям]

Теория: Окулов. Программирование в алгоритмах. 2004.
Практика: 192. По размещению!

Рассмотрим все размещения для n = 4 и m = 3:

1. 123
2. 124
3. 132
4. 134
5. 142
6. 143
7. 213
8. 214
9. 231
10. 234
11. 241
12. 243
13. 312
14. 314
15. 321
16. 324
17. 341
18. 342
19. 412
20. 413
21. 421
22. 423
23. 431
24. 432

* This source code was highlighted with Source Code Highlighter.

Можно заметить, что все размещения можно разбить на 4(n) блока. Элементы первого блока начинаются на 1, второго - на 2 и т.д. В каждом блоке находится равное количество элементов равное (n-1)!/(n-m)!. В нашем случае по 6 элементов.
Зная значения n и m и текущее размещение, можно найти размер блока B и определить интервал [L,R], в котором лежат все размещения, начинающиеся на общий первый элемент.
L = B * LESS, где LESS - количество элементов алфавита, меньших первого элемента размещения.
R = L + B – 1.
Далее извлекаем первый элемент размещения из общего алфавита и решает ту же задачу для n`=n-1 и m`=m-1. Рассмотрим идею на конкретном примере:
Пусть n = 9, m = 7. Размещение R = {6, 3, 8, 1, 9, 4, 7}.

Итерация	Размещение	Размер блока	Нижняя граница	Неиспользованный члены
1	6******	8!/2! = 20160	5*20160 = 100800	123456789
2	63*****	7!/2! = 2520	2*2520  =   5040	12345789
3	638****	6!/2! = 360	5*360   =   1800	1245789
4	6381***	5!/2! = 60	0*60    =      0	124579
5	63819**	4!/2! = 12	4*12    =     48	24579
6	638194*	3!/2! = 3	1*3     =      3	2457
7	6381947	2!/2! = 1	2*1     =      2	257

Номер размещения будет равен сумме нижних границ интервалов на каждой итерации:
100800+5040+1800+0+48+3+2 = 107693. Полученный номер был получен с тем расчетом, что изначально все размещения нумеровались с нуля.
Все вышесказанное можно реализовать таким образом:

1. int placement_amount(int n, int m) {
2.   int res = 1;
3.   for (int i = n; i >= n-m+1; --i) {
4.     res *= i;
5.   }
6.   return res;
7. }
8. int get_num_by_placement(const vector<int> &mas, int n, int m) {
9.   vector<bool> usd(n,false);
10.   int res = 0;
11.   int _n = n-1, _m = m-1;
12.   for (int i=0;i<mas.size();++i) {
13.     int amount = 0;
14.     for (int j=0;j<n;++j) {
15.       if (!usd[j]) amount++;
16.       if (mas[i] == j) {
17.         int ampt = (amount - 1) * placement_amount(_n, _m);
18.         res += (amount - 1) * placement_amount(_n, _m);
19.         usd[j] = true;
20.       }
21.     }
22.     usd[mas[i]] = true;
23.     --_n; --_m;
24.   }
25.   return res;
26. }

* This source code was highlighted with Source Code Highlighter.

Генерация следующего и предыдущего размещения без повторений за O(N)

[Все темы по размещениям]

Теория: Окулов. Программирование в алгоритмах. 2004
Практика: K4.Размещения.(dl.gsu.by)

На текущий момент мы умеем генерировать следующее размещение в лексикографическом порядке со сложностью O(N*N) и O(N*log(N)). Сегодня сделаем эту операцию с линейной сложностью. Для этого нужно будет вспомнить алгоритм генерации следующей перестановки в лексикографическом порядке. Для удобства я буду пользовать STL’ным аналогом next_permutation. Итак начнем по порядку.

Пусть n = 9, m = 5. В качестве алфавита будем использовать цифры от 1 до 9. Рассмотрим текущее размещение P_i = {1,2,4,9,8}. Найдем следующее размещение P_i+1 в лексикографическом порядке.
Поставим во взаимно-однозначное соответствие текущему размещению P_i перестановку Perm_i, префикс которой равен Pi, а постфикс формируется из оставшихся минимальных элементов алфавита, не использованных в P_i.

Permi	124983567	Формируем перестановку Permi.
	124987653	Реверсируем хвост перестановки
Permi+1	125346789	Генерируем следующую перестановку в лексикографическом порядке.

Получив перестановку Perm_i+1, отбрасываем хвост и получаем следующее размещение P_i+1= {1,2,5,3,4}.
Если на каком-то этапе не получилось сгенерировать следующую перестановку, значит на текущем этапе обрабатывалось последнее размещение в лексикографическом порядке.

1. bool next_placement(string &perm, int m) {
2.   reverse(perm.begin()+m, perm.end());
3.   return next_permutation(perm.begin(), perm.end());
4. }

* This source code was highlighted with Source Code Highlighter.

Т.к. выполнение реверса хвоста и генерация следующей перестановки имеют сложность O(N), то и генерация следующего размещения так же будет иметь линейную сложность.
Полная реализация: здесь

Генерация предыдущего размещения выполняется таким же образом.

1. bool prev_placement(string &perm, int m) {
2.   reverse(perm.begin()+m, perm.end());
3.   return prev_permutation(perm.begin(), perm.end());
4. }

* This source code was highlighted with Source Code Highlighter.

Полная реализация: здесь

Генерация следующего размещения без повторений за O(N*N) и O(N*log(N))

[Все темы по размещениям]

Теория: Окулов. Программирование в алгоритмах. 2004
Практика: K4.Размещения.(dl.gsu.by)

Пусть n = 9, а m = 6. Рассмотрим текущее размещение P_i = {1,3,6,5,9,8}. Найдем следующее размещение P_i+1 в лексикографическом порядке. Алфавитом в данном случае будет являться набор цифр от 1 до 9.

Для начала разделим все элементы алфавита на две группы: те, что входят в текущее размещение P_i и те, что нет(множество F - свободные члены): 

136598247

Будем последовательно перебирать элементы размещения P_i справа налево. Если на каком-то этапе для текущего элемента размещения P_i[j] можно найти элемент F[k] из свободных членов, который больше его, то заменяем P_i[j] на F[k]. При этом F[k] должен быть минимально возможным. При этом может возникнуть две ситуации:
1) Это сделать удалось. При это нужно дополнить размещение так, чтобы ее размер стал равным m. Для этого на свободные места последовательно добавляем элементы множества F в порядке возрастания начиная с самого маленького.
2) Этого сделать не удалось. Текущий элемент P_i[j] удаляем из текущего размещения и добавляем в множество F. Берем следующий элемент P_i[j-1] и повторяем итерацию. Если же не удалось найти такой элемент, значит на текущей итерации мы работали с последним размещением в лексикографическом порядке.

Давайте получим размещение P_i+1 по вышеизложенным правилам:

Pi   =	136598247	Нет свободного элемента больше 8
	136592478	Нет свободного элемента больше 9
	136524789	Есть 3 свободных элемента больше 5: 7,8,9. Выбираем 7 и меняем их местами
	136724589	Первые 4 элемент размещения Pi+1 определены
Pi+1 =	136724589	Дополняем префикс размещения Pi+1

Данный подход можно реализовать со сложностью O(N*N):

1. string letters = "1234567";
2. bool next_placement(string &cur, vector<bool> &usd, int n, int m) {
3.   int beg = -1;
4.   for (int i=m-1;i>=0;--i) {
5.     if (beg != -1) break;
6.     for (int j=cur[i] - letters[0] + 1; j < n; ++j) {
7.       if (!usd[j]) {
8.         usd[j] = true;
9.         usd[cur[i] - letters[0]] = false;
10.         cur[i] = letters[j];
11.         beg = i;
12.         break;
13.       }
14.     }
15.     if (beg == -1)
16.       usd[cur[i] - letters[0]] = false;
17.   }
18.   if (beg != -1) {
19.     for (int i=beg+1, j = 0; i<m && j<n;++j) {
20.       if (!usd[j]) {
21.         usd[j] = true;
22.         cur[i++] = letters[j];
23.       }
24.     }
25.     return true;
26.   }
27.   else
28.     return false;
29. }

* This source code was highlighted with Source Code Highlighter.

Рассмотрим параметры, передаваемые в функцию next_placement:
1. cur – текущее размещение.
2. usd – массив меток. Если usd[i] == false, значит i-ый элемент алфавита является свободным членом.
Т.к. текущее размещение cur передается по ссылке, то после выполнения функции оно заменится на следующее размещение в лексикографическом порядке.

Полная реализация: здесь

Немного подумав, можно смело заменить массив меток на множество(set) свободных членов, улучшив асимптотику до O(N*log(N)):

1. bool next_placement(string &cur, set<char> &vac, int n, int m) {
2.   set<char>::iterator it;
3.   for (int i=cur.size()-1;i>=0;--i) {
4.     it = vac.lower_bound(cur[i]);
5.     if (it != vac.end()) {
6.       char tmp = cur[i];
7.       cur[i] = *it;
8.       vac.erase(it);
9.       vac.insert(tmp);
10.       for (int pos = i+1; pos < m; ++pos) {
11.         cur[pos] = *vac.begin();
12.         vac.erase(vac.begin());
13.       }
14.       return true;
15.     }
16.     vac.insert(cur[i]);
17.   }
18.   return false;
19. }

* This source code was highlighted with Source Code Highlighter.

Полная реализация: здесь

Генерация всех размещений без повторений рекурсивным способом

[Все темы по размещениям]

Теория: Окулов. Программирование в алгоритмах. 2004
Практика: K4.Размещения.(dl.gsu.by)

Представим, что нужно рассадить N гостей на M мест, при этом может получиться такая ситуация, что некоторые гости останутся стоять. Занумеруем всех гостей числами от 1 до N. А теперь давайте попробуем перечислить все возможные посадки. Пусть N = 4, а M = 3. Получаем:

1. 123
2. 124
3. 132
4. 134
5. 142
6. 143
7. 213
8. 214
9. 231
10. 234
11. 241
12. 243
13. 312
14. 314
15. 321
16. 324
17. 341
18. 342
19. 412
20. 413
21. 421
22. 423
23. 431
24. 432

Чтобы убедиться в том, что ни одна комбинация не была пропущена, найдем общее количество размещений по формуле A(M,N) = N! / (N-M)! = 4! / 1! = 24. Можно двигаться дальше.
Что касается самого принципа генерации, то он полностью совпадает с принципом генерации перестановок без повторений. Тем более, что если N = M, то будет происходить генерация всех перестановок без повторения.

1. int n,m;
2. string letters = "1234567";
3. vector<bool> usd;
4. string res;
6. void placement_lex(int pos) {
7.   if (pos == m) {
8.     printf("%s\n", res.c_str());
9.     return;
10.   }
11.   for (int i=0;i<n;++i) {
12.     if (!usd[i]) {
13.       usd[i] = true;
14.       res[pos] = letters[i];
15.       placement_lex(pos+1);
16.       res[pos] = ' '; // debug only
17.       usd[i] = false;
18.     }
19.   }
20. }
21. int main() {
22.     ...
23.   usd.resize(n);
24.   res.resize(m,' ');
25.   placement_lex(0);
26. }

* This source code was highlighted with Source Code Highlighter.

Решение: здесь

Размещения (placements)

Размещения без повторений
         Вопрос: “Сколькими способами можно разместить N гостей по M местам?” (N >= M)
         Правило: Порядок имеет значение, т.е. картежи {1,4,2} и {2,4,1} являются различными.
         Количество: A(M,N) = N * (N-1) * (N-2) * (N - M + 1) = N! / (N - M)!
1. Генерация всех размещений без повторений
     1.1. Рекурсивная генерация в лексикографическом порядке
          Практика: [K4.Размещения(dl.gsu.by)]
     1.2. Генерация следующего размещения в лексикографическом порядке(без перестановок) O(N*N)
          Практика: [K4.Размещения(dl.gsu.by)]
     1.3. Генерация следующего размещения в лексикографическом порядке(без перестановок) O(logN*N)
          Практика: [K4.Размещения(dl.gsu.by)]
     1.4. Генерация следующего размещения в лексикографическом порядке(с перестановками) O(N)
          Практика: [K4.Размещения(dl.gsu.by)]
     1.5. Генерация предыдущего размещения в лексикографическом порядке                  O(N)
          Практика: [K4.Размещения(dl.gsu.by)]
2. Генерация размещения по номеру L (задаются значения M и N)          O(N*N)
          Практика: [3784. Генерация размещений]
3. Получения номера по размещению (задаются значения M и N)            O(N*N) 
          Практика: [192. По размещению]

Размещения с повторениями
         Вопрос: “Сколько различных букетов можно собрать из K цветков, используя N видов цветов”
         Правило: Порядок имеет значение, т.е. картежи {1,1,5} и {1,5,1} являются различными.
         Количество: A(K,N) = N^K, где N - мощность алфавита, K - длина последовательности
4. Генерация всех размещений без повторений.
     4.1. Рекурсивная генерация в лексикографическом порядке
          Практика: [82. Все строки длины n из k различных символов]
     4.2. Генерация следующего размещения в лексикографическом порядке
          Практика: [82. Все строки длины n из k различных символов]
     4.3. Генерация предыдущего размещения в лексикографическом порядке
          Практика: [83. Все строки длины n из k различных символов в обратном порядке]
5. Генерация размещения по номеру L (задаются значения K и N)
6. Получение номера по размещению (задаются значения K и N)
7. Расстановка знаков в арифметическом выражении