Permutaciones de dígitos hasta un límite
La misión
Problema
Dada una lista de dígitos distintos y un límite, devuelve en orden creciente todos los números que usan cada dígito exactamente una vez, en algún orden, y que no superan el límite. Un número no puede empezar con 0 salvo que sea el dígito 0 solo. Hay como máximo 8 dígitos.
Ejemplos
Input: digits = [3, 1, 2], limit = 300
Output: [123, 132, 213, 231]
Por qué: 312 y 321 superan el límite, y probar los dígitos en orden creciente produce los números ya ordenados
Input: digits = [0, 2, 1], limit = 999
Output: [102, 120, 201, 210]
Por qué: se descartan los órdenes que empiezan con 0, porque 012 es en realidad un número de dos dígitos
Input: digits = [5], limit = 4
Output: []
Por qué: caso límite: el único orden posible ya supera el límite
Pistas
0 / 3
Construye el número dígito por dígito, marcando cada dígito como usado mientras está en el prefijo actual y desmarcándolo cuando retrocedes.
Ordena los dígitos primero. Así los números salen en orden creciente sin tener que ordenarlos al final, porque cada prefijo se prueba empezando por su menor dígito siguiente.
Poda: un prefijo seguido de r dígitos más vale al menos prefijo × 10 elevado a r. Si eso ya supera el límite, cualquier dígito siguiente mayor también lo hará, así que detén el bucle.
- Tiempo objetivo
- O(n · n!)
- Espacio objetivo
- O(n!)
Restricciones
- digits are distinct
- at most 8 digits
Solución
Es la plantilla de permutaciones con un array (arreglo) de usados: elige un dígito sin usar, llama recursivamente y luego libéralo. Ordenar los dígitos primero hace que la búsqueda visite los prefijos en orden creciente, así que los resultados salen ordenados sin costo extra. El límite da una poda barata: completar el resto con lo que sea hace que el número valga al menos el prefijo desplazado a la izquierda tantas posiciones como falten, así que, en cuanto esa cota supera el límite, este dígito y todos los mayores se pueden saltar con un break. La regla del cero a la izquierda es una sola condición sobre la primera posición. En el peor caso se construyen los n! órdenes, así que el tiempo es O(n × n!) y el espacio es O(n) por la recursión, más la salida.
def orderings_up_to(digits, limit):
digits = sorted(digits) # increasing digits give sorted output
used = [False] * len(digits)
out = []
def place(value, length):
if length == len(digits):
out.append(value)
return
for i, d in enumerate(digits):
if used[i] or (length == 0 and d == 0 and len(digits) > 1):
continue # used already, or a leading zero
nxt = value * 10 + d
if nxt * 10 ** (len(digits) - length - 1) > limit:
break # the smallest completion is too big
used[i] = True
place(nxt, length + 1)
used[i] = False # back out
place(0, 0)
return out
print(orderings_up_to([3, 1, 2], 300)) # -> [123, 132, 213, 231]
print(orderings_up_to([0, 2, 1], 999)) # -> [102, 120, 201, 210]
print(orderings_up_to([5], 4)) # -> []¿Lo que te frena es la idea y no el código? Permutaciones lo explica.