Я умею табличку 2^N·N:
2^N даёт маска уже использованных чисел,
N — для какого числа мы хотим узнать позицию.

(Нынче даже массив не очень нужен, операция popcount стала быстрой.)

1. Сначала решение за O(N²). Заведём булевский массив размера N: какие числа мы ещё не видели. Увидев очередной элемент перестановки x, мы хотим прибавить к номеру соответствующий факториал, умноженный на количество ещё не виденных чисел, меньших x. Например, для перестановки 4 1 3 5 2, увидев 4, мы прибавляем 3·4!: ведь мы ещё не видели числа 1, 2 и 3, которые меньше, чем 4. Дальше мы видим 1 и прибавляем 0·3!. Дальше идёт 3, а к ответу прибавляется 1·2!: ведь из чисел, меньших 3, мы ещё не видели только одно число 2. И так далее.

2. Теперь решение с битовым сжатием. Вместо булевского массива будем рассматривать двоичное число, например, типа int. Бывшие элементы булевского массива превращаются в биты этого числа с соответствующими номерами. В остальном решение остаётся прежним.

3. Ускорение: научимся находить, сколько битов с номерами, меньшими заданного, ещё не обнулены в нашем двоичном числе, за O(1). Тогда весь поиск номера будет работать за O(N). Увидев очередное число x, мы берём наши биты, оставляем только первые x - 1 из них (это просто b -> b AND (2^x - 1)) и считаем количество единичных битов.

4. Например, это можно сделать, посчитав для каждого возможного двоичного числа от 0 до 2^N, сколько в нём единичных битов, и сохранив в массиве размера 2^N.

5. В современных процессорах есть инструкция POPCNT, которая делает это без предподсчитанных массивов за O(1).