Ich möchte eine Sammlung von Elementen (mit einer potenziellen Größe von mehr als 100.000) sortieren, bei denen die Elemente in der Sammlung keinen inneren (vergleichbaren) Wert haben.lles, was ich habe, sind die Vergleiche zwischen zwei beliebigen Elemente, die von Nutzern subjektiv angegeben wurden.

Beispiel: Betrachten Sie eine Sammlung mit Elementen[a, b, c, d] und Vergleiche von Benutzernb > a, a > d, d > c. Die korrekte Reihenfolge dieser Sammlung wäre[b, a, d, c].

Dieses Beispiel ist einfach, es kann jedoch auch kompliziertere Fälle geben:

Da die Vergleiche subjektiv sind, kann ein Benutzer auch sagen, dassc > b. In diesem Fall würde dies zu einem Konflikt mit der obigen Reihenfolge führen.Auch haben Sie möglicherweise keine Vergleiche, die alle Elemente "verbinden", d. H.b > a, d > c. In diesem Fall ist die Bestellung nicht eindeutig. Es könnte sein[b, a, d, c] oder[d, c, b, a]. In diesem Fall ist jede Bestellung akzeptabel.

Wenn möglich, wäre es nett, mehrere Instanzen desselben Vergleichs zu berücksichtigen und denjenigen mit höheren Vorkommen mehr Gewicht zu verleihen. Aber eine Lösung ohne diese Bedingung wäre immer noch akzeptabel.

Eine ähnliche Anwendung dieses Algorithmus wurde von Zuckerbergs FaceMash-Anwendung verwendet, in der er Personen anhand von Vergleichen einstufte (wenn ich es richtig verstanden habe), aber ich konnte nicht herausfinden, was dieser Algorithmus tatsächlich war.

Gibt es bereits einen Algorithmus, der das obige Problem lösen kann? Ich möchte keine Mühe aufwenden, um eine zu finden, wenn dies der Fall ist. Wenn es keinen bestimmten Algorithmus gibt, gibt es vielleicht bestimmte Arten von Algorithmen oder Techniken, auf die Sie mich hinweisen können?