Um algoritmo feito assim pode varrer todas as
combinações de pares possíveis se isso for necessário (acho que é altamente
improvável que isso ocorra, talvez seja até impossível).
a demonstração que eu tinha imaginado para o
problema (logo após a sua primeira postagem) era +/- assim:
para n = 1 (1 casal) temos que é sempre
possível obter um "1-casamento"
suponha para todo 1 <= n < k seja sempre
possível obter um n-casamento
um (n+1)-casamento pode ser obtido da seguinte
maneira:
1) Existe um subconjunto Hx (1<= x <= n), de
x homens, e Mx, de x mulheres, tal que para todo homem de Hx as x
mulheres preferidas estão todas em Mx e para toda mulher de Mx seux x homens
preferidos estão em Hx.
neste caso, podemos dividir o
problema em dois menores, arranjando um x-casamento e um (n + 1 - x)-casamento,
o que é perfeitamente possível dentro da hipótese de indução
2) há uma mistura total de gostos!, neste caso
estamos com um problema chato para resolver.
ainda não tive nenhuma boa idéia de como lidar com
esse caso.
|
- [obm-l] Teorema de Donald Johann Peter Gustav Lejeune Dirichlet
- [obm-l] Para Peter Dirichilet Domingos Jr.
- [obm-l] Para Peter Dirichilet bruno lima
- RE: [obm-l] Teorema de Donald João Gilberto Ponciano Pereira