Номер по объекту

Материал из Algocode wiki
Перейти к: навигация, поиск

Эта задача обратна по смыслу к генерации объекта по номеру. Но принцип остается тем же. Рассмотрим решение на примере перестановок.

Зададим перестановку $(a_1, a_2, \dots, a_n)$.

Первый элемент - $a_1$. Значит, гарантированно все перестановки, начинающиеся на числа от $1$ до $a_1 - 1$ будут меньше данной. Давайте посчитаем, сколько таких. Их в точности $(n-1)! \cdot (a_1 - 1)$. То есть мы пропустили в лексикографическом порядке $a_1 - 1$ класс перестановок (деление на классы происходит по первому элементу), в каждом классе $(n-1)!$ элементов, потому что один элемент перестановки уже задан, осталось определить порядок остальных $n-1$.

После того как мы прибавили число пропущенных перестановок к счетчику, переходим ко второму элементу, сужая класс рассматриваемых перестановок до тех, что начинаются с $a_1$. Это можно сделать, так как мы учли все перестановки с другим первым элементом. А теперь мы делаем все то же самое, но уже для перестановки из $n-1$ элементов. Заметим, что из нашего поля выпадает элемент $a_1$. Поэтому все оставшиеся числа $a_2, \dots , a_n$ уже нельзя рассматривать просто так. Например, если $a_2 > a_1$, то меньше нас будет не $(a_2 - 1) \cdot (n-2)!$ перестановок, а $(a_2 - 2) \cdot (n-2)!$. Таким образом, нам надо перенумеровать оставшиеся числа номерами от $1$ до $N-1$, сохраняя их относительный порядок, и работать уже с перенумерованной последовательностью.

Пример: перестановки из пяти элементов. Объект : $(2, 4, 5, 1, 3)$

$Num(x)$ будет обозначать порядковый номер числа $x$ в текущем наборе элементов. Например, если остались числа $(1, 2,5, 9, 11)$, то $Num(5) = 3$. Каждый раз пересчитываем $Num$, предварительно вычеркнув все обработанные числа $a_1 \dots a_{k-1}$, если сейчас мы на $a_k$.

  • $a_1 = 2 \Rightarrow ans += (2 - 1) \cdot (5-1)! = 4! = 24$
  • $a_2 = 4 \Rightarrow Num(a_2) = 3 \Rightarrow ans += (3 - 1) \cdot (4 - 1)! = 2 \cdot 6 = 12$
  • $a_3 = 5 \Rightarrow Num(a_3) = 3 \Rightarrow ans += (3 - 1) \cdot (3 - 1)! = 2 \cdot 2 = 4$
  • $a_4 = 1 \Rightarrow Num(a_4) = 1 \Rightarrow ans += 0 $
  • $a_5 = 3 \Rightarrow Num(a_5) = 1 \Rightarrow ans += 0$
  • $ans = 40$



Автор конспекта: Полина Романченко

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