Ранг строковых перестановок + структура данных

Проблема под рукой:

Given a string. Tell its rank among all its permutations sorted lexicographically.

Вопрос можно решить математически, но мне было интересно, есть ли какой-то другой алгоритмический метод для его вычисления?

Кроме того, если нам нужно хранить все перестановки строк по рангам, как мы можем сгенерировать их эффективно (и какова будет сложность ). Какой должна быть хорошая структура данных для хранения перестановок и которая также эффективна для поиска?

РЕДАКТИРОВАТЬ

Спасибо за подробные ответы на часть генерации перестановок, может ли кто-нибудь также предложить хорошую структуру данных? Я мог думать только о трие-дереве.