Учитывая массив длины n, мне нужно распечатать лексикографический индекс массива (индексируется с нуля). Лексикографический индекс - это, по сути, место, которое данный массив имел бы, если бы он был помещен в супермассив, содержащий все возможные перестановки исходного массива.
Это оказалось не так уж сложно (Уникальные перестановки элементов), но теперь моя проблема заключается в создании того же алгоритма, но для массива, содержащего дубликаты одного и того же элемента.
Вот пример диаграммы, показывающий некоторые из возможных перестановок небольшого массива и их соответствующие ожидаемые возвращаемые значения:
[0 1 1 2 2]->0
[0 1 2 1 2]->1
[0 1 2 2 1]->2
[0 2 1 1 2]->3
[0 2 1 2 1]->4
[0 2 2 1 1]->5
[1 0 1 2 2]->6
[1 0 2 1 2]->7
[1 0 2 2 1]->8
[1 1 0 2 2]->9
[1 1 2 0 2]->10
[1 1 2 2 0]->11
..
[2 2 1 0 1]->28
[2 2 1 1 0]->29
Самое главное, я хочу сделать это БЕЗ генерации других перестановок для решения проблемы (например, я не хочу генерировать все перестановки меньше заданной перестановки).
Я ищу псевдокод - никакого конкретного языка не требуется, пока я понимаю концепцию. Даже принцип расчета без псевдокода был бы в порядке.
Я видел некоторые реализации, которые делают нечто подобное, но для двоичной строки (содержащей только два различных типа элементов), и они использовали биномиальные коэффициенты, чтобы выполнить работу. Надеюсь, это поможет.
