понедельник, 12 марта 2012 г.

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

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

Теория: Окулов. Программирование в алгоритмах. 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;
  5. void placement_lex(int pos) {
  6.   if (pos == m) {
  7.     printf("%s\n", res.c_str());
  8.     return;
  9.   }
  10.   for (int i=0;i<n;++i) {
  11.     if (!usd[i]) {
  12.       usd[i] = true;
  13.       res[pos] = letters[i];
  14.       placement_lex(pos+1);
  15.       res[pos] = ' '; // debug only
  16.       usd[i] = false;
  17.     }
  18.   }
  19. }
  20. int main() {
  21.     ...
  22.   usd.resize(n);
  23.   res.resize(m,' ');
  24.   placement_lex(0);
  25. }
* This source code was highlighted with Source Code Highlighter.

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

1 комментарий: