2388. Номер по перестановке

Дана перестановка из n чисел от 1 до n. Найдите её номер в лексикографическом порядке.

Вход. Первая строка содержит целое число n (1 ≤ n ≤ 12). В следующей строке задается перестановка из n чисел.

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

Пример входа	Пример выхода
3 2 1 3	3

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Пусть m₁m₂…m_n – входная перестановка. Обозначим через d_i количество таких пар (i, j), что i < j и m[i] > m[j] (элементы m[i] и m[j] образуют инверсию). То есть d_i равно количеству таких чисел, которые стоят правее от i-ой позиции и меньше m[i].

Тогда номер перестановки в лексикографическом порядке определяется по формуле:

d₁ * (n – 1)! + d₂ * (n – 2)! + … + d_n-1 * 1! + 1

Пример

Для перестановки (2, 1, 3) массив d = (1, 0, 0). Номер перестановки равен 1 * 2! + 1 = 3.

Для перестановки (1, 4, 3, 2) массив d = (0, 2, 1, 0). Номер перестановки равен 0 * 3! + 2 * 2! + 1 * 1! + 1 = 6.

Для перестановки (3, 2, 1, 4) массив d = (2, 1, 0, 0). Номер перестановки равен 2 * 3! + 1 * 2! + 0 * 1! + 1 = 15.

Для лексикографически наименьшей перестановки (1, 2, …, n) массив d = (0, 0, …, 0). Ее номер равен 1, так как все слагаемые кроме последнего равны нулю.

Для лексикографически наибольшей перестановки (n, n – 1, n – 2, …, 1) массив d = (n – 1, n – 2, n – 3, …, 0). Ее номер равен (n – 1) * (n – 1)! + (n – 2) * (n – 2)! + … + 1 * 1! + 1 = n! Эту формулу можно доказать методом математической индукции:

База индукции. 1 = 1!.

Шаг индукции. n! + n * n! = n! (1 + n) = (n + 1)!

Реализация алгоритма

Входную перестановку храним в массиве m. В массиве fact вычислим факториалы чисел: fact[i] = i!

#define MAX 13

int fact[MAX], m[MAX];

Основная часть программы. Читаем входную перестановку в массив m.

scanf("%d",&n);

for(i = 1; i <= n; i++) scanf("%d",&m[i]);

Заполняем массив факториалов чисел.

fact[0] = 1;

for(i = 1; i <= n; i++) fact[i] = fact[i-1] * i;

В переменной res вычисляем номер перестановки в лексикографическом порядке.

res = 0;

for(i = 1; i <= n; i++)

{

Для заданного значения i в переменной inv подсчитываем количество d_i таких элементов m[j], для которых i < j и m[i] > m[j].

inv = 0;

for(j = i + 1; j <= n; j++)

if (m[j] < m[i]) inv++;

Добавляем к результату значение d_i * (n – i)!

res += inv * fact[n-i];

}

Выводим ответ.

printf("%d\n",res + 1);

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m[] = new int[13];

for(int i = 1; i <= n; i++)

m[i] = con.nextInt();

int fact[] = new int[13];

fact[0] = 1;

for(int i = 1; i <= n; i++)

fact[i] = fact[i-1] * i;

int res = 0;

for(int i = 1; i <= n; i++)

{

int inv = 0;

for(int j = i + 1; j <= n; j++)

if (m[j] < m[i]) inv++;

res += inv * fact[n-i];

}

System.out.println(res + 1);

con.close();

}

}