Задача "Легенды футбола"

README.md

Идея следующая - загнать футбольные команды в граф, где вершины - команды, а рёбра - показатель того, что в командах есть дублирующиеся игроки, после чего задача сводится к задаче о независимом множестве (http://ru.wikipedia.org/wiki/Задача_о_независимом_множестве).

Картинка:

Там кажется, что 2 и 5 связаны - это не так. 2 и 5 по отдельности связаны с 15-ю.

В коде неоптимально вычисляется пересечение - достаточно самого факта, а вычисляем пересечение целиком. Можно заоптимизировать.

Надо сказать, что поскольку задача о независимом множестве NP-полная, а "Легенды футбола" сводится к ней за полиномиальное время, то и "Легенды футбола" NP-полная задача, и нечего комплексовать, что не можем придумать к ней оптимального алгоритма. Тут и подходят-то только поиск с возвратом, жадный поиск, A* и их друзья.

fooball.R

#!/usr/bin/env Rscript

# Решение разминки "Легенды футбола".
# http://vecherka.cssum.net/v5/warm-up-football-legends.html
# Идея следующая - загнать футбольные команды в граф,
# где вершины - команды, а рёбра - показатель того, что 
# в командах есть дублирующиеся игроки,
# после чего задача сводится к задаче о независимом множестве.
# http://ru.wikipedia.org/wiki/Задача_о_независимом_множестве

library(rjson)
library(igraph)

json.file <- "http://vecherka.cssum.net/v5/warm-up-football-legends/teams.json"
team.data <- fromJSON(paste(readLines(json.file), collapse=""))

team.graph <- graph.empty(directed = FALSE) + vertices(names(team.data))

# проводим ребра, если у команд есть непустое пересечение
for (pair in combn(names(team.data), 2, simplify = FALSE)) {
  first.players <- team.data[[pair[1]]]
  second.players <- team.data[[pair[2]]]
  if (length(intersect(first.players, second.players)) > 0) {
    team.graph <- team.graph + edges(pair[1], pair[2])
  }
}

# Задача свелась к задаче о независимом множестве.
# Хорошие библиотеки сильно помогают в решении исследовательских задач.
solutions <- largest.independent.vertex.sets(team.graph)

for (solution in solutions) {
  print("Решение:")
  for (team.vertice.id in solution) {
    print(V(team.graph)[team.vertice.id]$name)
  } 
}

output.txt

[1] "Решение:"
[1] "Аякс Амстердам 1994-95"
[1] "Ювентус 1995-96"
[1] "Манчестер Юнайтед 1998-99"
[1] "Динамо Киев 1990-2000"
[1] "Реал Мадрид 2001-02"
[1] "Арсенал 2003-04"
[1] "Ливерпуль 2005-06"
[1] "Барселона 2005-06"
[1] "Милан 2007-08"

Вывод:

[1] "Решение:"
[1] "Аякс Амстердам 1994-95"
[1] "Ювентус 1995-96"
[1] "Манчестер Юнайтед 1998-99"
[1] "Динамо Киев 1990-2000"
[1] "Реал Мадрид 2001-02"
[1] "Арсенал 2003-04"
[1] "Ливерпуль 2005-06"
[1] "Барселона 2005-06"
[1] "Милан 2007-08"

Вывод:

[1] "Решение:"
[1] "Аякс Амстердам 1994-95"
[1] "Ювентус 1995-96"
[1] "Манчестер Юнайтед 1998-99"
[1] "Динамо Киев 1990-2000"
[1] "Реал Мадрид 2001-02"
[1] "Арсенал 2003-04"
[1] "Ливерпуль 2005-06"
[1] "Барселона 2005-06"
[1] "Милан 2007-08"

[1] "Решение:"
[1] "Аякс Амстердам 1994-95"
[1] "Ювентус 1995-96"
[1] "Манчестер Юнайтед 1998-99"
[1] "Динамо Киев 1990-2000"
[1] "Реал Мадрид 2001-02"
[1] "Арсенал 2003-04"
[1] "Ливерпуль 2005-06"
[1] "Барселона 2005-06"
[1] "Милан 2007-08"