Escreva uma função recursiva que dado um número
, gere todas as possíveis combinações com as
primeiras letras do alfabeto. Ex.:
. Resposta:
Passo 1
O problema pede uma função que, dado um inteiro
, gere todas as permutações das
primeiras letras do alfabeto (isto é, das letras
até a
-ésima).
Conteúdo: recursão e geração de permutações.
Vamos usar o princípio de “pegar cada letra como primeira e permutar o resto”.
Conteúdo: recursão e geração de permutações.
Vamos usar o princípio de “pegar cada letra como primeira e permutar o resto”.
Passo 2
Definimos uma função recursiva
permuta(letters)
que recebe uma lista de letras.- Caso base: se
letters
tiver exatamente uma letra, só há uma permutação: ela mesma. - Passo recursivo: para cada índice
em letters
, removemos a letra na posição, permutamos o restante recursivamente e inserimos a letra removida na frente de cada permutação obtida.
Passo 3
Em pseudocódigo Python, isso fica assim:
def permuta(letters):
# caso base
if len(letters) \(==1\):
return [letters.copy()]
resultado \(=\) []
Passo 4
for i in range(len(letters)):
letra letters[i]
resto letters[:i]
letters[i
:]
# chama recursivamente
for p in permuta(resto):
resultado.append([letra] p)
return resultado
letra
resto
# chama recursivamente
for p in permuta(resto):
resultado.append([letra]
return resultado
Passo 5
Para usar no problema original, montamos a lista das primeiras
letras e chamamos:
import string
def \(todas_permutacoes\)(n):
letras \(=\) list(string.\(ascii_uppercase\)[:n])
return permuta(letras)
# Exemplo de uso para n\(=3\)
for p in \(todas_permutacoes\)(\(3\)):
print(' '.join(p))
Resposta
def permuta(letters):
if len(letters) \(==1\):
return [letters.copy()]
resultado \(=\) []
for i in range(len(letters)):
letra \(=\) letters[i]
resto \(=\) letters[:i] \(+\) letters[i\(+1\):]
for p in permuta(resto):
resultado.append([letra] \(+\) p)
return resultado
import string
def \(todas_permutacoes\)(n):
letras \(=\) list(string.\(ascii_uppercase\)[:n])
return permuta(letras)
# Exemplo: n \(=3\)
# Saída:
# A B C
# A C B
# B A C
# B C A
# C A B
# C B A