9.3 Генерация перестановок

Перестановки - это множества, состоящие из одних и тех же элементов и отличающиеся только порядком расположения этих элементов. Возьмем n различных элементов {a1, a2, a3, . . . , an} и переставим эти элементы всевозможными способами, оставляя без изменения числа элементов, меняя только порядок их расположения.Обозначим общее число полученных таким образом перестановок P_n. Число перестановок вычисляется по следующей формуле:

(9.2)

Наша цель состоит в том, чтобы построить алгоритм генерации перестановки по заданному номеру и алгоритм нумерации перестановки. Для этого рассмотрим рис. 9.1, на котором показан фрагмент дерева для получения перестановок множества символов {a, b, c}.

Корень этого дерева содержит первый символ «a», при этом слева и справа от этого символа записаны кружки, которые показывают, где может находиться следующий символ «b» относительно «a». Выходные дуги из корня показывают варианты перехода (их всего два). Символ «c» для каждого варианта может находиться в трех позициях, отмеченных кружками. Соответственно, из каждой вершины «ba» и «ab» следует по три дуги. Это дает 6 вариантов перестановок. Построение дерева перестановок можно продолжить для 4 элементов. Из каждого узла, содержащего 3 элемента, будет выходить по 4 дуги. Вариантов перестановок будет 24.

Задавая путь в таком дереве, можно получить некоторую перестановку. Алгоритм построения перестановки по дереву основан на операциях сдвига и вставки. Берется первый элемент и ставится в позицию 1, берется i-й элемент и определяется его позиция j(0 < j < i). Все элементы, стоящие справа от j-го элемента, сдвигаются на одну позицию вправо, сдвиг начинается с j-го. На место j-го элемента становится данный i-й элемент.

Рассмотрим теперь вопросы генерации перестановки по ее номеру. Пусть задано множество E = {a1, a2, a3, . . . , an} и некоторое целое число k, удовлетворяющее условию

0 < k <= n!

Необходимо найти k-ю перестановку. Для того, чтобы найти заданную перестановку, необходимо по числу k найти позицию каждого элемента ai и использовать вышеизложенный алгоритм построения перестановки. Номера позиций вычисляются следующим образом:

Тогда алгоритм генерации k-й перестановки множества E = {a1, a2, a3, . . . , an} будет следующий:

1. i = 1 в элемент массива v[i] = a1;
2. если i > n, конец;
3. вычислить pi = k mod i , k = k/i;
4. выполнить операцию сдвига вправо в массиве v относительно позиции pi ; v[pi] = ai;
5. i = i + 1, перейти на шаг 2.

Назовем этот алгоритм GPermutation.
Ниже приведены функции для реализации предложенного алгоритма генерации:

Функция вставки номера в массив перестановки

void Insert(int v[ ], int n, int i, int a)
{
      for (int j=n-2; j>=i; j--) v[j+1]=v[j]; //сдвиг
      v[i]=a; //вставка
}

Функция генерации перестановки по заданному номеру

void GeneratePermutation(int v[ ], int n, int k)
{
      int pos;
      v[0]=1;
      for (int i=2; i<=n; i++){
            pos=k%i;
            k=k/i;
            Insert (v,i,pos,i);
      }
}