Arranjos de dígitos até um limite
A missão
Problema
Dada uma lista de dígitos distintos e um limite, retorne, em ordem crescente, todos os números que usam cada dígito exatamente uma vez, em alguma ordem, e que não passam do limite. Um número não pode começar com 0, a menos que seja o dígito único 0. Há no máximo 8 dígitos.
Exemplos
Input: digits = [3, 1, 2], limit = 300
Output: [123, 132, 213, 231]
Por quê: 312 e 321 passam do limite, e tentar os dígitos em ordem crescente já gera os números ordenados
Input: digits = [0, 2, 1], limit = 999
Output: [102, 120, 201, 210]
Por quê: arranjos que começam com 0 são pulados, porque 012 na verdade é um número de dois dígitos
Input: digits = [5], limit = 4
Output: []
Por quê: edge case: o único arranjo já passa do limite
Dicas
0 / 3
Monte o número um dígito por vez, marcando cada dígito como usado enquanto ele está no prefixo atual e desmarcando-o quando você recua.
Ordene os dígitos primeiro. Assim, os números saem em ordem crescente sem uma ordenação final, porque cada prefixo é testado a partir do menor próximo dígito.
Faça a poda: um prefixo seguido de mais r dígitos vale pelo menos prefixo × 10 elevado a r. Se isso já passa do limite, todo próximo dígito maior também vai passar, então pare o loop.
- Tempo-alvo
- O(n · n!)
- Espaço-alvo
- O(n!)
Restrições
- digits are distinct
- at most 8 digits
Solução
Este é o template de permutação com um array de usados: escolha um dígito não usado, chame recursivamente e depois libere-o. Ordenar os dígitos primeiro faz a busca visitar os prefixos em ordem crescente, então os resultados já saem ordenados. O limite oferece uma poda (pruning) barata: preencher o resto com qualquer coisa deixa o número pelo menos igual ao prefixo deslocado à esquerda pelas posições restantes; assim, quando esse limite inferior passa do limite, este dígito e todos os maiores podem ser pulados com um break. A regra do zero à esquerda é uma única condição na primeira posição. No pior caso, todos os n! arranjos são montados, então o tempo é O(n × n!) e o espaço é O(n) para a recursão, mais a saída.
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)) # -> []Travou na ideia, e não no código? Permutações explica isso.