Получения номера по перестановке: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «=Задача= Дана перестановка, требуется получить ее номер в лексикографическом порядке =И...»)
 
 
Строка 8: Строка 8:
 
=Решение=
 
=Решение=
  
Номер перестановки = $\sum \limit_{i} \sum \limit_{i < j} a[i] > a[j] \cdot (n - i)!$
+
Номер перестановки = $\sum \limits_{i} \sum \limits_{i < j} a[i] > a[j] \cdot (n - i)!$
  
 
{{Автор|Глеб Лобанов|glebodin}}
 
{{Автор|Глеб Лобанов|glebodin}}
  
 
[[Категория:Конспект]]
 
[[Категория:Конспект]]

Текущая версия на 14:54, 6 февраля 2021

Задача

Дана перестановка, требуется получить ее номер в лексикографическом порядке

Идея

Заметим, что для каждой позиции нас интересует только то сколько меньших лексикографически вариантов могло стоять на этой позиции, так как любой вариант меньше на этой позиции дает меньшие перестановки независимо от суффикса, следовательно давайте для каждой позиции посчитаем сумму сколько вариантов меньше из-за того, что число на этой позиции меньше

Решение

Номер перестановки = $\sum \limits_{i} \sum \limits_{i < j} a[i] > a[j] \cdot (n - i)!$



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin