Zur Zeit beschäftigt mich folgendes Problem:

Man betrachte eine Schublade S mit n schwarzen einzelnen Socken S_i, 1≤i≤n. Die Socken sind zwar wie gesagt allesamt schwarz, allerdings bestehen doch erkennbare Unterschiede, z.B. in Musterung, Länge, Grad der Verwaschenheit u.ä. Um das ganze zu formalisieren benötigen wir eine Ähnlichkeitsprädikat f, das ermittelt, ob sich zwei Socken genug ähneln, um als tragbares Paar bezeichnet werden zu können (In der Praxis wird f meist durch Nebeneinanderhalten und Anstarren der beiden Parametersocken bestimmt und ist damit selbst für einen festen Modegeschmack leider nicht wohldefiniert, da das Ergebnis z.B. von Beleuchtung und Tagesform abhängt). Der Einfachheit halber nehmen wir allerdings an, dass f(S_i,S_j) innerhalb einer gewissen Zeitspanne auch bei mehrmaliger Berechnung das gleiche Ergebnis liefert.

Erschwerend kommt hinzu, dass nicht zu jedem S_i ein S_j mit f(S_i,S_j) existiert (das Problem der verschwindenden Socken, allgemein bekannt), außerdem ist f nicht transitiv (aus f(S_i,S_j) und f(S_j,S_k) folgt nicht immer f(S_i,S_k)) - es können also keine disjunkten Äquivalenzklassen gebildet werden, stattdessen muss man mit schwammigeren Äquivalenzmengen Vorlieb nehmen.

Gesucht ist nun ein Algorithmus, der mit möglichst wenig Verwendungen von f möglichst viele Paare S_i, S_j mit f(S_i,S_j) aus S entfernt ("in die andere Schublade legt") und dabei möglichst wenige Socken in S verbleiben lässt (Natürlich müsste man an dem formalen Unterbau dieser Aufgabenstellung noch ein wenig arbeiten, ein wenig exakter werden und die passenden Quellen zitieren; um die Idee zu skizzieren sollte das erstmal langen).

Meiner oberflächlichen Recherche nach beschäftigen sich die meisten Arbeiten auf diesen Gebiet mit disjunkten und damit zerlegbaren Mengen von Socken ("Sock Selection Problem"), leider haben wir es bei dem vorgestellten Problem mit einem Haufen sich wirr überschneidender Teilmengen zu tun, fast so wie ein Wäschestapel in dem Katzen gespielt haben. Ich müsste mir mal ein wenig Zeit nehmen und ausführlich über das Problem nachdenken. Ganz unanbhängig davon: Dr. Seuss, Fox in Socks Matching Game.

... link