Подскажите как оптимизировать код на python, чтобы пройти рандомные тесты на сервере

Измените алгоритм:

1. уберите из него ненужные проверки на очень частные случаи
2. не используйте permutations (этот перебор очень неэффективный)

Алгоритм основывается на нескольких наблюдениях:

1. чтобы получить новое большее число, нужно в записи числа заменить одну из цифр в некоторой позиции j, на большую цифру, которая встречается правее (т.е. в более младшем разряде) в записи числа.
2. чтобы изменение числа при такой замене было минимальное, нужно выбрать позицию j как можно ближе к правому краю числа.
3. чтобы изменение числа было минимальным, нужно оставшиеся цифры упорядочить таким образом, чтоб сначала шли самые маленькие.

Теперь собственно сама программа. Этот алгоритм не требует перебора 2**n (как с permutations, а работает за линейное время (так как для поиска минимальных чисел использует индексную сортировку для цифр или по другому просто их подсчет).

import math

def generate_number_for_digit_counts(digit_counts):
    """ генерирует минимальное число, в котором есть заданное количество цифр
        digit_counts содержит для каждой цифры количество ее вхождений в число.
        см. тест test_order с примерами
    """
    val = 0
    for digit, count in enumerate(digit_counts):
        for _ in range(count):
            val = val * 10 + digit
    return val

def next_bigger(n):
    # количество разрядов в числе
    digits = int(math.log10(n)) + 1
    # k-й элемент содержит количество цифр k, которые встретились при просмотре числа
    digit_counts = 10 * [0]
    # вспомогательное значение, которое используется для выделения разряда
    curr_base = 1
    for j in range(digits, 0, -1): # просматриваем разряды начиная справа
        curr_digit = (n // curr_base) % 10 # выделяем цифру в текущем разряде
        digit_counts[curr_digit] += 1      # увеличиваем счетчик просмотреных 
                                           # для текущей цифры
        # следующий цикл ищет есть ли справа от текущей цифры
        # большая цифра. Ищем такую минимальную
        # начиная от curr_digit + 1 и до 9
        for i in range(curr_digit + 1, 10):
            if (digit_counts[i] == 0): # если цифра і нам не встречалась
                continue               # то переходим к следующей т.е. i+1

            # тут мы оказываемся если цифра i встречалась нам правее от текущей
            # позиции j
            digit_counts[i] -= 1  # цифру i будем ставить в позицию j
                                  # для этого исключaeм ее из тех, которые будем
                                  # размещать справа от позиции j

            # тут составляем новое число
            # у него начало (до позиции j-1) от числа n:
            #      n // curr_base - это цифры от начала до j включительно, т.е.
            #      с curr_digit в самой правой позиции
            # далее идет цифра i:        
            #      - curr_digit + i это замена curr_digit на i в позиции j
            # далее идут остальные цифры числа отсортированные по возрастанию
            return curr_base * (n // curr_base - curr_digit + i) \
                + generate_number_for_digit_counts(digit_counts)

        curr_base *= 10

    return -1

import pytest
@pytest.mark.parametrize("test_input,expected", [
    ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 0),
    ([1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 0),
    ([1, 0, 0, 0, 1, 0, 0, 0, 0, 0], 4),
    ([1, 0, 4, 0, 1, 0, 0, 0, 0, 0], 22224),
])
def test_generate_number_for_digit_counts(test_input, expected):
    assert generate_number_for_digit_counts(test_input) == expected


@pytest.mark.parametrize("test_input,expected", [
    (2017, 2071),
    (2071, 2107),
    (2107, 2170),
    (2701, 2710),
    (2170, 2701),
    (2710, 7012),
    (82734210, 82740123),
    (8273421110, 8274011123),
    (8974421110, 9011124478),
    (91684, 91846)
])
def test_next_bigger(test_input, expected):
    assert next_bigger(test_input) == expected

В общем, проверки индивидуальных случаев я не смотрел, возможно они и нужны на случай очень длинных чисел в проверках, чтобы не гонять варианты впустую. Сам алгоритм вроде вот так нормально работает:

from itertools import permutations

def next_bigger(n):
    zu = None
    for el in permutations(str(n), len(str(n))):
        q = int(''.join(el))
        if q > n:
            if not zu or q < zu:
                zu = q
    if not zu:
        return -1
    return zu 

next_bigger(127643)

Суть в том, что я смотрю все комбинации, но ищу при этом минимальное из чисел, которые больше n.

Можно немного улучшить время, если отказаться от преобразований в int и работать со строками:

def next_bigger(n):
    zu = None
    n = str(n)
    for el in permutations(n, len(n)):
        q = ''.join(el)
        if q > n:
            if not zu or q < zu:
                zu = q
    return int(zu) or -1 

1. Не всегда первое найденное число будет следующим за

2. Первая проверка делается много проще len(set(str(n))) == 1.

3. В проверках вы слишком часто выполняете одни и те же преобразования вроде str(n), len(str(n))), их лучше вынести в переменные.

Попробуйте так:

def next_bigger(n):
    n_s = str(n)
    n_len = len(n_s)
    if len(set(n_s)) == 1:
        return -1
    if n_len == 2:
        k = int(n_s[::-1])
        return k if k>n else -1

    lst = []
    for el in permutations(n_s):
        k = int(''.join(el))
        if k > n:
            lst.append(k)
    return min(lst) if lst else -1  

UPD1:

def next_bigger(n):
    n_lst = list(str(n))
    n_len = len(n_lst)
    new = -1
    if len(set(n_lst)) == 1:
        return -1
    for i in range(n_len-1, 0, -1):
        for j in range(i, -1, -1):
            if n_lst[i] > n_lst[j]:
                n_lst[i], n_lst[j] = n_lst[j], n_lst[i]
                k = int(''.join(n_lst))
                if new == -1 or new > k:
                    new = k
                n_lst[i], n_lst[j] = n_lst[j], n_lst[i]
    return new

Предварительные соображения.

Пусть некоторое число, например, 123456789 мы модифицировали следующим образом:

1. цифру в i-той позиции уменьшили на 1,
2. все цифры левее оставили без изменения,
3. все цифры правее установили в 9:

Исходное:            123 4 56789
Модифицированное:    123 3 99999

Модифицированное число строго меньше, чем исходное. А если девятки в правой части заменить другими цифрами, то модифицированное число станет ещё меньше. Значит, чтобы модифицированное число было больше исходного, самая левая модифицированная цифра не может быть уменьшена.

Теперь модифицируем число так:

1. цифру в i-той позиции увеличим на 1,
2. все цифры левее оставим без изменения,
3. все цифры правее установим в 0:

Исходное:            123 4 56789
Модифицированное:    123 5 00000

Исходное:            123456 7 89
Модифицированное:    123456 8 00

Теперь модифицированное число строго больше, чем исходное. А если нули в правой части заменить другими цифрами, то модифицированное число станет ещё больше. Таким образом, для увеличения числа самая левая модифицированная цифра должна быть увеличена.

Также по приведённому примеру видно, что чем правее находится «самая левая модифицированная цифра», тем меньше изменённое число отличается от исходного.

Алгоритм

Пусть число представлено массивом цифр arr, где arr[0] — старшая цифра числа, arr[arr.length - 1] — младшая цифра числа.

1. В цикле от arr.length - 2 до 0 перебираем цифры до тех пор, пока не найдём такую, которая бы была меньше, чем стоящая справа цифра, т.е. arr[i] < arr[i+1]. Назовём её "опорной".
2. Если такой цифры в массиве нет, то массив представляет невозрастающую последовательность цифр. Следовательно перестановками цифр нельзя сделать число больше. Вернём -1.
3. На данном шаге массив состоит из трёх частей. Цифры слева от опорной, опорная цифра и цифры справа от опорной.

Пример:

     5432   1   987654321

Здесь левая часть — 5432. Опорная цифра — 1. Правая часть — 987654321.

Заметим:

• Левая часть может быть пустым множеством.
• Правая часть содержит по крайней мере одну цифру.
• В правой части есть по крайней мере одна цифра, которая больше чем опорная цифра.
• Невозможно увеличить итоговое число перестановками только в правой части, т.к. цифры в правой части расположены по невозрастанию.

Итак, уже сейчас мы можем нарастить число, обменяв местами опорную цифру и стоящую правее. Следовательно, наращивать цифры в левой части не имеет смысла: получившееся число будет больше, чем если бы мы заменили опорный элемент и всю правую часть на девятки.

Хотелось бы оставить опорную цифру без изменений и нарастить что-нибудь в правой части. Но этого тоже нельзя сделать. Цифры в правой части итак расположены по невозрастанию. Никакими перестановками цифр только в правой части, правую часть не увеличить.

Значит нужно увеличить опорную цифру. Причём увеличить как можно меньше. Найдём справа цифру меньшую среди всех больших, чем опорная и обменяем их местами. Теперь, если даже все цифры справа обнулить, получившееся число будет строго больше чем исходное.

Однако, просто так обнулить правую часть мы не можем — только перестановки. Поэтому отсортируем правую часть по неубыванию цифр.

Продолжаем алгоритм:

4. Запомним опорную цифру в вспомогательной переменной pivot.
5. Найдём в правой части минимальную цифру среди цифр больших, чем опорная. Удалим её из правой части (теперь правая часть может быть пустым множеством) и запишем на место опорной цифры.
6. Сделаем правую часть как можно меньше. Отсортируем правую часть по неубыванию цифр. (Применять непосредственно алгоритм сортировки не обязательно. Т.к. цифры в правой части расположены по невозрастанию, достаточно сделать реверс.)
7. Вставим опорный элемент pivot в правую часть так, чтобы порядок цифр в правой части сохранился.
8. Полученный массив содержит решение задачи.

Все этапы — поиск опорной цифры, поиск в правой части, удаление из правой части, реверс правой части, добавление в правую часть — имеют линейную сложность O(N), где N — количество цифр в массиве arr. Итоговая сложность алгоритма — O(N).

Набросок кода (увы, но код на python написать не могу... Пусть будет JavaScript):

function nextBigger(n) {
    let arr = Number(n).toFixed().split("");
    
    //Ищем индекс опорного элемента
    let pivotIndex = arr.length - 2;
    for ( ; pivotIndex >= 0; --pivotIndex)
        if (arr[pivotIndex] < arr[pivotIndex + 1])
            break;
    if (pivotIndex < 0)
        return -1;
    
    //Извлекаем из массива правую часть и опорный элемент
    //Сразу сделаем реверс правой части
    let right = arr.splice(pivotIndex + 1, arr.length - pivotIndex - 1).reverse();
    let pivot = arr.pop();
    
    //Ищем индекс заменителя опорного элемента
    let pivotRepIndex = right.findIndex(elem => elem > pivot);
    //Извлекаем из правой части заменитель опорного элемента
    let pivotRep = right.splice(pivotRepIndex, 1);
    
    //Ищем позицию в правой части для вставки опорного элемента
    let j = 0;
    for ( ; j < right.length; ++j)
        if (pivot <= right[j])
            break;
    
    //Вставляем опорный элемент в правую часть
    right.splice(j, 0, pivot);
    
    //Объединяем левую часть, заменитель опорного и правую часть.
    arr = arr.concat(pivotRep, right);
    
    return Number(arr.join(""));
}

console.log(nextBigger(12));
console.log(nextBigger(513));
console.log(nextBigger(2017));
console.log(nextBigger(54321987654321));

Используйте алгоритм next_permutation, подобный тому, что используется в C++ STL. Насколько я помню, подобный метод из itertools с дубликатами не так, как нужно, обращается, но своя реализация (время линейное) довольно проста, больше времени будет уходить на разбор по цифрам и сбор назад.

def nextperm(seq):
    i = len(seq) - 2
    while i >= 0 and seq[i] >= seq[i+1]:
        i -= 1
    if i < 0:
        return None
    j = len(seq) - 1
    while seq[j] <= seq[i]:
        j -= 1
    seq[i], seq[j] = seq[j], seq[i]
    seq[i+1:] = reversed(seq[i+1:])
    return seq

s = list(str(534))
n = nextperm(s)
if n:
    print("".join(n))
else:
    print(-1)