Conjuntos em Python: set, frozenset e Operações

Os artigos anteriores desta série apresentaram a teoria dos conjuntos em linguagem matemática: o que é um conjunto, como diagramas de Venn e operações funcionam e as noções de cardinalidade. Agora é hora de ver essa teoria em ação no Python.

A boa notícia: não é preciso importar nenhuma biblioteca especial. O Python implementa conjuntos matemáticos de forma nativa com o tipo set, mapeando diretamente os conceitos já estudados — inclusive a notação de pertinência, inclusão e as operações de união, interseção e diferença.

O tipo set

#

Em Python, um conjunto é criado com chaves {} separando os elementos, ou com o construtor set() recebendo qualquer iterável:

A = {1, 2, 3}
B = set([3, 1, 2])

print(A)      # {1, 2, 3}
print(A == B) # True

Duas propriedades matemáticas se aplicam automaticamente:

Unicidade — elementos repetidos são silenciosamente ignorados:

C = {1, 2, 2, 3, 3, 3}
print(C)      # {1, 2, 3}
print(len(C)) # 3

Sem ordem — o Python não garante nenhuma ordem de iteração, assim como \(\{1,2,3\} = \{3,2,1\}\) matematicamente:

print({1, 2, 3} == {3, 2, 1}) # True

O conjunto vazio: set(), não {}

#

vazio      = set()
dicionario = {}

print(type(vazio))      # <class 'set'>
print(type(dicionario)) # <class 'dict'>

Notação por compreensão

#

A definição matemática por compreensão \(C = \{x \in \mathbb{N} \mid x \text{ é par e } x < 10\}\) tem uma tradução quase literal em Python:

C = {x for x in range(1, 10) if x % 2 == 0}
print(C)  # {2, 4, 6, 8}

A estrutura {expressão for variável in iterável if condição} é chamada de set comprehension e segue exatamente a lógica da notação por compreensão matemática.

potencias = {2**n for n in range(10) if 2**n < 100}
print(potencias)  # {1, 2, 4, 8, 16, 32, 64}

Pertinência e inclusão

#

Python oferece operadores que mapeiam diretamente os símbolos matemáticos:

naturais = {1, 2, 3, 4, 5}
pares    = {2, 4}

print(3 in naturais)      # True  — 3 ∈ naturais
print(6 not in naturais)  # True  — 6 ∉ naturais
print(pares <= naturais)  # True  — pares ⊆ naturais
print(pares < naturais)   # True  — pares ⊂ naturais (inclusão estrita)
print(naturais >= pares)  # True  — naturais ⊇ pares
print(set() <= naturais)  # True  — ∅ ⊆ A para qualquer A

A última linha confirma em código a propriedade \(\emptyset \subseteq A\) para qualquer conjunto \(A\).

{1, 2}.issubset([1, 2, 3])  # True — funciona com lista
{1, 2} <= [1, 2, 3]         # TypeError — exige set

Operações entre conjuntos

#

As quatro operações fundamentais têm operadores dedicados:

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

print(A | B)  # {1, 2, 3, 4, 5, 6}  — A ∪ B
print(A & B)  # {3, 4}              — A ∩ B
print(A - B)  # {1, 2}              — A \ B
print(B - A)  # {5, 6}              — B \ A
print(A ^ B)  # {1, 2, 5, 6}        — A △ B

{1, 2, 3}.union([3, 4, 5])  # {1, 2, 3, 4, 5} — funciona
{1, 2, 3} | [3, 4, 5]       # TypeError — exige set

A = {1, 2, 3}
A |= {4, 5}    # equivalente a A.update({4, 5})
print(A)       # {1, 2, 3, 4, 5}

A &= {2, 3, 4} # equivalente a A.intersection_update({2, 3, 4})
print(A)       # {2, 3, 4}

Disjunção

#

Para verificar se dois conjuntos são disjuntos (\(A \cap B = \emptyset\)):

print({1, 2}.isdisjoint({3, 4}))  # True
print({1, 2}.isdisjoint({2, 3}))  # False

frozenset: o conjunto imutável

#

O Python oferece um segundo tipo de conjunto: frozenset. A diferença é que frozenset é imutável — seus elementos não podem ser adicionados ou removidos após a criação.

fs = frozenset({1, 2, 3})
# fs.add(4)  # AttributeError: 'frozenset' has no attribute 'add'

Por que isso importa? Porque frozenset pode ser elemento de outro set — algo impossível com set mutável:

# Tentativa com set mutável
{{1, 2}}       # TypeError: unhashable type: 'set'

# Com frozenset funciona
{frozenset({1, 2}), frozenset({3})}  # OK

Isso permite representar o conjunto das partes \(\mathcal{P}(A)\), cujos elementos são conjuntos — conceito introduzido no primeiro artigo desta série, onde o Diagrama de Hasse e a árvore de decisão ilustram sua estrutura:

from itertools import combinations

A = {1, 2, 3}
partes = {frozenset(sub)
          for r in range(len(A) + 1)
          for sub in combinations(A, r)}

print(len(partes))  # 8 = 2³  ✓
print(partes)
# {frozenset(), frozenset({1}), frozenset({2}), frozenset({3}),
#  frozenset({1, 2}), frozenset({1, 3}), frozenset({2, 3}),
#  frozenset({1, 2, 3})}

Cardinalidade com len()

#

A cardinalidade \(|A|\) de um conjunto é obtida com len():

A = {1, 2, 3}
print(len(A))         # 3  — |A| = 3
print(2 ** len(A))    # 8  — |𝒫(A)| = 2³ = 8

Por que set é tão rápido: hashability

#

A operação x in A em um set tem custo constante em média — \(O(1)\) — independentemente do tamanho do conjunto. Em uma lista, o mesmo teste exige percorrer os elementos um a um: \(O(n)\).

import time

grande = set(range(10_000_000))
lista  = list(range(10_000_000))

inicio = time.perf_counter()
_ = 9_999_999 in grande
print(f"set:  {time.perf_counter() - inicio:.2e} s")  # ~1e-07 s

inicio = time.perf_counter()
_ = 9_999_999 in lista
print(f"list: {time.perf_counter() - inicio:.2e} s")  # ~1e-01 s

Isso é possível porque o Python calcula um hash (uma impressão digital numérica) de cada elemento ao inseri-lo. Na busca, calcula o hash do valor procurado e vai direto à posição — sem percorrer nada.

A conexão com a teoria: na matemática, os elementos precisam apenas ser bem definidos. No entanto, para que o Python implemente isso com a velocidade que vimos acima, a linguagem impõe uma restrição prática: o elemento precisa ser imutável (hashable). É por isso que:

{[1, 2]}    # TypeError: unhashable type: 'list'
{(1, 2)}    # OK — tupla é imutável
{"texto"}   # OK — string é imutável

Listas são mutáveis: seu conteúdo pode mudar a qualquer momento, o que quebraria a invariante do hash. Tuplas, strings e números são imutáveis — portanto, hashable e aceitos como elementos.

Das identidades ao código

#

Os três artigos anteriores estabeleceram resultados que, vistos em equações, podem parecer abstratos. Com set em mãos, é possível executá-los diretamente — o que serve tanto para consolidar a intuição quanto para testar conjecturas antes de demonstrá-las formalmente.

Complemento

#

O artigo sobre operações define o complemento de \(A\) como \(\bar{A} = U - A\): tudo que está no universo mas não em \(A\). Python não oferece um operador de complemento nativo — e a razão é direta: set não carrega o universo consigo. É preciso defini-lo explicitamente:

U = set(range(1, 11))   # universo: {1, 2, ..., 10}
A = {1, 3, 5, 7, 9}    # ímpares

comp_A = U - A
print(comp_A)           # {2, 4, 6, 8, 10}

Essa limitação é uma consequência direta da hashability: um set armazena apenas seus próprios elementos, sem referência ao contexto maior em que está inserido. Na matemática, o universo \(U\) é sempre implícito; no código, ele precisa ser explícito.

Leis de De Morgan

#

O mesmo artigo prova as duas identidades:

Com o universo já definido, ambas podem ser verificadas diretamente:

U = set(range(1, 11))
A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7, 8}

comp_A = U - A
comp_B = U - B

# Primeira lei: complemento da união = interseção dos complementos
print((U - (A | B)) == (comp_A & comp_B))   # True

# Segunda lei: complemento da interseção = união dos complementos
print((U - (A & B)) == (comp_A | comp_B))   # True

Note que o artigo citado apresentou De Morgan no contexto da lógica booleana (not (A or B) ↔ not A and not B). Aqui as mesmas leis aparecem na versão conjuntista — e são a mesma estrutura algébrica vista de dois ângulos.

Princípio da Inclusão-Exclusão

#

O artigo sobre cardinalidade mostra que, quando dois conjuntos se sobrepõem, somar suas cardinalidades conta a interseção duas vezes. A correção é:

Em Python, len() e os operadores de conjunto permitem confirmar isso diretamente:

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

pie = len(A) + len(B) - len(A & B)
print(pie == len(A | B))  # True — 4 + 4 - 2 = 6

A igualdade vale para qualquer par de conjuntos finitos — o Python pode servir de verificador rápido ao trabalhar com exemplos concretos antes de uma demonstração formal.

Aplicações práticas

#

Deduplicação de listas

#

com_repeticao = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
sem_repeticao = list(set(com_repeticao))
print(sem_repeticao)  # [1, 2, 3, 4, 5, 6, 9]  (ordem não garantida)

sem_repeticao_ordenado = list(dict.fromkeys(com_repeticao))
print(sem_repeticao_ordenado)  # [3, 1, 4, 5, 9, 2, 6] (ordem preservada)

Verificação de permissões

#

permissoes_necessarias = {"leitura", "escrita"}
permissoes_usuario     = {"leitura", "escrita", "execucao"}

tem_acesso = permissoes_necessarias <= permissoes_usuario
print(tem_acesso)  # True — permissoes_necessarias ⊆ permissoes_usuario

Elementos em comum entre grupos

#

turma_a = {"Ana", "Bruno", "Carla", "Diego"}
turma_b = {"Bruno", "Carla", "Eduardo", "Fernanda"}

em_ambas = turma_a & turma_b
print(em_ambas)   # {'Bruno', 'Carla'}

so_em_a = turma_a - turma_b
print(so_em_a)    # {'Ana', 'Diego'}

Quando não usar set

#

O fluxograma abaixo resume a decisão de qual tipo usar quando a coleção precisa de elementos únicos:

flowchart TD
  A["Preciso de uma coleção"] --> B{"Elementos únicos
sem ordem?"}
  B -- "Não" --> C{"Ordem
importa?"}
  C -- "Sim" --> D["list"]
  C -- "Não" --> E{"Multiplicidade
importa?"}
  E -- "Sim" --> F["collections.Counter"]
  E -- "Não" --> G{"Associação
chave → valor?"}
  G -- "Sim" --> H["dict"]
  G -- "Não" --> D
  B -- "Sim" --> I{"Precisa ser
imutável / hashável?"}
  I -- "Não" --> J["set"]
  I -- "Sim" --> K["frozenset"]

Exercícios

#

print(type(set()))  # <class 'set'>
print(type({}))     # <class 'dict'>

A, B = {2, 4}, {1, 2, 3, 4, 5}
print(A <= B)       # True — (i)  A ⊆ B
print(A < B)        # True — (ii) A ⊂ B (inclusão estrita)
print(set() <= A)   # True — (iii) ∅ ⊆ qualquer conjunto

A, B = {1, 2, 3, 4}, {3, 4, 5, 6}
print(A | B)  # {1, 2, 3, 4, 5, 6}
print(A & B)  # {3, 4}
print(A - B)  # {1, 2}
print(A ^ B)  # {1, 2, 5, 6}

tags1 = ["python", "conjuntos", "matematica", "programacao"]
tags2 = ["python", "conjuntos", "grafos",     "programacao"]

t1, t2 = set(tags1), set(tags2)
print(t1 & t2)   # {'python', 'conjuntos', 'programacao'}
print(t1 - t2)   # {'matematica'}
print(t1 <= t2)  # False — 'matematica' não está em t2

from itertools import combinations

A = {1, 2, 3}
partes = {frozenset(sub)
          for r in range(len(A) + 1)
          for sub in combinations(A, r)}

print(len(partes))  # 8 ✓

Próximos passos

#

Com a teoria e a implementação Python consolidadas, a série prossegue para outros tópicos de Matemática Discreta. Para aprofundar o uso de set e frozenset, consulte a documentação oficial do tipo set e o módulo itertools para operações combinatórias sobre conjuntos.

Até o próximo artigo!