Как найти следующее меньшее число, состоящее из тех же цифр?

Благодаря "наводке" Mark Shevchenko написал следующий вариант без permutations. Использовал перестановки. На любых числах работает без задержки. Даже такое "злое" число 12345679088888 отработал с около нулевой задержкой.

from functools import reduce

def next_smaller(input_num):
    num_dig = [int(i) for i in str(input_num)] # раскладываем число на отдельные цифры
    n = len(num_dig) # длина числа потребуется для обхода
    buff = list() # буферный массив для перестановки
    srt = list() # массив для сортировки "хвоста"
    result = -1 #по-умолчанию возвращаем -1 на случай, если ничего не будет найдено
    for i in range(n - 1, 0, -1): # итерируем исходное число с конца (с права на лево)
        for k in range(i - 1, -1, -1): # второй цикл также с "хвоста" но с отступом на один шаг
            if num_dig[k] > num_dig[i]: # если найдено число (которое ближе к "голове") больше, то меняем числа местами
                buff.clear()
                buff = num_dig.copy() # копируем исходный массив чисел
                buff[k], buff[i] = buff[i], buff[k] # меняем найденные числа местами
                if buff[0] > 0: # отсекаем числа, начинающиеся на ноль
                    srt.clear()
                    srt = buff[(k + 1) : :].copy() # копируем хвост числа для сортировки
                    srt.sort(reverse=True) # сортируем хвост числа по убыванию
                    buff[(k + 1) : :] = srt #перезаписываем хвост его отсортированной версией
                    # конвертируем полученный результат в число и сохраняем, если оно максимальное из всех найденных
                    result = max(result,reduce(lambda dig_prev, dig_next: 10*dig_prev + dig_next, buff))
                break # прерываем цикл по k и переходим к поиску следующей пары
    return result

В цикле по i исходное число итерируется один раз от хвоста к голове не доходя то самой первой цифры. Цикл по k срабатывает (n-1) раз, где n - длина исходного числа, каждый раз стартуя от i со смещением в один шаг к голове, т.е. длина цикла по k все время уменьшается по мере перемещения по i. Кроме того, при нахождении первой пары, цикл по k прерывается досрочно.

Проверил данный алгоритм на сайте с тестами для этого задания. Все тесты ОК. Время выполнения в среднем 550ms.

P.S. Функция поддается запуску параллельно в нескольких процессах, но затраты на запуск пула процессов оказались выше, чем синхронное исполнение. Должен быть совсем тяжелый случай, чтобы имело смысл использовать мультизадачность. Отказался от этой идеи, но если кому интересно...

Позвольте свои "пять копеек". На тяжелом числе 1234567908 мне удалось получить чуть более 2-х секунд, применительно к моей машине конечно. На числе 907 просто 0 секунд. Насколько смог протестировать, получился довольно универсальный алгоритм, который отрабатывает любые числа (но это не точно).

from itertools import permutations

input_num = 1234567908 # входное значение

# разбираем число на символы, генерируем комбинации перестановок и собираем список полученных чисел
nums_list = [int(''.join(nums_str)) for nums_str in permutations(str(input_num))]
# Отсекаем все что больше входного значения. Само входное значение тоже отсекаем
nums_truncate = [num for num in nums_list[1::] if num < input_num]
# если полученный список не пуст, ищем максимальное значение, иначе возвращаем -1
result_num = max(nums_truncate) if nums_truncate else -1

Простой алгоритм: составить все перестановки, отсортировать, выбрать предыдущее число, меньшее текущего, работает долго. Если число состоит из N цифр, то количество перестановок N!. Сложность сортировки такого массива равна O(N!×log N!).

Нужен более быстрый алгоритм, корректность которого надо проверить.

Во-первых, попробуем разобраться, когда у нас вообще возможен результат. Что значит, что у нас не может быть числа, меньше исходного?

Посмотрим на примеры: 1234, 357, 689. 1 < 2 < 3 < 4, 3 < 5 < 7, 6 < 8 < 9. Если цифры числа упорядочены от меньшей к большей, то мы имеем наименьшее число.

Посмотрим на число 1243, для которого наименьшим будет 1234. Если мы будем идти от младшей цифры (это 3) к старшей (это 1) и сравнивать две соседние цифры, то обнаружим, что 4 > 3. Нам останется поменять 4 и 3 местами, чтобы получить результат.

Всегда ли достаточно одной перестановки?

Рассмотрим число dd...dd978, где d — какие-то десятичные цифры. Это такое большое число, которое заканчивается на 978. Поменям местами 9 и 8, получим число dd...dd879. Это следующее число, меньшее, чем dd...dd978?

Нет. Следующее число dd...dd897 и чтобы его получить, нужны две перестановки. Это значит, что ни один простой алгоритм с одной перестановкой не даст нам гарантированного результата.

Рассматривая последний результат, мы понимаем, что речь идёт не о произвольной перестановке. По сути, цифры после 8 упорядочиваются в порядке убывания, тогда мы получаем следующее наименьшее число.

Чтобы проиллюстрировать идею, рассмотрим число 236145. Рассматриваем его с конца. Вторая с конца цицфа 4, 4 < 5, всё нормально. Следующая цифра 1, 1 < 5, всё нормально. Далее 6, 6 > 5. Мы нашли позицию, ниже которой можем найти меньшее число.

Переставляем на место 6 самую большую из цифр справа, то есть 5. Остальные цифры упорядочиваем в порядке убывания. Получаем 235641.

Поскольку нам нужно упорядочивать массив, значения которых принимают всего десять значений от '0' до '9', мы можем использовать счётную сортировку. Мы будем получать результат за O(N), где N — длина числа.

Реализацию писать не буду — в Питоне не силён. Но алгоритм, кажется, верный.

чтоб не переделывать твой код можно сделать так:

from itertools import permutations


def next_smaller(n):
    numbers = []
    perm_iter = permutations(list(str(n)))
    for i in perm_iter:
        new_num = int(''.join(i))
        if new_num >= n or len(str(new_num)) != len(str(n)):
            continue
        else:
            numbers.append(new_num)

    numbers.sort(reverse=True)
    for k in numbers:
        if k < n:
            return k
    return -1

def next_smaller2(n):
    if n < 10:
        return n

    text = str(n)
    for l in range(2, len(text) + 1):
        num = int(text[-l:])
        num2 = next_smaller(num)
        if num2 < num and num2 != -1:
            return int(text[:len(text) - l] + str(num2))
    return -1

print(next_smaller2(907))
print(next_smaller2(1234567908))

Вот код раза в полтора побыстрее:

from itertools import permutations


def next_smaller(n):
    perm_iter = permutations(str(n), len(str(n)))
    res = -1
    for i in perm_iter:
        new_num = int(''.join(i))
        if res < new_num < n and i[0] != '0':
            res = new_num

    return res

def next_smaller2(n):
    if n < 10:
        return n

    base = 100
    while base < 10 * n:
        num = n % base
        num2 = next_smaller(num)
        if num2 < num and num2 != -1:
            return (n // base) * base + num2
        base *= 10

    return -1

логика простая - нам не нужно смотреть ВСЕ перестановки цифр, нам надо смотреть перестановки только последних цифр и находить наименьшее число, образованное такими перестановками

сначала смотрим перестановку 2 цифр, не получилось получить меньшее число (например из "09" меньше не получить), дальше смотрим варианты из 3х последних цифр и так далее

в итоге алгоритм работает у меня за 6.230012513697147e-05 сек вместо 1.3 сек :)

С подобной задачей встречался на просторах сети лет 5 назад, но не нашёл сейчас ссылку. Вот примерно вариант без permutations.

def next_smaller(n):
    digits = list(str(n))
    pivot = None
    for i in range(len(digits) - 1, 0, -1):
        if digits[i - 1] > digits[i]:
            pivot = i - 1
            break
    if pivot is None:
        return -1
    for i in range(len(digits) - 1, pivot, -1):
        if digits[i] > digits[pivot]:
            continue
        else:
            digits[i], digits[pivot] = digits[pivot], digits[i]
            break
    suffix = digits[pivot + 1:]
    suffix.sort(reverse=True)
    new_digits = digits[:pivot + 1] + suffix
    return int(''.join(new_digits))

print(next_smaller(907))
print(next_smaller(1234567908))
input("Нажмите Enter для выхода")    

UPDATE. Пока нетрогаю код выше. А если так:

def next_smaller(n):
    digits = sorted(list(str(n)), reverse=True)
    for i in range(n - 1, 0, -1):
        if sorted(list(str(i)), reverse=True) == digits:
            return i
    return -1

print(next_smaller(907))
print(next_smaller(1234567908))
print(next_smaller(414))
input("Нажмите Enter для выхода")   

Отсортировать цифры числа в порядке убывания и вернуть первое число, которое меньше исходного?