вторник, 8 февраля 2011 г.

Часть 2. Генерация перестановок без повторений. Episode 1

[Все темы по перестановкам]

Теория:
1) Липский. Комбинаторика для программистов. 1988
2) Меньшиков. Олимпиадные задачи по программированию. 2006.

Рассмотрим две задачи:
1) Рекурсивный способ генерации всех перестановок в лексикографическом порядке.
2) Рекурсивный способ генерации всех перестановок в антилексикографическом порядке.

Для начала разберемся, что такое лексико- и антилексико-графические порядки.
Начальная перестановка: {1, 2, 3}

Лексикографический

Антилексикографический

0 1 2 3 1 2 3
1 1 3 2 2 1 3
2 2 1 3 1 3 2
3 2 3 1 3 1 2
4 3 1 2 2 3 1
5 3 2 1 3 2 1

Напомним, что лексикографический порядок – это порядок слов, который используется в словарях.
Слово A меньше слова B, если первые i символов слов равны, а символ A[i+1] < B[i+1]. Отсюда вытекает следствие, что если слово А является началом слова B, то A < B.

Антилексикографический порядок отличается от лексикографического только тем, что сравнение символов идет справа налево.
Слово A меньше слова B, если последние i символов равны, а символ A[i-1] < B[i-1]. Также следует, что если слово B заканчивается на слово A, то A < B.

Практика:
Решим задачу
2B-Перестановки из задачника Федора Меньшикова двумя рассматриваемыми способами.
Как можно было заметить, оба порядка начинаются с минимальной перестановки {1, 2, 3} и заканчивается максимальной {3, 2, 1}.

1) Генерация всех перестановок в лексикографическом порядке.
  1. int n;
  2. vector<int> p;
  3. vector<bool> used;
  4. string str;
  5. ...
  6. void lex(int pos)
  7. {
  8.   if (pos == n) {
  9.     for (int i=0;i<n;i++)
  10.       cout<<str[p[i]];
  11.     cout<<endl;
  12.     return;
  13.   }
  14.   for (int i=0;i<n;i++) {
  15.     if (!used[i]) {
  16.       used[i] = true;
  17.       p[pos] = i;
  18.  
  19.       lex(pos+1);
  20.      
  21.       p[pos] = 0; // debug only
  22.       used[i] = false;
  23.     }
  24.   }
  25. }
* This source code was highlighted with Source Code Highlighter.

Рекурсивная функция lex(n) генерируется все перестановки из алфавита {0,1,..n-1} длиной n и хранит текущую перестановку в массиве p. Если номер текущей позиции pos == n, тогда сгенерирована следующая перестановка.
[Решение]

2) Генерация всех перестановок в антилексикографическом порядке
Решение полностью идентично, за исключением того, что перестановка формируется с конца
[Решение]

6 комментариев:

  1. Товарищ, прога сочетания генирирует а не перестановки !

    ОтветитьУдалить
  2. Если можете, поясните свою точку зрения.

    Со своей стороны могу добавить, что для генерации сочетаний необходимо множество из N элементов и K (K<=N) элементов, которые необходимо выбрать из N. Пусть мы имеем множество {1,2,3} N = 3. Допустим K=2.
    Если мы говорим о сочетаниях, то далее перечислены все сочетания из N по K:
    A = {1,2}
    B = {1,3}
    C = {2,3}
    Проверяем по формуле С(n,k) = 3!/(2!*1!) = 3. Следовательно больше сочетаний нет.

    Сочетание D = {2,1} не будет входить в исходный набор, т.к. оно равно сочетанию A. Поэтому помним, что для сочетаний порядок элементов не важен. Если же важен порядок, то тут уже речь идет о размещениях.

    ОтветитьУдалить
  3. Видимо предыдущий оратор намекал на то, что сложность вашего алгоритма - pow(N, N), в то время как для оптимальный алгоритм должен иметь сложность fact(N).

    ОтветитьУдалить
    Ответы
    1. Предыдущий оратор не знает разницы между сочетаниями и перестановками. И если несложно поясните оценку pow(N,N)

      Удалить
    2. Этот комментарий был удален автором.

      Удалить
    3. У вас на каждом рекурсивном шаге цикл пробегает от 0...n-1, for (int i=0;i<n;i++), если вы будете запускать его с текущей позиции pos, то будет факториал, вот пример: http://www.cyberforum.ru/cpp-beginners/thread444081.html
      Хотя перестановки не будут упорядоченны лексикографически

      Удалить