main.py (956f128) - dost

main.py

import math
import typing
import collections.abc

Func: typing.TypeAlias = collections.abc.Callable
DistTable: typing.TypeAlias = list[list[float]]
IndSeq: typing.TypeAlias = list[int]

def distance_table[T](points: list[T], metric: Func[[T, T], float]) -> DistTable:
    return [[metric(x, y) for y in points] for x in points]

def score_nearest(distances: DistTable, sample: IndSeq) -> float:
    return sum(min(distances[i][j] for j in sample) for i in range(len(distances)))

def score_total(distances: DistTable, sample: IndSeq) -> float:
    return sum(sum(
        0 if i in sample else distances[i][j] for j in sample
    ) for i in range(len(distances)))

def greedy_min_seq(distances: DistTable, score_func: Func[[DistTable, IndSeq], float]) -> IndSeq:
    seq = []
    options = set(range(len(distances)))
    while options:
        best = min(options, key=lambda o: score_func(distances, seq + [o]))
        seq.append(best)
        options.remove(best)
    return seq

dt: DistTable = distance_table([(0, 2), (3, 2), (4, 2), (5, 0), (0, 0)], math.dist)
print(greedy_min_seq(dt, score_total))

dost

Initial commit: greedy nearest-neighbour and total