Ich suche nach einer funktionellen Datenstruktur, die endliche Bijektionen zwischen zwei Typen darstellt, das ist platzsparend und zeiteffizient.
Zum Beispiel würde ich mich freuen, wenn ich eine Bijektion f der Größe n in Betracht ziehe:
Ich bin mir der effizienten Darstellung von Permutationen bewusst, wie dieses Papier , aber es scheint mein Problem nicht zu lösen .
Bitte werfen Sie einen Blick auf meine Antwort für eine relativ ähnliche Frage. Der angegebene Code kann allgemeine NxM-Beziehungen behandeln, aber auch auf Bijektionen spezialisiert sein (genau wie bei einem binären Suchbaum).
Die Antwort hier der Vollständigkeit halber einfügen:
Am einfachsten ist es, ein Paar unidirektionaler Karten zu verwenden. Es kostet etwas, aber Sie werden nicht viel besser (Sie könnten ein bisschen besser mit dedizierten binären Bäumen, aber Sie haben eine große Komplexität Kosten zu zahlen, wenn Sie es selbst implementieren). Im Prinzip sind Suchvorgänge genauso schnell, aber das Hinzufügen und Löschen ist doppelt so lang. Was für eine logarithmische Operation nicht so schlecht ist. Ein weiterer Vorteil dieser Technik besteht darin, dass Sie für den Schlüssel- oder Werttyp spezielle Zuordnungstypen verwenden können, wenn Sie einen verfügbar haben. Mit einer bestimmten generalistischen Datenstruktur erhalten Sie nicht so viel Flexibilität.
Eine andere Lösung ist die Verwendung eines Quadtree (anstatt eine NxN-Beziehung als ein Paar von 1xN- und Nx1-Relationen zu betrachten, sehen Sie sie als eine Menge von Elementen im kartesischen Produkt (Key * Value) Ihrer Typen , eine räumliche Ebene), aber mir ist nicht klar, dass die Zeit- und Speicherkosten besser sind als bei zwei Karten. Ich nehme an, es muss getestet werden.
Obwohl es Ihre dritte Anforderung nicht erfüllt, bimap scheinen wie der Weg zu gehen. (Sie machen nur zwei endliche Karten, eine in jeder Richtung, bequem zu verwenden.)
Tags und Links haskell data-structures functional-programming ocaml bijection