Найдите перестановку по её номеру в лексикографическом порядке. Total — кол-во элементов, К — номер перестановки. Как сократить время программы?

Question

[tumur4]

Как сократить время выполнения программы?

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

[Rsa97]

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

Пример:
Элементы: (a, b, c, d).
Перестановка M=11 (начиная с 0).
Список (a, b, c, d). K₁ = ⌊11/3!⌋ = 1. Элемент 'b'. M' = 10 mod 3! = 5.
Список (a, c, d). K₂ = ⌊5/2!⌋ = 2. Элемент 'd'. M' = 5 mod 2! = 1
Список (a, c). K₃ = ⌊1/1!⌋ = 1. Элемент 'c'. M' = 1 mod 1! = 0
Список (a). K₄ = ⌊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

Comments

[tumur4]

Спасибо.

import math
n = int(input())
k = int(input()) - 1
permutation = list(range(1, n + 1))
result = []
for i in range(n, 0, -1):
    index = k//math.factorial(i-1)
    k = k % math.factorial(i-1)
    result.append(permutation.pop(index))
print(' '.join(map(str, result)))

Answer 2

[Wataru]

Вы генерируете перестановки по одной, пока не отсчитаете 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. Пока не спуститесь до этого момента нужно сразу брать первый незанятый элемент и не считать факториал вообще.