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

[zZoMROT]

Подскажи те, как не таблично пронумеровать перестановки без повторений из k эл-тов? Что-то никак не придумаю.

[Профессор Снэйп]

Что значит "не таблично"?

-- Сб сен 22, 2012 21:18:32 --

Вообще, есть какая-то специальная нумерация, вроде бы даже в языки программирования встроенная. Но чёт не помню её в деталях.

А чем лексикографическое упорядочение перестановок не подходит?

[zZoMROT]

Профессор Снэйп в сообщении #622394 писал(а):

Что значит "не таблично"?

Под этим я подразумевал, что где-то хранится какой перестановке какое число соответствует. Это не очень удобно, если имеется перестановка, например, из 16 элементов. Хотелось бы задать какую-нибудь функцию, сопоставляющую каждой перестановке какое-то число, которую можно было бы программно реализовать. Желательно чтобы эти числа были от 0 до кол-во перестановок

[apriv]

Пронумеруйте их в лексикографическом порядке и осознайте, что есть простенький алгоритм, который по перестановке вычисляет ее номер, а по номеру восстанавливает перестановку.

[gris]

Я так понял, что нужна формула для получении номера перестановки (хотя бы для одного вида нумерации), в котором по строке из k разных k-ричных цифр выдавался номер последовательности. Я было предложил просто использовать эту k-ричную запись, но она годна только для перестановок с повторениями. Ну типа все числа от 1111 до 4444. Как-то ужимать надо.

[EtCetera]

gris в сообщении #622400 писал(а):

Как-то ужимать надо.

Например, так: пусть имеется перестановка $\pi^{(k)}=\left\langle\alpha_{k}^{(k)}\alpha_{k-1}^{(k)}\ldots\alpha_{2}^{(k)}\alpha_{1}^{(k)}\right\rangle$, $\alpha_i^{(k)}\in\{1\ldots k\}$ ($1\le i\le k$), $m=\arg\max\limits_{1\le i\le k}\alpha_i^{(k)}$. Тогда номер перестановки $n^{(k)}\left(\pi^{(k)}\right)=k\cdot n^{(k-1)}\left(\tilde\pi^{(k-1)}\right)+m-1$, где $\tilde\pi^{(k-1)}=\left\langle\alpha_{k-1}^{(k-1)}\alpha_{k-2}^{(k-1)}\ldots\alpha_{m+1}^{(k-1)}\alpha_{m-1}^{(k-1)}\ldots\alpha_{2}^{(k-1)}\alpha_{1}^{(k-1)}\right\rangle$ ($n^{(1)}\left(\pi^{(1)}\right)=0$).
Впрочем, это всего лишь небольшой вклад в отечественный велопром.