Как оптимизировать код на Python во времени?

Question

[Maksym122]

Вот условия задачи:
За розміщенням знайдіть його номер у лексикографічному порядку.
Вхідні дані:
У першому рядку вхідного файлу знаходяться числа і (1 ≤ ≤
≤ 20). У другому рядку записано попарно різних чисел з діапазону від
1 до - розміщення.
Вихідні дані:
У вихідний файл виведіть єдине число - номер заданого розміщення.
Приклад вхідних даних:
3 2
3 1
Приклад вхідних даних:
5
Пояснення. Розміщенням з елементів по – це впорядкована
вибірка елементів без повторень з множини {1,2,3, … , − 1, }. У
прикладу, наведеного вище, розглядаються вибірки довжиною 2 з 3-х
елементів:
(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)
Розміщення (3, 1) у списку всіх розміщень записано під номером 5
(нумерація розміщень починається із 1)
Непонятные слова можете перевести
Вот мой код:

from itertools import permutations

def find_permutation_number(N, K, permutation):
    all_permutations = permutations(range(1, N + 1), K)
    all_permutations = list(all_permutations)
    permutation_index = all_permutations.index(permutation) + 1
    return permutation_index

N, K = map(int, input().split())
permutation = tuple(map(int, input().split()))

result = find_permutation_number(N, K, permutation)
print(result)

Comments

[Everything_is_bad]

1 если именно python, то освоить модуль profile, найти узкие места, подумать над оптимизацией
2 если вообще, то использовать более оптимальный алгоритм

[Maksym122]

Everything_is_bad, можете, пожалуйста, подказать принцип более оптимального алгоитма?

[Everything_is_bad]

Maksym122, ну так это про алгоритмы, а не про ЯП

[Vindicar]

Непонятные слова можете перевести

Задайся вопросом: кому нужен ответ на вопрос, нам или тебе?
Чем выше читаемость вопроса, тем больше шанс получить ответ.
От такого примечания разит ленью, если честно.

Answer 1

[Vindicar]

Тебе незачем генерировать все возможные перестановки, чтобы найти нужную.
Прочитай внимательно приведённый пример: на каждое изменение первой цифры приходится 3 цифры всего - 1 задействованная = 2 изменения второй цифры. Поэтому, чтобы добраться до первой цифры, равной 3, нужно будет пропустить минимум 4 перестановки: две для смены 1 на 2 и две для смены 2 на 3, так как каждое изменение второй цифры означает одну перестановку. А значит, искомый номер будет не менее 5. Если бы цифр было больше, то каждое изменение второй цифры означало бы более 1 перестановки.
Аналогичные рассуждения выполняешь для последующих цифр, с поправкой на то, что у тебя будет больше задействованных цифр. Таким образом, наращиваешь искомый номер, пока не достигнешь заданной перестановки.

Comments

[Maksym122]

Спасибо!

[Maksym122]

def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

def calculate_placement_number(N, K, placement):
    placement_number = 0
    available_numbers = list(range(1, N + 1))

    for i in range(K):
        position = placement[i]
        index = available_numbers.index(position)
        placement_number += index * factorial(N - i - 1)
        available_numbers.pop(index)

    return placement_number + 1

N, K = map(int, input().split())
placement = list(map(int, input().split()))

placement_number = calculate_placement_number(N, K, placement)
print(placement_number)

placement_number = calculate_placement_number(N, K, placement)
print(placement_number)

Только 30% тестов правильные, в чем может быть проблема?

[Vindicar]

Maksym122, отредактируй комментарий, оформи код кнопкой </>. Без отступов код нечитаем же.

[Maksym122]

Vindicar, готово

[Vindicar]

Maksym122, первое, что бросается в глаза: число перестановок.
Пусть у тебя N=5 возможных цифр, и ты считаешь перестановки по k=3 цифры.
Тогда число перестановок будет не (N-k-1)!, а N!/k!.

И второй момент, не пойму, учёл ли ты его: число перестановок для цифр справа от текущей, надо умножать не на текущую цифру - 1. Нужно иметь ввиду, что некоторые значения текущей цифры могут быть уже "заняты" предыдущими цифрами. Упрощённо, если в перестановке первая цифра 1, то вторая цифра может начаться только с 2.

[Maksym122]

Vindicar, Спасибо большое!! Прошло! Можно пожалйста еще спросить что не так с кодом в одной задаче?

[Maksym122]

Vindicar, Двоичная цифра.
Некоторая последовательность двоичных цифр получается следующим образом:
―первой записывается цифра 1;
―для получения следующей последовательности цифр необходимо все предыдущие
инвертировать, то есть вместо 0 записать 1 и наоборот.
Например, на 5-м шаге формирования последовательности она будет выглядеть так:
1 0 0 1 0 1 1 0 | 0 1 1 0 1 0 0 1.
Определить, какая двоичная цифра будет находиться на -м месте в данной
последовательности.
Входные данные:
В первой строке входного потока данных записано число 1 ≤ ≤ 15000 –
количество тестовых случаев; в следующих строках – порядковый номер двоичной
цифры , 1 ≤ ≤ 2
31 − 1, для которой нужно решить задачу.
Исходные данные:
Соответствующее значение двоичной цифры, каждое значение в отдельной строке.
Пример входящих данных:
2 (количество входных данных)
5
6
Пример исходных данных:
1 (ответ для 5)
0 (ответ для 6)

def invert_binary(binary, d):
    for i in range(1, d+1):
        binary = binary[:i] + str(1 - int(binary[i-1])) + binary[i:]
    return binary
data=[]
N = int(input())
for _ in range(N):
    d = int(input())
    binary = "1"
    result = invert_binary(binary, d)
    data.append(result[d-1])
for i in range(N):
    print(data[i])

Возможно я неправильно понял условия задачи?

[Vindicar]

Maksym122, это лучше в отдельный вопрос - только обязательно вместе со своим кодом, иначе вопрос могут снести как задание.

[Maksym122]

Vindicar, Почему код не работает?