Afinidades entre pessoas podem ser descritas através de dicionários. Por exemplo, se tivermos:
  • Leo gosta de Sofia,
  • Marcos gosta de Andrea,
  • Sofia gosta de Leo,
  • Alex gosta de Andrea, e
  • Andrea gosta de Marcos
Podemos representar estas relações através do dicionário: afinidades = {‘Leo’: ‘Sofia’, ‘Marcos’: ‘Andrea’, ‘Sofia’: ‘Leo’, ‘Alex’: ‘Andrea’, ‘Andrea’: ‘Marcos’ }
Escreva uma função que recebe um dicionário de afinidades e retorna uma lista de pares com afinidade mútua, ou seja, onde um gosta do outro. Por exemplo, para o dicionário acima, a função deve retornar:
[(‘Marcos’, ‘Andrea’), (‘Sofia’, ‘Leo’)]

Passo 1

O enunciado dá um dicionário que representa “quem gosta de quem”: cada chave é uma pessoa e o valor associado é a pessoa que essa chave gosta. Exemplo dado (peguei os nomes do enunciado):
  • {‘Leo’: ‘Sofia’, ‘Marcos’: ‘Andrea’, ‘Sofia’: ‘Leo’, ‘Alex’: ‘Andrea’, ‘Andrea’: ‘Marcos’}
O que o problema pede:
  • Escrever uma função que recebe um dicionário de afinidades e retorna uma lista de pares com afinidade mútua, isto é, pares (A,B) tais que A gosta de B e B gosta de A.
Observações importantes que vêm do enunciado e precisamos considerar:
  • O dicionário tem pares “quem” -> “quem gosta”.
  • Quando A e B são mutuamente ligados, a função deve listar esse par exatamente uma vez (não repetir (A,B) e (B,A)).
  • Em geral, devemos ignorar casos em que a pessoa gosta de si mesma (por segurança), a menos que o enunciado pedisse o contrário (não pediu).
  • Não foi especificada ordem exigida na lista resultante; vamos manter uma ordem natural de iteração do dicionário (inserção) e garantir que cada par mútuo apareça apenas uma vez.

Passo 2

Escolha do método (explicando como pensar como se estivesse na prova):
  • Método direto e simples (o mais básico e seguro para uma prova): percorrer todas as entradas do dicionário e, para cada pessoa a e seu valor b:
    1. Verificar se b está presente como chave no dicionário (ou seja, se sabemos para quem b gosta).
    2. Verificar se o dicionário diz que b gosta de a, isto é, se a afinidade é recíproca.
    3. Evitar adicionar o par duas vezes (quando depois encontrarmos a entrada b a). Uma maneira simples de evitar duplicação é: só adicionar (a,b) se ainda não tivermos adicionado (b,a).
  • Isso usa operações muito básicas sobre dicionários que costumam cair em prova: iterar com items(), buscar por chave com get() ou indexing, e testar pertença em uma estrutura auxiliar (por exemplo, um conjunto).
Por que essa escolha?
  • É direto, usa só operações básicas (iteração e comparação) e é eficiente: cada par é verificado em tempo constante e percorremos o dicionário uma vez → complexidade linear O(n).
  • Evita técnicas mais avançadas (ex.: construir grafos e procurar componentes) que são desnecessárias aqui.

Passo 3

Conceitos básicos (mini-aula prática sobre dicionários e as operações que vamos usar):
  • Dicionário: estrutura que associa chaves a valores; em Python escreve-se algo como affinities = {‘A’: ‘B’, …}.
  • Iteração com .items(): para cada par chave-valor (k,v) em affinities.items() obtemos os dois juntos; isso é útil para verificar “quem gosta de quem”.
  • Obter valor de uma chave: affinities.get(key) retorna o valor associado se existir, ou \text{None} (ou um valor default) se não existir. Usar .get evita KeyError se a chave não estiver presente.
  • Evitar duplicação: manter um conjunto auxiliar ( \text{seen}) com pares já adicionados. Para verificar se já adicionamos o par oposto, podemos testar se (b,a) está em \text{seen}. Um conjunto tem busca em tempo constante.
Exemplo concreto com o dicionário do enunciado (passo a passo de iteração):
  • Iteramos as entradas na ordem de inserção (supondo Python 3.7+):
    1. a=“Leo”, b=“Sofia”. Checamos affinities.get(“Sofia”) que é “Leo”. Como isso iguala a e a \neq b, temos mutualidade. Como ainda não adicionamos (“Sofia”,“Leo”), adicionamos (“Leo”,“Sofia”).
    2. a=“Marcos”, b=“Andrea”. affinities.get(“Andrea”) é “Marcos” → mutuo. Ainda não adicionamos (“Andrea”,“Marcos”), então adicionamos (“Marcos”,“Andrea”).
    3. a=“Sofia”, b=“Leo”. affinities.get(“Leo”) é “Sofia” → mutuo. Mas aqui já adicionamos (“Leo”,“Sofia”) no passo 1, então testamos se (“Leo”,“Sofia”) está em seen; está, então não adicionamos (“Sofia”,“Leo”) de novo.
    4. a=“Alex”, b=“Andrea”. affinities.get(“Andrea”) é “Marcos”, não é “Alex” → não é mútuo.
    5. a=“Andrea”, b=“Marcos”. affinities.get(“Marcos”) é “Andrea” → mutuo, mas já temos (“Marcos”,“Andrea”) em seen, então não adicionamos (“Andrea”,“Marcos”) novamente.
  • Resultado final (na ordem em que foram adicionados): [(“Leo”,“Sofia”), (“Marcos”,“Andrea”)].
  • Observação: o enunciado mostrou [('Marcos','Andrea'), ('Sofia','Leo')] — a ordem entre pares pode variar dependendo da ordem de iteração do dicionário. O importante é que cada par mútuo apareça exatamente uma vez. O algoritmo acima preserva a ordem natural de iteração do dicionário e não repete pares.

Passo 4

Construindo a função passo a passo (linha a linha, explicando o que cada linha faz):
  • Assinatura: vamos chamar a função de affinities_pairs(afinities).
  • Dentro:
    1. Criar uma lista vazia \text{result} onde vamos guardar os pares mutuamente afetivos.
    2. Criar um conjunto vazio \text{seen} para registrar os pares já adicionados (vamos guardar tuplas (a,b) adicionadas).
    3. Iterar por cada (a,b) em affinities.items():
      • Obter \text{c} = affinities.get(b). Isso tenta ver para quem b gosta.
      • Verificar se \text{c} == a (ou seja, b gosta de a) e também se a \neq b para ignorar auto-afinidade.
      • Se for mútuo, testar se (b,a) não está em \text{seen}. Se não estiver, então:
        • Adicionar (a,b) à lista \text{result}.
        • Adicionar (a,b) ao conjunto \text{seen}.
    4. No final, retornar \text{result}.
  • Assim, garantimos que cada par mútuo aparece só uma vez, e a ordem do par preserva a visão “quem é a chave no dicionário” quando esse par foi visto primeiro.

Passo 5

Código da função explicada (aqui está a implementação pronta; logo abaixo, um exemplo de uso):
def affinities_pairs(affinities):
result = [] # lista onde vamos acumular os pares mutuos
seen = set() # conjunto para evitar duplicatas (guardamos pares já adicionados)
for a, b in affinities.items(): # percorre cada chave (a) e seu valor (b)
if a == b:
continue # ignora casos de “gostar de si mesmo”
if affinities.get(b) == a: # checa se b gosta de volta de a
if (b, a) not in seen: # verifica se o par oposto já não foi adicionado
result.append((a, b)) # adiciona o par na orientação (a, b)
seen.add((a, b)) # marca como adicionado
return result
Exemplo de uso com o dicionário do enunciado:
affinities = {‘Leo’: ‘Sofia’, ‘Marcos’: ‘Andrea’, ‘Sofia’: ‘Leo’, ‘Alex’: ‘Andrea’, ‘Andrea’: ‘Marcos’}
print(affinities_pairs(affinities))

saída provável: [(‘Leo’, ‘Sofia’), (‘Marcos’, ‘Andrea’)]

Passo 6

Complexidade e variações rápidas (dicas de prova e estudo)
  • Complexidade de tempo: O(n), onde n é o número de chaves no dicionário, porque cada entrada é verificada uma vez e as operações de conjunto e get() são O(1) em média.
  • Complexidade de espaço: O(k) onde k é o número de pares mútuos (para armazenar resultado e seen).
  • Variações: se quiser que cada par apareça ordenado alfabeticamente dentro da tupla, poderia usar tuple(sorted((a,b))). Se quiser ordenar a lista final por algum critério, ordenar depois de montar a lista.
  • Teste sempre com casos limites: dicionário vazio, pessoa que gosta de si mesma, cadeias sem reciprocidade, dois pares mútuos, etc.

Resposta

def affinities_pairs(affinities):
result = []
seen = set()
for a, b in affinities.items():
if a == b:
continue
if affinities.get(b) == a:
if (b, a) not in seen:
result.append((a, b))
seen.add((a, b))
return result

Exercícios relacionados