Где ошибка в алгоритме пермутаций?

Question

[Kit Scribe]

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

Мой код проходит не все тесты. В чём я ошибся с алгоритмом? И как это можно исправить?

Код

def next_bigger(n):
    origin = n
    n = list(str(n))

    for i in range(len(n), 0, -1):
        n2 = n[::]
        n2[i - 2] = n[i - 1]
        n2[i - 1] = n[i - 2]
        
        if int("".join(n2)) > origin:
            return int("".join(n2))
    return -1

if __name__ == "__main__":
    print(next_bigger(12)) #   -> 21
    print(next_bigger(144)) # -> 414
    print(next_bigger(1234567890)) # -> 1234567980! должно быть 1234567908

Answer 1

[o5a]

Алгоритм должен быть такой: с конца ищем первый символ, такой, что a[i] < a[i+1], так мы определяем наименьший разряд, который сделает число больше предыдущего. Затем нам нужно минимизировать "хвост", чтобы получилось число, ближайшее к исходному (чем меньше хвост, тем оно ближе к исходному). Для этого мы хвост сортируем по возрастанию и переставляем наше число наименьшего разряда с первым числом из хвоста, большим его.

В примере с 1234567890.

1. Ищем цифру наименьшего разряда, когда a[i] < a[i+1]. Это 8, хвост [9, 0].
2. Сортируем хвост [0, 9] и идем по нему в поисках первой цифры, большей нашей 8. Это 9.
3. Переставляем их и возвращаем результат
1234567809 => 1234567908

Comments

[Kit Scribe]

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

[o5a]

Kit Scribe,
Если цифры в числе расположены по убыванию (например 8531), то при любой перестановке цифр мы не сможем получить число, большее этого. Большее число возможно только если на каком-то участке цифры идут в порядке возрастания, например 8351, поэтому мы и ищем такой переходный момент. А ищем с конца, потому что нам надо найти наименьший разряд (который увеличит число), чтобы число оказалось ближайшим к оригинальному.

[Kit Scribe]

o5a, спасибо большое за помощь! Посидев и подумав, через время, получилось реализовать алгоритм

Answer 2

[Andy_U]

Количество перестановок множества длиной N равно N! (факториал). У вас цикл длиной N, т.е. вы не все варианты перебираете. Может быть, конечно, что можно перебирать не все варианты, но из последнего примера явно следует, что одиночными попарными рокировками не обойтись.