distance_aufgabe.rst

Es seien zwei variabel lange Listen mit variabel langen Tupeln darin: :

a = [(85, 0), (190, 2), (190, 6)]
b = [(85, 0), (190, 2, 0), (190, 2, 0), (190, 6)]

Die Listen sind stets sortiert, kleinste Werte zuerst. Es soll eine Distanzfunktion geschrieben werden die diese beiden Listen auf Ähnlichkeit untersucht. Diese Funktion soll eine Zahl zwischen 0.0 (volle ähnlichkeit) und 1.0 (volle divergenz) ergeben.

Schwierigkeit: Eine Distanzfunktion muss folgened Kriterien erfüllen: :

dist(a, a) = dist(b, b) = 0  # Gleiches muss stets völlig gleich sein.
dist(a, b) = dist(b, a)      # Die Reihenfolge der Parameter muss vertauschbar sein.

Die einzelnen Tupel sollen folgendermaßen untereinander verglichen werden:

1. Element für Element, breake falls ungleich.
2. Gebe zurück: Anzahl der gleichen durch die Länge des längeren beider Tupel.

Randbemerkung: Die Tupel stellen einen Pfad durch einen Baum da. Daher sind sie auch unterschiedlich lang.

Rein zur Vorstellung.

Code dafür gibts gratis:

def compare_single_path(left, right):
    n = 0.0
    for l, r in zip(left, right):
        if l == r:
            n += 1
        else:
            break
    return 1 - n / (max(len(left), len(right)) or 1)

Schreibe eine Distanzfunktion mit diesen Eigenschaften!