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’)]
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
tais que gosta de e gosta de .
Observações importantes que vêm do enunciado e precisamos considerar:
- O dicionário tem pares “quem” -> “quem gosta”.
- Quando
e são mutuamente ligados, a função deve listar esse par exatamente uma vez (não repetir e ). - 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
e seu valor : - Verificar se
está presente como chave no dicionário (ou seja, se sabemos para quem gosta). - Verificar se o dicionário diz que
gosta de , isto é, se a afinidade é recíproca. - Evitar adicionar o par duas vezes (quando depois encontrarmos a entrada
→ ). Uma maneira simples de evitar duplicação é: só adicionar se ainda não tivermos adicionado .
- Verificar se
- 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
. - 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
: para cada par chave-valor 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
(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 (
) com pares já adicionados. Para verificar se já adicionamos o par oposto, podemos testar se está em . 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+):
-
“Leo”, “Sofia”. Checamos affinities.get(“Sofia”) que é “Leo”. Como isso iguala e , temos mutualidade. Como ainda não adicionamos (“Sofia”,“Leo”), adicionamos (“Leo”,“Sofia”). -
“Marcos”, “Andrea”. affinities.get(“Andrea”) é “Marcos” → mutuo. Ainda não adicionamos (“Andrea”,“Marcos”), então adicionamos (“Marcos”,“Andrea”). -
“Sofia”, “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. -
“Alex”, “Andrea”. affinities.get(“Andrea”) é “Marcos”, não é “Alex” → não é mútuo. -
“Andrea”, “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
— 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:
- Criar uma lista vazia
onde vamos guardar os pares mutuamente afetivos. - Criar um conjunto vazio
para registrar os pares já adicionados (vamos guardar tuplas adicionadas). - Iterar por cada
em affinities.items(): - Obter
affinities.get(b). Isso tenta ver para quem gosta. - Verificar se
(ou seja, gosta de ) e também se para ignorar auto-afinidade. - Se for mútuo, testar se
não está em . Se não estiver, então: - Adicionar
à lista . - Adicionar
ao conjunto .
- Adicionar
- Obter
- No final, retornar
.
- Criar uma lista vazia
- 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
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))
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:
, onde é o número de chaves no dicionário, porque cada entrada é verificada uma vez e as operações de conjunto e get() são em média. - Complexidade de espaço:
onde é 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
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