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

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

Теория: Окулов. Программирование в алгоритмах. 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.

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