Problema estável no casamento

fundo

Suponha que haja 2*npessoas para se casar e, além disso, suponha que cada pessoa seja atraída por exatamente noutras pessoas sob as restrições de que:

1. Atração é simétrica ; isto é, se pessoa Aé atraída por pessoa B, então pessoa Bé atraída por pessoa A.
2. A atração é antitransitiva ; isto é, se pessoa Ae pessoa Bsão atraídas por pessoa C, pessoa Ae pessoa Bnão são atraídas uma pela outra.

Assim, a rede de atrações forma o gráfico bipartido completo (não direcionado) Kn,n. Também assumimos que cada pessoa classificou as pessoas pelas quais é atraída. Eles podem ser representados como pesos das arestas no gráfico.

Um casamento é um par (A,B)onde Ae Bsão atraídos um pelo outro. O casamento é instável se houver outro casamento em que uma pessoa de cada casamento possa se divorciar do parceiro e se casar, e ambos terminem com alguém com uma classificação superior à do ex-parceiro.

Objetivo

Sua tarefa é escrever um programa ou função completa que tome as preferências de cada pessoa como entrada e produza um casamento para cada pessoa, de modo que cada casamento seja estável.

Entrada

A entrada pode estar em qualquer formato conveniente; por exemplo, gráfico ponderado, lista ordenada de preferências, dicionário / associação, etc. Você pode opcionalmente considerar o número total de pessoas como entrada, mas nenhuma outra entrada é permitida.

Resultado

A saída também pode estar em qualquer formato conveniente; por exemplo, lista de tuplas, cobertura mínima de borda , uma função que associa a cada pessoa seu parceiro, etc. Observe que a única restrição é que cada casamento é estável, não há outros requisitos de otimização.

Notas

1. Você pode encontrar mais informações e um O(n^2)algoritmo para resolver esse problema na Wikipedia ou neste vídeo Numberphile . Você é livre para usar qualquer algoritmo, no entanto.
2. As brechas padrão são proibidas.
3. Isso é código-golfe . A resposta mais curta (em bytes) vence.

Mathematica, 28 bytes

Pensaria, isso é trapaça. Eu por mim mesmo assim:

Combinatorica`StableMarriage

• Precisa ser chamado com as matrizes de peso das preferências de homens e mulheres.
• Retorna os indizes diretos para o acoplamento.

(Sim, Combinatoricafoi preterido, mas custa menos bytes que FindIndependentEdgeSet)

Exemplo (GoT-like): (Para ser justo - adivinhei os pesos ... mas estou bem com os resultados)

m = {{2, 4, 3, 1}, {1, 2, 4, 3}, {3, 2, 1, 4}, {4, 2, 1, 3}};
w = {{2, 3, 4, 1}, {3, 2, 1, 4}, {3, 2, 4, 1}, {4, 1, 2, 3}};
result = Combinatorica`StableMarriage[w, m];
MapThread[
  UndirectedEdge[Show[#1, ImageSize -> 130], 
    Show[#2, ImageSize -> 130]] &, {names1, 
   names2[[result]]}] // TableForm