В этом задании мы рассмотрим задачу кластеризации объектов. Вам необходимо реализовать два алгоритма кластеризации, которые разбирались на лекциях:

1) Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние;
2) Кластеризация жадным алгоритмом, приближенно минимизирующая максимальное внутрикластерное расстояние.

Мы будем работать с текстами в виде векторов, где каждому отдельному слову соответсвует координатная ось.
Текст разбивается на слова и для каждого слова считается количество его повторений.
Такие вектора обычно содержат много нулей, поэтому мы их будем хранить в виде списка пар - id слова и количество повторений

Вам дается код с заготовкой на Python, в котором реализованы три функции растояния, а также наборы текстов.
test_5 - стартовый набор содержащий всего 50 тестов.
test_4, test_10, test_50, test_100 - наборы на 400, 1000, 5000, 10000 соотвественно.
Код python работает недостаточно эффективно для 1000+ текстов, поэтому рекомендуем запастить терпением или переписать существующий код на C++
Запишите вашу реализацию в функцию cluster.
Приведите примеры удачных и неудачных разбиений для каждого алгоритма.

Каждый файл теста имеет вид
N
M
K
TextId WordID count
...
TextId WordID count
Где N - колчество текстов, M - количество уникальных слов, K - количество строк, TextId [1, N], WordId [1, M]

Также вы можете найти файлы вида map_test_...txt - отображение слов для соответсвующих тестов в GlobalWordId
vocab.nytimes.txt - содержит последовательно все слова. То есть iое слово в этом файле есть слово с GlobalWordId == i
Обращаю внимание, что вся нумерация текстов и слов начинается с 1!!!

Пояснения по коду:
1) filename - имя файла с тестом
2) distance - функция, используемая для подсчета расстояния
3) clusters_num(num_of_clusters) - желаемое количество кластеров
4) min_count и max_count - границы частоты учитываемых слов. То есть, слова которые встречаются во всех текстах менее чем min_count или более чем max_count не учитываются