Datenstruktur für die Partition einer Menge

  • Eine Partition eines Sets S ist eine Trennung des Sets in eine beliebige Anzahl von nicht leeren, paarweise disjunkten Untergruppen, deren Vereinigung genau S lautet. Auf welche Art einer Datenstruktur sollte eine Partition einer Menge dargestellt werden, wenn die folgenden Methoden optimiert werden müssen:

    1. Verschieben eines Elements von einem Teil in einen anderen, möglicherweise ein völlig neues, und
    2. Durchlaufen der Teile der Partition.

    Eine naive Methode zur Priorisierung von 1 wäre eine Hash / Tree / -form-Zuordnung von Mengenelementen zu "Teilekennungen", aber das Iterieren der Teile würde O (N ) für das erste Konstruieren der tatsächlichen Teile aus den Etiketten. 2 wird naiv als Hash / Baum / was auch immer von Hash / Baum / was auch immer gesetzt, priorisiert, aber wenn Sie Elemente verschieben, insbesondere in neue Teilmengen, kommt dies zu Speicherverwaltungsaufwand.

    Gibt es eine Möglichkeit, das Beste aus beiden Welten zu bekommen? Die Implementierung, die ich brauche, ist Python, aber ich kann mir vorstellen, dass dies eine sprachübergreifende Frage ist.

    04 September 2012
    GillesTimeless
1 answer
  • Ich kenne das Thema nicht, daher kann ich nur ein paar Hinweise geben. Das Bearbeiten von Partitionen endlicher Mengen ist unter mehreren Namen bekannt:

    • union-find , wenn Sie mit Singletons beginnen und Sets schrittweise zusammenführen ;
    • Partitionsverfeinerung , wenn Sie mit einem einzelnen Satz und beginnen Teilen Sie es schrittweise auf;
    • union-split-find Wenn Sets wie in Ihrem Fall zusammengeführt und aufgeteilt werden können.

    Katherine J. Lai erörtert das Problem der Unionsspaltung und schlägt einen Algorithmus vor, der B-Bäume verwendet, der sich als Fingerbäume zur Darstellung jedes Satzes. Jedes Element wird durch eine bestimmte ganze Zahl dargestellt. Die Verwendung aufeinander folgender Werte für Elemente, die wahrscheinlich zusammenbleiben, ist effizienter. Um zwei Sätze zusammenzuführen, teilen Sie sie in nicht überlappende Intervalle, die vollständig in einem der Sätze enthalten sind, und verbinden Sie die Teile miteinander. Einzelheiten finden Sie in ihrer Doktorarbeit.

    03 September 2012
    GillesTimeless