пятница, 11 февраля 2011 г.

Часть 4. Генерация перестановки по номеру и получение номера по перестановке

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

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

Рассмотрим две задачи:
1) Генерация перестановки по номеру
2) Получение номера по перестановке

Генерация перестановок происходит в лексикографическом порядке. Нумерация перестановок начинается с единицы.

Практика: 
Обе задачи реализуем на основе problem Перестановка по номеру.

1) Генерация перестановки по номеру
Вся необходимая теория довольно популярно изложена в книге Окулова. Остановлюсь на некоторых моментах. Перестановку будем последовательно получать слева направо. Сначала мы имеем N пустых позиций перестановки. Если выписать в столбец все перестановки в лексикографическом порядке то увидим, что их можно разбить на N групп размерностью по (N-1)! каждая. Зная номер перестановки можно без проблем определить в какую группу она попадет. Номер группы и уже полученное начало перестановки однозначно определяют текущий элемент перестановки.
Общую логику передает функция permutation_by_num:

  1. int fact[13] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,  39916800, 479001600};
  2. int notUsed(vector<bool> &used, int blockNum) {
  3.  
  4.   int j, pos = 0;
  5.   for (j = 1; j < used.size(); j++) {
  6.     if (!used[j]) pos++;
  7.     if (blockNum == pos)
  8.       break;
  9.   }
  10.   return j;
  11. }
  12. vector<int> permutation_by_num(int n, int num) {
  13.  
  14.   vector<int> res(n); 
  15.   vector<bool> used(n+1,false);
  16.  
  17.   for (int i = 0; i < n; i++) {
  18.     int blockNum = (num - 1) / fact[n - i - 1] + 1;
  19.     int j = notUsed(used, blockNum);
  20.     res[i] = j;
  21.     used[j] = true;
  22.     num = (num - 1) % fact[n - i - 1] + 1;
  23.   }
  24.   return res;
  25. }
* This source code was highlighted with Source Code Highlighter.

[Решение]

2) Получение номера по перестановке
Для решения этой задачи в первую очередь нужно понять принцип решения первой задачи, а потом проделать обратные манипуляции.
Мне не удалось найти problem, которая в чистом виде решает поставленную задачу. Но у нас есть problem Перестановка по номеру, на основе которой можно проверить правильность решения этой задачи.

[Решение]

4 комментария:

  1. Ссылка на второе решение не работает

    ОтветитьУдалить
    Ответы
    1. Да, к нашему удивлению, код был заменен спамом. В скором времени поправим.

      Удалить
    2. спустя 5 лет, так и не поправили

      Удалить
    3. Скоро поправим, не переживайте.

      Удалить