When you have a candidate number that needs to change, I would suggest making a directed search in the (virtual) list of permutations to find the permutation whose value is as close as possible to the value you compared with in order to restore the strictly ascending order.
It is not necessary to generate all permutations for this, which would consume too much time and space when the number of digits in the input numbers exceeds 10.
The idea is to count the number of digits you have of each digit, in the number that needs a permutation, and then take the next digit for building a permutation in such a way that you stay as close as possible to the target value. Some backtracking is needed, but for each digit position at most 2 attempts are needed: one for a digit that exactly matches the digit in the target (the value to compare with), and potentially a second attempt with another digit.
Here is an implementation of that idea.
First a helper function to find a permutation of a given value that is as near as possible to a target value (but not equal to it), and must be either less or greater (last argument controls this):
def permute_near(value, target, side=1):
# If side is 1, we will look for the minimum permutation of value that is
# greater than the target.
# If side is -1, we will look for the maximum permutation of value that is
# less than the target.
freedigit = 0 if side == 1 else 9
end = freedigit + 10*side
target += side
# Get a count for each digit of value (could also use Counter module for this)
s = str(value)
n = len(s)
digits = [0]*10
for digit in s:
digits[int(digit)] += 1
# Pad the target value to have the same number of digits
limit = [int(digit) for digit in str(target).rjust(n, "0")]
# Use recursion to find the permutation of value that is nearest to the target
def recur(k, isfree, accumulator):
if k >= n: # All digits were processed, we have the result
return accumulator
limitdigit = limit[k]
for i in range(freedigit if isfree else limitdigit, end, side):
if digits[i]:
digits[i] -= 1 # Select this digit for the permutation
permutation = recur(k + 1, isfree or i != limitdigit, accumulator * 10 + i)
digits[i] += 1 # Backtrack
if permutation > -1 or i != limitdigit:
return permutation
# If it failed for the case where the chosen digit was the same
# as in the target, try with one alternative digit in a
# second and also last iteration of this loop.
return -1
return recur(0, False, 0)
Here is the main function:
def solution(numbers):
try:
# Find the first index where the next value is not greater
i = next(i for i, val in enumerate(numbers) if val >= numbers[i+1])
except:
return numbers # The input is already completely ascending
# Permute numbers[i], so it becomes less than its successor
result = permute_near(numbers[i], numbers[i+1], -1)
# Check that such permutation exists, and is still greater than its predecessor
if result >= 0 and (i == 0 or numbers[i - 1] < result):
numbers[i] = result # OK, we have success
else:
# ... or permute numbers[i+1], so it becomes greater than its predecessor
result = permute_near(numbers[i+1], numbers[i], 1)
# Check that such permutation exists, and is still less than its successor
if result >= 0 and (i + 2 >= len(numbers) or result < numbers[i + 2]):
numbers[i + 1] = result # OK, we have success
if all(a < b for a, b in zip(numbers, numbers[1:])):
return numbers
Some runs:
# A few test cases
print(solution([2,4,800,12])) # [2, 4, 8, 12]
print(solution([44,37,74])) # [44, 73, 74]
print(solution([52,53,36])) # [52, 53, 63]
print(solution([64,52,53])) # [46, 52, 53]
print(solution([89221173000,89221173456,13437127829,89221173477]))
# [89221173000, 89221173456, 89221173473, 89221173477]
The function returns the adjusted list if there is a solution, None otherwise.
