Найдите перестановку по её номеру в лексикографическом порядке. Total — кол-во элементов, К — номер перестановки. Как сократить время программы?
Вы генерируете перестановки по одной, пока не отсчитаете k. Это медленно, потому что k может быть очень большим. Перестановок-то n! - это дофига много.

Надо генерировать ее сразу по номеру.

Посмотрите на первый элемент. У первых (n-1)! перестановок там 1, у следующих (n-1)! - там 2, потом идет группа, начинающихся с 3 и т.д.

Уже вы можете понять в какой группе искомая k-ая перестановка. Тупо floor(k/(n-1)!) (если нумерация с 0 и перестановок и групп). Фактически, формула для первого элемента - a[0] = (k-1)/(n-1)! + 1.

Дальше вы можете выкинуть из рассмотрения первый элемент. Сфокусируйтесь на группе с заданным известным первым элементом. Какой номер искомая перестановка имеет среди этих (n-1)!? Надо из k вычесть количество перестановок c меньшими первыми элементами (их (a[0]-1)*(n-1)!. Потом задача сводится к преведущей - сгенерировать k-ую перестановку среди оставшихся n-1 элементов.

Если использовать какое-нибудь дерево отрезков, чтобы быстро искать j-ый пока не занятый элемент, то все решение будет за O(n log n). Если делать совсем просто - двумя циклами - то будет O(n^2). Гораздо быстрее вашего O(n!).

Надо только аккуратно обработать случаи, когда (n-1)! слишком большое. Фактически, вам надо найти максимальный факториал, который меньше k. Пока не спуститесь до этого момента нужно сразу брать первый незанятый элемент и не считать факториал вообще.
Рассмотрим список всех перестановок в лексикографическом порядке. Этот список содержит N! перестановок. При этом его можно разбить по первому элементу на N непрерывных групп по (N-1)! перестановок.
Таким образом, определить первый элемент перестановки с номером M (начиная с 0) можно как К1=⌊M/(N-1)!⌋ (также, начиная с 0). Внутри группы перестановка будет иметь номер M'=M mod (N-1)!.
Вычеркнем найденный элемент из списка и повторим вычисления, пока не найдём все элементы.

Пример:
Элементы: (a, b, c, d).
Перестановка M=11 (начиная с 0).
Список (a, b, c, d). K1 = ⌊11/3!⌋ = 1. Элемент 'b'. M' = 10 mod 3! = 5.
Список (a, c, d). K2 = ⌊5/2!⌋ = 2. Элемент 'd'. M' = 5 mod 2! = 1
Список (a, c). K3 = ⌊1/1!⌋ = 1. Элемент 'c'. M' = 1 mod 1! = 0
Список (a).  K4 = ⌊0/0!⌋ = 1. Элемент 'a'.
Получили перестановку (b, d, c, a).
Сгенерируем все перестановки и проверим правильность:0: a, b, c, d
1: a, b, d, c
2: a, c, b, d
3: a, c, d, b
4: a, d, b, c
5: a, d, c, b
6: b, a, c, d
7: b, a, d, c
8: b, c, a, d
9: b, c, d, a
10: b, d, a, c
11: b, d, c, a
12: c, a, b, d
13: c, a, d, b
14: c, b, a, d
15: c, b, d, a
16: c, d, a, b
17: c, d, b, a
18: d, a, b, c
19: d, a, c, b
20: d, b, a, c
21: d, b, c, a
22: d, c, a, b
21: d, c, b, a
