вторник, 20 марта 2012 г.

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

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

Теория: Окулов. Дискретная математика. 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.
Полное решение: здесь

Комментариев нет:

Отправить комментарий