In der Tat habe ich mich bei der Suche nach der Lösung des Sockenproblems viel zu früh auf eine Modellierung festgelegt. Als wir heute im Dekanat darüber diskutierten kam Prof. Madlener (Grundlagen der Informatik, formale Methoden) vorbei und fand meinen Graphenansatz "nett, aber übertrieben". Stattdessen schlug er folgende Lösung vor:

Man entscheidet sich für ein einziges Unterscheidungskriterium (Farbe, Farbton, Länge, Breite, Muster, Musterung, etc.) und bildet Haufen mit Socken, die hinsichtlich dieses Kriteriums gleich sind. Ist der Haufen groß genug wählt man ein neues Unterscheidungskriterium oder unterscheidet genauer und unterteilt diesen Haufen nochmals auf die gleiche Art in kleinere (man wendet das Verfahren also rekursiv an); bei kleinen Haufen kann man dann einfach passende Socken zusammenfügen.

Ich habe das ganze mal ausprobiert und damit in deutlich weniger als einer halben Stunde meinen Sockenhaufen in 42 passende Sockenpaare und 10 unzuteilbare Einzelsocken umwandeln können. Verglichen mit meine bisherigen Sockensortierzeiten eine fantastische Verbesserung. Probleme treten nur bei schwer unterscheidbaren Socken auf, hierbei ist das größte Problem, ein sinnvolles Entscheidungskriterium zu formulieren.

Insgesamt bin ich mit dieser Lösung sehr zufrieden.