Escreva uma função recursiva que dado um número n, gere todas as possíveis combinações com as n primeiras letras do alfabeto. Ex.: n=3. Resposta: A B C, A C B, B A C, B C A, C A B, C B A

Passo 1

O problema pede uma função que, dado um inteiro n, gere todas as permutações das n primeiras letras do alfabeto (isto é, das letras
\mathrm{A},\mathrm{B},\dots até a n-é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”.

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 i em letters, removemos a letra na posição i, 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 +1:]
# chama recursivamente
for p in permuta(resto):
resultado.append([letra] + p)
return resultado

Passo 5

Para usar no problema original, montamos a lista das primeiras n 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

Exercícios relacionados