Найдите индекс данной перестановки в списке перестановок в лексикографическом заказ [дубликат]

На этот вопрос уже есть ответы здесь :

Закрыто 8 лет назад .

Возможный дубликат:
Данная строка и перестановка строки. Найдите индекс этой переставленной строки в отсортированном списке перестановок строки.

Это вопрос интервью. Пусть есть список перестановок в лексикографическом порядке. Например, 123 , 132 , 213 , 231 , 312 , 321 . Для данной перестановки найдите ее индекс в таком списке. Например, индекс перестановки 213 равен 2 (если мы начинаем с 0).

Тривиально, мы можем использовать алгоритм next_permutation для генерации следующей перестановки в лексикографическом порядке, но это приводит к решению O (N!), что явно невыполнимо. Есть ли лучшее решение?

задан Community 23 May 2017 в 12:03

0 ответов

Другие вопросы по тегам:

algorithm math permutation combinatorics

Найдите индекс данной перестановки в списке перестановок в лексикографическом заказ [дубликат]

0 ответов

Похожие вопросы: