Find the permutation by its number in lexicographic order. Total - number of elements, K - permutation number. How to shorten the program time?

Question

Python

How to reduce program execution time?

total = int(input())
k = int(input())
def find_max_index(permutation):
    for i in range(len(permutation) - 2, -1, -1):
        if permutation[i] < permutation[i+1]:
            return i
    return -1


def find_index_bigger_element(permutation, element):
    for i in range(len(permutation) - 1, -1, -1):
        if permutation[i] > element:
            return i
    return -1


def swap(permutation, i, j):
    permutation[i], permutation[j] = permutation[j], permutation[i]


def reverse_permutation(permutation, index):
    n = len(permutation)
    for i in range(n - 1, index, -1):
        a = permutation.pop(i)
        permutation.append(a)
    return permutation


def permutation_generator(n):
    permutation = list(range(1, n+1))
    index = find_max_index(permutation)
    count = 0
    while index != -1 or count != k:
        count += 1
        element = permutation[index]
        swap_index = find_index_bigger_element(permutation, element)
        swap(permutation, index, swap_index)
        permutation = reverse_permutation(permutation, index)
        if count == k-1:
            print(' '.join(map(str, permutation)))
            break
        index = find_max_index(permutation)
permutation_generator(total)

Answer 1

Consider a list of all permutations in lexicographic order. This list contains N! permutations. Moreover, it can be divided by the first element into N continuous groups by (N-1)! permutations.
Thus, the first element of the permutation with the number M (starting from 0) can be defined as K ₁ =⌊M/(N-1)!⌋ (also starting from 0). Within the group, the permutation will have the number M'=M mod (N-1)!.
We cross out the found element from the list and repeat the calculations until we find all the elements.
Example:
Elements: (a, b, c, d).
Permutation M=11 (starting from 0).
List (a, b, c, d). K ₁ = ⌊11/3!⌋ = 1. Element 'b'. M' = 10 mod 3! = 5.
List (a, c, d). K2 _{_}= ⌊5/2!⌋ = 2. Element 'd'. M' = 5 mod 2! = 1
List (a, c). K ₃ = ⌊1/1!⌋ = 1. Element 'c'. M' = 1 mod 1! = 0
List (a). K ₄ = ⌊0/0!⌋ = 1. Element 'a'.
We got a permutation (b, d, c, a).

Let's generate all the permutations and check the correctness:

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

Answer 2

You generate permutations one at a time until you count k. This is slow because k can be very large. There are n permutations! - that's a hell of a lot.
It is necessary to generate it immediately by number.
Look at the first element. First (n-1)! there are 1 permutations, the next ones have (n-1)! - there are 2, then there is a group, starting with 3, etc.
You can already understand in which group the desired k-th permutation is. Stupidly floor(k/(n-1)!) (if numbering starts from 0 and permutations and groups). In fact, the formula for the first element is - a[0] = (k-1)/(n-1)! + 1.
Then you can drop the first element from consideration. Focus on the group with a given known first element. What is the number of the desired permutation among these (n-1)!? It is necessary to subtract from k the number of permutations with smaller first elements (their(a[0]-1)*(n-1)!. Then the task is reduced to the leading one - to generate the k-th permutation among the remaining n-1 elements.
If we use some segment tree to quickly find the j-th element that is not yet occupied, then the whole solution will be in O(n log n). If to do absolutely simply - two cycles - that will be O(n^2). Much faster than your O(n!).
We just need to carefully handle the cases where (n-1)! too big. In fact, you need to find the maximum factorial that is less than k. Until you go down to this point, you need to immediately take the first unoccupied element and not calculate the factorial at all.